An Introduction to Quantum Computers and Quantum Coding | by Oliver W. Johnson | Aug, 2024

Demystifying the novel world of quantum computing, quantum programming, and quantum algorithms.

Preface:

This is an adaptation of something I wrote for one of my physics courses, so it assumes a level of knowledge in mathematics and science. The topics referenced in the article include some linear algebra, superposition, basic algorithm concepts, and a bit of modular arithmetic when discussing algorithms. However, since you’re reading an article on quantum computing you’re likely savvy enough to look up and understand all the ideas referenced. Furthermore, all sources are cited, so you can explore all of those for deeper learning. Also, all images and figures used were generated by me, using tools like Microsoft Word, PyCharm, and diagrams.net unless otherwise noted.

Why Does This Matter?

Before committing to a somewhat lengthy and dense read, you might be wondering why this matters to you, even if you’ve never touched a quantum computer. The reality is that breakthroughs are happening all the time, and quantum computing holds real relevance in different computational fields, especially machine learning. For starters, the quantum analogs of classical algorithms have potential to be much more efficient.

One example of this is the Quantum Support Vector Machine. Notably, classical SVMs often use the kernel trick to transform data into a higher dimensional space so that they can locate a separating hyperplane. However, quantum SVMs would have a significant advantage as they naturally represent data in exponentially higher dimensional spaces without the computational strain that classical computers face. This allows quantum SVMs to handle more complex datasets more efficiently.

Another example is in the realm of neural network training. The basic unit of quantum computation, the qubit, can be entangled with other qubits, creating correlations that classical systems can’t replicate. While entanglement offers possibilities for correlated updates across a quantum neural network, it’s important to note that the concept is still under research.

Part 1: Introduction to Quantum Computing

Quantum computers function very differently from classical computers, leveraging quantum properties and phenomena to greatly increase computational power. At a high level, there are a few tenets of quantum computing that differentiate it from classical computation: qubits versus bits, quantum versus classical logic gates, the presence of quantum phenomena, and the opportunities offered by quantum computing’s enhanced computational capabilities.

At the core of quantum computing is the qubit, which serves as the fundamental unit of computation in a quantum computer– taking the place of a classical computer’s bit. While the bit can occupy either the 0 or 1 state exclusively, the qubit can be in a superposition of the 0 and 1 states (Microsoft, n.d.). It can be very hard to conceptualize the qubit; where the classical bit is simply an electric current or absence of electric current, the qubit can take many different physical forms.

These include “spin” qubits, which is the most straightforward example. This type of qubit uses the spin property of a particle (generally an electron) to complete computations. To initialize a spin qubit, an electron is trapped using a quantum dot, for example, then manipulated using magnetic fields that interact with their spin state (Harvey, 2024). The computational difference between a bit and qubit is significant, and stems from the qubit’s ability to be affected by quantum phenomena like superposition between the 0 and 1 states, and entanglement with other qubits (Microsoft, n.d.).

One tool that is very helpful in visualizing the state of a qubit is the Bloch sphere; it is effectively just a sphere with north and south poles representing |0⟩ and |1⟩ respectively, and all other points along the sphere representing linear combinations of the poles’ values (Microsoft, 2024). Since this representation of the qubit uses a complex vector space, the state of the qubit will be described in Dirac notation hereafter. This visualization of the superposition state of a qubit aids in the understanding of quantum logic gates especially because it allows for a geometric understanding of the operation being performed. Generally, when a qubit is initialized it is in the z-basis |0⟩ state, which is analogous to the classical 0 state (Quantum-Inspire by QuTech, 2024).

Another key difference between the classical and quantum computer is the logic gates: while classical computers use AND, OR, NOT, etc. to perform basic logic operations, quantum computers use quantum logic gates such as X, Hadamard, Toffoli, and CNOT (Wikipedia, 2024). These quantum gates are used to perform logical operations on a single qubit or a very small number of qubits, and can be combined with others to perform more complex operations and manipulations.

1. First, the X gate is very similar to the classical NOT gate: it inverts the phase of a qubit– if a qubit is in the |0⟩ state, it inverts to the |1⟩ state, and vice versa.
2. Next, the Hadamard gate is used to put a qubit in the |0⟩ state into an equal superposition between |1⟩ and |0⟩. Third, the Toffoli gate is an example of a multi-qubit gate.
3. The Toffoli gate operates with three qubits, two of them are “control” and one is the “target.” In the Toffoli gate it will invert the target qubit only if the two control qubits are in the |1⟩ state (Roy & Chakrabarti, 2024).
4. Finally, the CNOT gate is a very common gate used in quantum computing, and we will examine a use case later on. The CNOT is also a multiple qubit gate, as it has one target qubit and one control qubit; when the control qubit is in the |1⟩ state, it inverts the phase of the target qubit.

These are just a few examples of many interesting quantum logic gates, and it is important to note that unlike classical logic gates, there is not necessarily a physical “gate” that the qubits pass through, but rather these are just operations that are performed on the qubit which take different forms depending on many factors.

A third major difference between classical and quantum computing is the presence of quantum phenomena such as superposition, superconduction, entanglement and interference. These properties are used in different ways depending on the methods used to perform quantum computations (Microsoft Azure, 2024). Another property that is present is quantum decoherence, which poses a serious problem to the development of useful or widespread quantum computing. Quantum decoherence is when a particle in superposition interacts with its environment and becomes entangled with the environment, ultimately interfering with the computational outcome (Brandt, 1999).

The computational advances of a quantum computer are great: take, for example, the algorithm used for finding the prime factors of an integer. In classical computing, one of the leading prime factorization algorithms is General Number Field Sieve (Wikipedia, 2024). The program runs at a quasi-polynomial time complexity, and it shows how hard it can be to factor a very large number. Compared to the leading quantum algorithm, Shor’s Algorithm, which runs in logarithmic space complexity, and a polylogarithmic time complexity, which is once again a complicated expression, but boils down to the fact that it is vastly more efficient (Li et al., 2022). Obviously this is just one example, but it serves as a testament to the power of quantum computing– the power to turn a program which runs in exponential time into a program which runs in logarithmic time is truly remarkable.

Part 2: Quantum Programming: Languages, Compilers and Algorithms

Though their hardware is fundamentally different from classical computers, quantum computers are programmed using languages often similar in syntax to classical languages. These include QCL, Qiskit, and Q#, who are based around the syntax of C, Python, and C#/F# respectively. Furthermore, their compilers are built with C++, Python and C++, and C# respectively. (IonQ, 2024). Thus, classical and quantum languages can be very similar syntactically– the main difference comes from the content of the programs, and how quantum algorithms are structured.

Before examining different languages, their syntaxes, and how they compare to the classical languages that they’re based around, it’s important to understand the content of a quantum program and why no matter how similar the syntax is, there is an unbridgeable gap between a classical and quantum program.

This stems from the mechanics of a quantum computer– as discussed before, quantum computation is based around holding qubits in superposition, and applying different “gates” to them– effectively transformations along the Bloch sphere that they are represented by. What that boils down to is the fact that unlike a classical computer, where you write a program which will utilize a pre-made circuit to perform computations, quantum programming is the act of actually encoding the circuit. Let’s examine some pseudo code and its associated quantum circuit to better understand this. Maybe the simplest possible quantum program/circuit, the following program simply initializes a qubit, applies a Hadamard gate to put it into a superposition, then measures the state of the qubit.

The associated quantum circuit for this program is:

The double line following the measurement symbol indicates that the qubit is no longer in a superposition, but rather one of two discrete states (0 or 1) since its wave function was collapsed during the measurement.

To get a better feel for the syntax of different quantum languages, let’s look at programs in the three aforementioned languages that all serve identical purposes. All three programs are made to create a Bell state, which is an entangled state of two qubits. The gates (operations) applied to the two qubits are: Hadamard on the first qubit, 0, then on the second qubit, 1, with the first qubit as the control. The function of the CNOT gate is effectively just to entangle two qubits (Rioux, 2023).

#Qiskit (Python Basd)
#Create a quantum circuit with two qubits
qc = QuantumCircuit(2)
#Apply a Hadamard gate on the first qubit
qc.h(0)
#Apply a CNOT gate with the first qubit as control and the second qubit as target
qc.cx(0, 1)

//Q# (C#/F# based)
namespace BellState{
operation PrepareBellState() : Unit{
using (qubits = Qubit[2]) {
//Apply a Hadamard gate on the first Qubit
H(qubits[0]);
//Apply a CNOT gate with the first qubit as control and the second qbit as target
CNOT(qubits[0], qubits[1]);
}
}
}

//QCL (C based)
init {
qubits q[2]
//Apply a Hadamard gate on the first qubit
H(q[0]);
//Apply a CNOT gate with the first qubit as control and the second as target
CNOT(q[0], q[1]);
}

Unsurprisingly, the quantum programs look very similar in syntax to the languages each is based on– for example the Pythonic program uses a couple built-in methods and doesn’t have much else going on and the C# based program is full of curly brackets. Reviewing the syntax of a few quantum languages is helpful to understand what a quantum program looks like, but the reality is that the hardware being used is so different that the actual code in a quantum program would be useless to a classical computer, and vice versa. Because of that, it would be much more interesting to analyze two algorithms made for the same purpose, one classical and one quantum, and dissect the different steps taken in each case to achieve the result.

Recall the example presented in Part 1 (GNFS and Shor’s algorithm), where we looked at the time complexities of two prime factorization algorithms. As both algorithms are rather abstract and complex, it may be easier to understand their respective theories in paragraph format instead of examining their pseudo code.

The classical algorithm, General Number Field Sieve, can be summarized into five main algorithmic steps (Case, n.d.). Throughout the explanation, “N” refers to the number being factored.

1. The first step is polynomial selection: this step involves selecting two polynomials such that they multiply to smooth numbers when evaluated at certain points modulo N.
2. The next step is the “sieve” step: the goal is to find sets of integers (a, b) such that 𝑓(𝑎)⋅𝑔(𝑏) ≡ ℎ2(mod N) where h is a smooth number, and store all values (a, b, and h).
3. The third step is the matrix step: a large matrix, A, is constructed from the relations found in the sieve step.
4. Next use Gaussian elimination to reduce A to a simpler form while preserving its properties. This process will identify a set of linearly independent relations.
5. Use linnear algebra methods such as Lanczos algorithm to find the null space of the matrix– this will give vectors that correspond to dependencies among the relations.
6. Combining the relations found before will produce squares in modulo N, which after further mathematical manipulation give two integers X and Y.
7. These two integers are used to find the non trivial factors of N by computing the GCD of X — Y and X + Y with respect to N (Case, n.d.). That method is described by quasi-polynomial complexity, which, while it does run in sub-polynomial time, is much slower than the quantum method, Shor’s algorithm.

The process of calculating an integer N’s prime factors using Shor’s algorithm is entirely different from using GNFS. Shor’s algorithm can be broken down into a few main steps.

1. The first step uses classical computing: pick a random integer r such that 1 < r < N, calculate their GCD’s and if it does not equal 1, it is a non-trivial factor of N.
2. The next step is to prepare the needed qubits– we do this with two quantum registers, which function just like classical registers. In the first register there are enough qubits to represent integers from 0 to q–1 where q is a power of 2 that is at least N². The second register has enough qubits to represent integers from 0 to N–1.
3. The next step deviates from classical computing heavily: to put the entire first register into a superposition, apply a Hadamard transform to each qubit.
4. Next use a quantum circuit to compute the function f(x) = r^x mod(N) and store the result in the second register; this will entangle the first and second registers.
5. Next measure the second register– this will collapse it into a state |k⟩ (where k = r^x mod(N)) which leaves the first register in a superposition of values x that map to |k⟩.Now the period of the function f(x)=r^x mod(N) can be expressed as T.
6. The penultimate step of the algorithm is to apply a quantum fourier transform (QFT) to the first register, which will yield a series of peaks in the frequency domain corresponding to values of 1/T.
7. The final step in the quantum computation is to measure the first register– the result will be an integer, B, such that B is q/T, recall q from when we defined the first register. Having completed the quantum computation, you then move onto the classical post-processing step to get the final result.

The post-processing involves manipulating the measured result B to get the period, T. If T is even, compute the GCD of N with r^(T/2) + 1 and r^(T/2) – 1, which will yield non-trivial factors of N. If T is odd, repeat algorithm with a different r value. This program’s polylogarithmic time complexity is very efficient, especially compared to the GNFS algorithm (Pavlidis & Gizopoulos, 2022).

Here is a visual representation of the flow of both algorithms to aid understanding, where red is the beginning step, blue is the GNFS algorithm, and green is Shor’s algorithm:

What enables Shor’s algorithm to run so much faster than the GNFS is the fundamentally different computational concepts being used: Shor’s algorithm leverages quantum mechanics to achieve polynomial time complexity. This speedup is primarily due to quantum parallelism (the ability to perform many quantum operations at the same time) and the efficient execution of the quantum Fourier transform, which are impossible in classical computing. By utilizing superposition and entanglement, Shor’s algorithm reduces factoring to a period-finding problem, solved exponentially faster than classical methods (Brandt, 1999).

Obviously both algorithms are very complex, but they serve as an excellent example since the problem of factoring a large integer is something a quantum computer can do much faster than a classical computer. A much simpler example that we can analyze the quantum code for is a quantum take on rock-paper-scissors (or a coin toss if that’s easier to think about). Two players each initialize a qubit (one each) to the |0⟩ state and apply a Hadamard gate which puts it into an equal superposition between |0⟩ and |1⟩. Finally, both qubits are measured– if both qubits collapse to the |0⟩ or |1⟩ state, it is a draw. Otherwise, whoever’s qubit collapsed to the |0⟩ state loses, and the one who’s qubit collapsed to the |1⟩ state wins. Let’s write the code to run this program in Qiskit:

qc = QuantumCircuit(2, 2)  # initialize a quantum circuit with 2 qubits and 2 classical bits
qc.h(0)  # apply Hadamrd gate to qubit 0, this is Bob's qubit
qc.h(1)  # apply Hadamard gate to qubit 1, this is Alice's qubit
qc.measure(0, 0) # measure Bob's qubit and map it to classical bit 0
qc.measure(1, 1) # measure Alice's qubit and map it to classical bit 1
print(qc) # prints the quantum circuit accociated with this program

The output of that code is simply the quantum circuit associated with the program, since it never actually runs the circuit on a quantum computer. However, that is the general format used when defining a very basic quantum circuit– a number of qubits and bits are allocated to it, then stating– in order– the operations to be performed on each qubit. The output of this code, which is just a visual representation of the circuit is:

Before we can run this program on a quantum computer, there are a few steps we need to take. The most important is optimizing the circuit; not all quantum computers have the same ability to operate on qubits with certain gates, and they don’t always have the same connectivity of qubits. We need to add this circuit optimization into our code to prepare it to run on a real quantum computer. To do this we use the following code which defines our access to the IBM Quantum Backend using an IBM API key, then runs an optimization of the circuit, printing the optimized circuit.

print(qc) # prints the quantum circuit accociated with this program
service = QiskitRuntimeService(channel="ibm_quantum", token="your_token")
backend = service.least_busy(simulator=False, operational=True)
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_circuit = pm.run(qc)
print(isa_circuit)

The output of this program is less important since it is just a more complex version of the same circuit, but it results in a circuit that is optimized for an IBM Quantum computer and while it looks much different and more complicated, it will function the same as the circuit from earlier.

In conclusion, while the topic of quantum programming can be daunting due to its many languages and contrasting algorithms, as well as the background in math, physics, and computing needed to understand it, when broken down right it’s not so bad. Through incremental learning it’s very achievable to understand quantum computing. Furthermore, quantum computing has fascinating aspects in many STEM fields– number theory, linear algebra, calculus, and discrete mathematics all apply to the theoretical side of quantum algorithms; engineering, physics, computer science, and logic all apply to the actual design of quantum algorithms. Then again, the more you learn about the fascinating realm of quantum computing, the more you may find yourself feeling like Richard Feynman’s famous quote: “I’m smart enough to know that I’m dumb.” (Goodreads, 2024)

References

Adedoyin, A., & et. al. (2022, January 8). Quantum Algorithm Implementations for Beginners. ACM Digital Library. Retrieved May 27, 2024, from https://dl.acm.org/doi/10.1145/3517340#d1e3003

Brandt, H. E. (1999, November). Qubit devices and the issue of quantum decoherence. Science Direct. Retrieved May 20, 2024, from https://www.sciencedirect.com/science/article/pii/S0079672799000038

Brubaker, B. (2023, October 17). Thirty Years Later, a Speed Boost for Quantum Factoring. Quanta Magazine. Retrieved May 27, 2024, from https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/

Case, M. (n.d.). A Beginner’s Guide To The General Number Field Sieve. UMD Computer Science. Retrieved May 26, 2024, from https://www.cs.umd.edu/~gasarch/TOPICS/factoring/NFSmadeeasy.pdf

Goodreads. (2024). Quotes by Richard P. Feynman (Author of Surely You’re Joking, Mr. Feynman!). Goodreads. Retrieved May 27, 2024, from https://www.goodreads.com/author/quotes/1429989.Richard_P_Feynman

Harvey, S. P. (2024, March 5). Quantum Dots/Spin Qubits. Oxford University Press and The American Institute of Physics. Retrieved May 19, 2024, from https://oxfordre.com/physics/display/10.1093/acrefore/9780190871994.001.0001/acrefore-9780190871994-e-83

IBM. (2024). IBM Qiskit Docs. IBM Quantum Documentation. Retrieved May 26, 2024, from https://docs.quantum.ibm.com/

IonQ. (2024, March 14). Hello Many Worlds in Seven Quantum Languages. IonQ. Retrieved May 26, 2024, from https://ionq.com/docs/hello-many-worlds-seven-quantum-languages

Li, J., Peng, X., Du, J., & Suter, D. (2022, January 8). An Efficient Exact Quantum Algorithm for the Integer Square-free Decomposition Problem. Nature. Retrieved May 26, 2024, from https://www.nature.com/articles/srep00260

Microsoft. (n.d.). What is a Qubit? Microsoft Azure. Retrieved May 19, 2024, from https://azure.microsoft.com/en-us/resources/cloud-computing-dictionary/what-is-a-qubit

Microsoft. (2024). Azure Quantum | Single-qubit gates. Azure Quantum. Retrieved May 20, 2024, from https://quantum.microsoft.com/en-us/explore/concepts/single-qubit-gates

Microsoft Azure. (2024, January 12). Understanding quantum computing — Azure Quantum. Microsoft Learn. Retrieved May 20, 2024, from https://learn.microsoft.com/en-us/azure/quantum/overview-understanding-quantum-computing

Pavlidis, A., & Gizopoulos, D. (2022, July 19). Quantum Cryptography — Shor’s Algorithm Explained. Classiq. Retrieved May 27, 2024, from https://www.classiq.io/insights/shors-algorithm-explained

Quantum-Inspire by QuTech. (2024). Qubit basis states. Quantum Inspire. Retrieved May 20, 2024, from https://www.quantum-inspire.com/kbase/qubit-basis-states/

Rioux, F. (2023, January 10). 8.53: Bell State Exercises. Chemistry LibreTexts. Retrieved May 26, 2024, from https://chem.libretexts.org/Bookshelves/Physical_and_Theoretical_Chemistry_Textbook_Maps/Quantum_Tutorials_(Rioux)/08%3A_Quantum_Teleportation/8.53%3A_Bell_State_Exercises

Roy, S. G., & Chakrabarti, A. (2024, March 5). Toffoli Gate. Science Direct. Retrieved May 20, 2024, from https://www.sciencedirect.com/topics/computer-science/toffoli-gate

Wikipedia. (2024). General number field sieve. Wikipedia. Retrieved May 24, 2024, from https://en.wikipedia.org/wiki/General_number_field_sieve

Wikipedia. (2024, May 15). Quantum logic gate. Wikipedia. Retrieved May 19, 2024, from https://en.wikipedia.org/wiki/Quantum_logic_gate

Wikipedia. (n.d.). Bloch sphere. Wikipedia. Retrieved August 20, 2024, from https://en.wikipedia.org/wiki/Bloch_sphere