Quantum Computing for Complete Beginners | by Angjelin Hila | Oct, 2023

Some have described the last several millennia of human dominion over the earth’s resources as the anthropocene, deriving from the Greek “anthropo” meaning human, and “cene” meaning recent. The last century in particular has been dubbed the fourth industrial revolution, due to the pace of technological innovation ushered in by the advent of computers in the middle of the 20th century.

In the past seventy years, computation has transformed every aspect of society, enabling efficient production at an accelerated rate, displacing human labour from chiefly production to services, and exponentially augmenting information storage, generation, and transmission through telecommunications.

How did we get here? Fundamentally, technological advancement draws on existing science. Without an understanding of the nature of electromagnetism and the structure of atoms, we wouldn’t have electricity and the integrated circuitry that power computers. It was only a matter of time, then, before we thought of exploiting the most accurate, fundamental description of physical reality provided by quantum mechanics for computation.

I became interested in quantum computation through both a strong interest in physics and the nature of computation. If successful, quantum computation could usher in an unprecedented chapter in our information age by exponentially augmenting the efficiency of current computers. As someone interested in data, computation, and information science, understanding the rudiments of quantum information will not only equip you with a very basic understanding of quantum physics but also prepare you for the next major technological frontier of our information age.

Quantum Phenomena & Quantum Information

In order to understand the basics of computing, it is necessary to have a basic understanding of the physical phenomena that quantum computing exploits.

The phenomena in question are electron spin and light polarization, the latter being another term for photon spin. Recall that electrons are negatively charged subatomic particles that surround a positively charged nucleus, whereas photons are the particle equivalents of electromagnetism or light. Electron and photon spin are connected since they both refer to quantum properties that have no analogue in classical mechanics, which describes the scale of everyday objects.

Nonetheless, the easiest way to introduce spin is to draw a comparison to a classical property called angular momentum. Angular momentum refers to the rotational equivalent of linear momentum in a classical system, where momentum is calculated as the product of mass and velocity. As such, momentum is a vector quantity since it possesses both magnitude and direction. Angular momentum is represented as the cross product of the position and momentum vectors of a particle. Since angular momentum is a classical property, it admits of continuous values and can be expressed as a volume integral (generalized from the integral as the area under the curve in two dimensions).

Spin is often defined as intrinsic angular momentum. Recall that in classical mechanics force is defined as change in momentum. Furthermore the energy of the system is defined in terms of motion or the rate of change of motion, which presupposes mass. Unlike classical mechanics, Einstein’s special theory of relativity ascribes intrinsic energy to rest mass through the equality E = mc². Similarly, intrinsic angular momentum is intimately bound up with the intrinsic energy state of a subatomic particle. In fact, it is a property that elementary particles possess whether or not they are actually rotating, that is, regardless of extrinsic factors like momentum and position, hence the qualifier intrinsic. Like classical angular momentum, quantum spin changes under rotations. However, unlike classical angular momentum, spin is quantized, which means that it only admits a discrete set of values.

The maximum spin of an elementary particle is given by the product of n (any integer of half integer n/2 values) and the reduced Planck’s constant ℏ (h/2????) . All ordinary particles, called fermions, have half-integer (1/2) spin, whereas force-carrier particles, known as bosons, like the photon have integer (1) spin. Both electrons and photons have two possible spin states: spin “up” or “down”. In mathematical terms, electrons will have a maximum spin of 1/2ℏ or -1/2ℏ, namely spin in the positive or negative “rotations”. The photon will have maximum spin of 1ℏ and -1ℏ, since it takes integer spin values. Even though we’re using the word “rotation”, it is best not think of it in terms of spatial transformations.

Now let’s look at the strange quantum properties that will be exploited for quantum computation. We noted earlier that the electron can have two possible spin states, but which state is it in at any given moment? This is where it is useful to draw a distinction between the state of the system and measurement. In classical mechanics, state and measurement coincide perfectly: the state of the system is what you measure. Not in quantum mechanics. The state of the system without measurement is given by a coherent superposition of wave functions ????i . After measurement, the state of the system will be given by either ????↓ or ????↑, if we’re measuring a single particle. This disjunction between state and measurement enables quantum computers to carry out operations that can take infinite values in two dimensional complex vector spaces.

Finally, measurements obey certain rules relative to the way the measurement is carried out. Specifically, the direction of measurement matters for the outcome. Let’s say we have two directions: vertical and horizontal. If we measure the spin of an electron in the vertical direction, we will get a state of spin up or down. If we carry out the exact same measurement, that is, measure spin again in the vertical direction, we will get the same outcome. This shows that there’s an experimental setup that yields predictable outcomes. However, if we first measure the spin of the electron in the vertical direction and subsequently in the horizontal and keep repeating the measurement, the outcomes will be a random sequence of spin up or down that distribute uniformly between the two with enough trials. This means that if we’re not careful, quantum measurements can produce random outcomes. The purpose of quantum algorithms will be to control the operations so that we get the outcomes we desire.

Even though qubits, the informational units of quantum computing, can be represented either by electron or photon spin, we will use the former as the physical analogue of quantum computation going forward.

From Quantum Phenomena to Quantum Computation

The fundamental informational unit of a classical computer is a called a bit, which has two discrete states often represented as 0 or 1. Since the computer is a physical machine, this mathematical abstraction must be mapped to some physical phenomenon. Classical computers map these discrete states on a flowing current or voltage. When the voltage is low or close to none, we use it to represent state 0 and when the voltage is higher, we use it to represent 1. In other words, modulations of voltage magnitudes allow us to mechanistically realize a binary system of representation. Sequences of these low-voltage and high-voltage states are subsequently arranged into electrical circuits that simulate logical operations like AND, XOR etc called logic gates. Combinations of logical operations through electrical circuitry are subsequently scaffolded to execute any computable algorithm.

Now that we see that classical computers leverage electricity to realize computations, it helps us to understand how a quantum computer might operate. Unlike a classical computer, a quantum computer leverages quantum or subatomic scale phenomena to carry out computations. While voltage in our everyday macro scale is measured as a continuous variable, quantum mechanics tells us that at the subatomic scale this is not really the case. Rather, by all experimental accounts, subatomic particles appear to occupy only discrete energy states. This means that an electron and a photon can occupy some energy states, and not others. This contravenes our intuitions about physical objects being able to occupy any continuous energy state. For example, while we typically think of time as a purely continuous variable that’s infinitely divisible, this is starkly not the case for the energy states of subatomic particles.

This has the peculiar consequence that subatomic particles cannot be described as having fixed positions and momenta. While we can try to describe these variables simultaneously, there’s a physical scale in which the precision breaks down such that knowing the momentum means losing track of the position and vice versa. That physical scale is the called the Planck scale denoted by h: 6.626070 · 10⁻³⁴ m²kg/s and represents the physical threshold between classical and quantum scale phenomena. At this scale, again by all experimental evidence, subatomic particles occupy all their possible states simultaneously. Because of this property, we can only describe subatomic particles as probability distributions of all their possible states as described by Schrödinger’s equation. As we pointed out earlier however, there’s a second description called a measurement. Prior to measurement, the particle exists in a state of superposition as described by Schrödinger’s wave function. After measurement, the particle collapses to a discrete state of one position or another. Quantum computing leverages this peculiar property of quantum mechanics to perform computations, that is, by taking advantage of both superposition and measurement states. (If you want to get clear on the experimental basis of the objectivity of the superposition read this).

So if a classical computer builds computations from two possible discrete states, we can think of a quantum computer as building computations from discrete states as well as superpositions. A qubit can be in state 0 or 1 when we measure it. However, prior to measurement, the qubit is in a superposition of 0 and 1. During superposition, the qubit can occupy an infinite amount of states. By leveraging the laws of quantum mechanics, quantum computation surpasses the computational capacities of classical computation whose state space is confined to 2^n. To be sure, measurement reduces quantum states to classical states, namely, the same state space of 2^n. In what way then does quantum computing confer advantages that elude classical computing?

As we will see below, quantum algorithms enable controlled operations in the state of superposition that allow us to get useful answers after measurement. Computer scientists define the complexity of an algorithm with respect to the time steps required to solve it. If n denotes the input length of the algorithm and T(n) the time to solve it, then complexity refers to the function that describes the growth of T(n). If T(n) amounts to a polynomial, then the algorithm is said to belong to a polynomial-time class problem. If T(n) amounts to an exponential function, then it belongs to an exponential-time class problem. Those that belong to exponential time, like the prime factorization of large numbers, are intractable for classical computers since the time required to solve the problem increases exponentially and can easily exceed human-scale time constraints.

The promise of quantum computing lies partly in being able to solve exponential-time problems sufficiently quickly.

Representing Qubits: Linear Algebra

In order to understand quantum computing, we have to understand some of the math underlying the representation of qubits. The mathematical tools need to correspond to the underlying phenomena upon which we will map computation, primarily linear algebra.

We represent Qubits with two-dimensional unit vectors.

What is a vector?

A vector is a quantity that is expressed by at least two values: a magnitude and a direction. A vector’s magnitude is given by the Euclidean distance, whereas the direction is given by the starting point. (1,-3) for example represents a two dimensional vector, with a length of 3.162 and a direction given by the x value.

What is a unit vector?

A unit vector is a vector with length or magnitude equal to 1. For example <0,1> is a unit vector because if we calculate the Euclidean distance using the Pythagorean Theorem we get the value 1.

Why two-dimensional unit vectors?

Since there are two possible electron spin measurement outcomes, a two dimensional vector space denoted by ℝ² will do. We use unit vectors because we want to limit measurement outcomes to two possible values: 0 or 1. As we will see, the operations we will perform on qubits will amount to rotations on a unitary plane. However, the space of possible outcomes should include all possible rotations on a three dimensional sphere whose underlying space is still two dimensional, denoting the two possible measurement outcomes. To do this we represent vectors as complex numbers rather than as real numbers, denoted by the complex vector space ℂ². (Complex numbers are any operations involving real numbers and imaginary numbers, where an imaginary number i is equal to √-1) For simplicity’s sake, we will for now stick to ℝ² and eschew complex numbers.

In order to limit outcomes to two possible values, we need more than just unit vectors. We need pairs of unit vectors to be orthogonal to each other. Two vectors are orthogonal to each other if and only if their inner or dot product equals to zero. When combinations of unit vectors are orthogonal to each other, we call those orthonormal bases, combining the word normal that stands for unit vectors and orthogonal.

Orthogonality: Two vectors are orthogonal if and only if their product equals zero : <a|b> = 0.

We can check that any n-dimension ket is an orthonormal basis if the product of the matrix A and its transposal A^T equals an identity matrix In.

Bracket Notation

Before we describe these bases, let’s say a few words about the standard notation used in linear algebra so that you you’re able to interpret symbols appropriately.

Column vectors are called bras, whereas row vectors are called kets denoted as follows: <a| & |b>, where:

Together, they form bra-kets. From the dot product rule (i.e. vector multiplication), we can only multiply bras with kets provided that each have equal dimensionality.

The inner product of the bra-ket above is represented by <a|b> and denotes:

However, vectors of the same type (bra or ket) of the same dimension can be summed.

Instead of using actual values, we can use arrows to represent the types of orthonormal pairs relevant for electron spin measurement.

There are three orthonormal bases for spin:

When we multiply bras and kets of the same spin, we yield a value of 1:

Conversely, when we multiply bras and kets of opposite spins, we yield a value of 0:

As you can see, orthonormal bracket products give us measurements that simulate binary outcomes.

The first basis, represented by the up and down arrows, is called the standard basis and corresponds to vertical measurement of spin, that is, measurement along the y-axis. The second basis, represented by the right and left arrows corresponds to the horizontal measurement of spin, namely measurement along the x-axis. Generally, ordered orthonormal bases represent the measurement of spin along a certain direction. In fact we can measure spin at any angle or direction ???? and the output will collapse to a discrete outcome of spin up or down in that direction, since spin states can only be discrete.

A quantum state of a single or multiple qubits will be given by a linear combination of these bases. The basis vectors, therefore, will represent the possible outcomes of a quantum state. As we said earlier, the state of a qubit can be modelled on the spin of an electron or photon. Prior to measurement, the particle or the quantum state will be in superposition, represented by a linear combination of the bases |b1> and |b2> that takes the form of c1|b1> + c2|b2> , where c1 and c2 represent probability amplitudes. Because the probability amplitudes can be negative, only their squared values are used to represent the probabilities of the outcomes where c1² + c2² = 1. In a superposition, therefore, c1² and c2² will each have a probability of 0.5.

After measurement, the spin state collapses to one of the orthonormal bases |b1> or |b2>. The probability of collapsing to |b1> is given by c1², while the probability of collapsing to |b2> is given by c2². If the measurement collapses to |b1>, c1² will equal 1 and c2² 0 and vice versa. To put it even more bluntly, the basis vector multiplied with probability value 1 will represent the outcome of the measurement.

In classical computing, multiple bits are represented by the tensor product of those bits, denoted by the following symbol: ⊗

We said that [1,0] and [0,1] kets represent the standard bases, and therefore constitute analogues of 0 and 1 respectively in classical bits. We also said that any quantum state must conserve the following equality: c1² + c2² = 1. We called it the unit measure constraint (the second axiom of probability theory), which means that all kets must be unit vectors in ℝ². However, since actual quantum particle states are represented via complex numbers, the actual state space is given by ℂ². Therefore, the actual unit measure constraint is given by: ‖????‖² + ‖β‖² = 1, where ???? and β are complex numbers and represent probability amplitudes.

To represent multiple qubit states we therefore take the tensor product of our standard bases |0> and |1>. Notice that the product will conserve the unit measure constraint, regardless of how many qubits we concatenate.

Since we’ve been working in ℝ², we can heuristically represent the state space of a qubit in two dimensions (x,y) via a unit circle. Remember that all operations will be on the orthonormal bases we enumerated above. Furthermore, all quantum logic gates will be represented by unitary and thereby orthogonal matrices. Why? Because vector multiplication by an orthogonal matrices produces rotations by preserving the inner product of vectors. This produces isometric transformations on a Euclidean space.

Notice, also, the negative signs for every 180⁰ rotations. The negative signs help distinguish equivalent outputs such that every operation can in principle be invertible or reversible. All quantum computations will need to be reversible to leverage the computational capacities of quantum states, namely the states of superposition and entanglement prior to measurement. As we will see later, the state of superposition (as well as entanglement) endows quantum computing with advantages that elude classical computing. In the state of superposition, any arbitrary number of qubits N occupy all of their possible states at once. If we have 4 qubits, the sample will have 2⁴ possible states, but in superposition all these states will obtain simultaneously. The probability of collapsing to one of these states upon measurement will be distributed equally along the linear combination of the unit vectors.

The lines in the unit circle below represent the state changes from input to output via operations with the Hadamard gate, which puts qubits into superposition and back. Due to the following equality ‖????‖² + ‖β‖² = 1, measurement will always collapse the system into a distinct classical state, which in our case map to electron or photon spin. Operations with quantum gates however change the state of a single or multiple qubits without collapsing the wave function.

If we apply the bit-flip operator, equivalent to the NOT gate in classical computing, it will invert the value of the input state. For example, the |1> ket will flip to the |0> ket indicated below by the state transition from (0,1) to (1,0).

The Hadamard gate, meanwhile, takes (0,1) as input and outputs (1/√2,−1/√2) by multiplying the input with the following orthogonal or unitary matrix:

In case you’re wondering exactly how the state changes, here’s an explicit illustration of matrix multiplication with the Hadamard gate from |1> input:

How does the Hadamard gate work and what is so special about it?

Notice by looking at the unit circle that the bit-flip operation corresponds to a 90⁰ rotation on the unit circle, meanwhile the Hadamard gate corresponds to 180⁰ rotation. What you need to keep in mind is that all quantum gates are done via orthogonal or unitary matrixes, which produce rotations along the origin. The Hadamard gate, specifically, produces half-rotations between the x and y axes, which correspond to probability amplitudes of 0.5.

Notice also that the vector output is a unit vector since (1/√2, −1/√2) observes the following identity ‖????‖² + ‖β‖² = 1. Try to do the calculation yourself by plugging in the output values in place of ???? and β.

Think of the state of the qubit at some point in the unit circle as distributing the probability amplitudes from analogues of 0 and 1 to some set of values in between that conserve the unit sum. The Hadamard gate sets that distribution exactly to a 50/50 outcome. In other words, there’s a 50/50 chance that measurement will collapse the qbit to |0> or |1> state vectors. This is the mathematical analogue to a state of superposition. We will see later how superposition can be leveraged computationally.

Finally, our demonstrations thus far have utilized the unit circle as the space of possible states of a qubit in ℝ². Since actual qbit states are represented by complex numbers in ℂ², a more accurate representation of the qubit state space is given by what’s called a block sphere, which aims to capture the possible states of complex valued numbers shown below as a three-dimensional sphere.

Quantum Logic Gates

Much like traditional computing, logic gates in quantum computing consist of circuits that perform some operation on a qubit or sets of qubits. Earlier we saw that quantum gates mathematically amount to matrix multiplications on qubits. We also said that qubits are represented by unit vectors, whereas quantum logic gates by orthogonal or unitary matrices. As we saw, these produce rotations on a unit sphere, or circle, to reduce the complex space to a two-dimensional one for the sake of simplification.

However, to perform operations on qubits, quantum gates must be reversible. Reversibility means that every operation from input to output must also be revertible from output to input. The reason for this is that quantum states are reversible, time-reversal invariant, and conserve information in the state of superposition. What we termed measurement, however, reduces the quantum state into a classical one. Measurement or collapse is irreversible and does not thereby conserve input information. In other words, we cannot revert the collapse into its preceding superpositioned state. As such, quantum gates constitute controlled operations that manipulate the quantum state while also conserving it. The circuitry necessary for these outcomes leverages semiconductor particles a few nanometers in size called quantum dots that have to be kept temperatures close to zero Kelvin. However, it is crucial to note that the desired outputs of quantum computation can only be retrieved through measurement.

There are, therefore, two properties that matter the most when it comes to quantum logic gates: a) reversibility and b) universality. Universality refers to a type of logic gate that can compute all possible operations on bits. The most well known universal gate in classical computing is NAND (NOT AND) represented by the table below:

Note that NAND is the truth-functional complement to AND. At most, only two logical operators suffice to express all possible logical statements including the theorems of logic. This is known as functional completeness. Since NAND combines both NOT & AND into one operation, by corollary it qualifies as a functionally complete and thereby universal logical operator and gate. For comparison’s sake, let’s look at the truth table for AND:

In classical computing, most operations are irreversible. For example, if we input a sequence 010011110 into most logic gates and get another binary sequence as output, we would not be able to retrieve the input sequence from the output sequence alone. XOR and NAND are both irreversible. However, there are some gates that allow us to retrieve the input from the output alone, like the CNOT (equivalent to XOR but reversible), Hadamard and TOFFOLI gates. Among these, the Hadamard and TOFFOLI qualify as both reversible and universal. However, there are other gates that meet these qualifications like the FRIEDKIN gate. We will focus on the former triad.

Let us now take a look at two gates essential for most quantum computations: CNOT & Hadamard. The CNOT operates on two or more qubits by entangling them. The Hadamard gate operates on one or more qubits by putting them into superposition. We will also look at a third gate, the TOFFOLI gate, also known as the controlled-controlled NOT gate, which is a universal version of the CNOT gate.

What is the purpose of the CNOT gate? It allows us to entangle two input qubits by performing bit-flip operations that are reversible. The CNOT gate consists of two inputs: a control and a target input. When the control bit equals 1 the CNOT gate flips the target input. When the control bit equals 0, the CNOT gate does nothing. This way, every output combination can be traced back to one and only one input combination.

In what sense is the CNOT gate equivalent to entanglement?

Let’s take a look at an operation by the CNOT gate on |1> and |0> qubits. We take the tensor product of the two qubits and multiply it with the CNOT gate unitary matrix, which converts the input tensor product from |10> to |11>. Why? Because CNOT flips the value of the target qubit if and only if the control qubit equals |1>.

By corollary, if our target qubit is |1> instead of |0>, the CNOT gate predictably flips the value back to |0> as we see below:

In other words, CNOT is the reversible classic-computational equivalent of the XOR (exclusive OR).

As we mentioned earlier, the Hadamard gate yields a perfect superposition. How does it do that? Take a look at the orthogonal matrix below:

If we multiply the matrix with a standard base |0>, then it outputs the following state: (1/√2, 1/√2) which is equivalent to (|0>+|1>)/√2. Conversely, if we multiply it with |1>, we get (1/√2,−1/√2), which is equivalent to (|0>−|1>)/√2. Even though each input converts the output to an equal distribution of probability amplitudes, the negative sign allows us to distinguish the input (whether it is |0> or |1>) and thereby ensures the operation is reversible.

Each value has a 50/50 chance of outcome in the classical world. Notice that in our example we carried out the operation on a single qubit. How do we put multiple qubits on superposition?

We we need to pass each qubit separately through a Hadamard gate, then take their tensor product. As we noted earlier, multiple qubit states are represented as tensor products of single qubit states.

Below you can see the operation on a single qubit by multiplying the |1> standard base with the Hadamard matrix:

Finally, let’s take a look at the TOFFOLI gate, also known as the controlled-controlled-not (CCNOT) gate. The TOFFOLI gate is identical to the CNOT save for having an additional control variable. With two control variables, the TOFFOLI gate utilizes an 8×8 orthogonal matrix for operations on three input qubits. Like CNOT, TOFFOLI produces quantum entanglement, and can be used to entangle and disentangle qubits.

The TOFFOLI gate input-output tables:

Why do we need the TOFFOLI gate when we have CNOT?

Because like NAND, TOFFOLI is universal for classical computation and can thereby be used by a quantum computer to simulate reversible classical computations. TOFFOLI is however not quantum computationally universal since it cannot produce superpositions.

Now that we have some handle on quantum logic gates and the operations that they perform, how do we combine them to get quantum algorithms?

Since quantum gates preserve the state of superposition, we can use them to perform unitary computations that are reversible. Physically speaking, the evolution of the system in time is described by Schrödinger’s wave function. To retrieve any information from the quantum computer, however, we need to collapse the wave function.

Typically, we combine operations of bit-flips and Hadamard gates to get desired outcomes. However, bit-flips are non-reversible. The challenge of quantum computing lies in devising ways to write non-reversible functions in a reversible way. We will see how to do this with the Deutsch algorithm.

Classical bits are special cases of qbits

In principle, a quantum computer can instantiate all classical computations as these are a proper subset of quantum computations.

In order to realize classical computations through a quantum computer, we must limit computations to qubits expressed by normal bases (as analogs to classical bits) we’ve been using as examples all along and design circuitry that utilize classically universal reversible gates like the TOFFOLI gate. Since the TOFFOLI gate is a universal gate for classical computation, it can be used to instantiate classical computations.

However, we haven’t said anything thus far about quantum algorithms. Just how would be go about constructing one?

Quantum Algorithms: The Deutsch Oracle

Everything we’ve explicated thus far would be frivolous from a computational standpoint if we could not construct quantum algorithms that confer computational advantages over classical algorithms.

The first algorithm that demonstrably achieved this was devised by David Deutsch in 1985, known as Deutsch’s Oracle.

Suppose you have four functions f₀-f₃. For every input 0 or 1, f₀ outputs 0. For every input of 0 or 1, f₁ outputs 0 if the input is 0 and 1 if the input is 1. For every input of 0 or 1, f₂ outputs 1 if the input is 0 and 0 if the input is 1. For every input of 0 or 1, f₃ outputs outputs 1.

We can call functions f₀ and f₃ constants, since they produce the same output regardless of the input. And we call the functions f₁-f₂ balanced, since they distribute the outputs in a reciprocal way.

The question we then ask is: if we’re given one of these functions at random, how many times should we query the algorithm to determine whether the function is a constant or balanced?

The answer is that classical computation cannot determine the right answer in less than two queries. Let’s see how this works. We have the choice of 0 or 1 as input. If we input 0, we could get 0 or 1 as output. Likewise, if input 1, we could get 0 or 1 as output. In both cases, we won’t know whether the output was produced by a constant or balanced function. We therefore have to query the algorithm a second time to make the correct determination.

With a quantum algorithm, Deutsch demonstrated, we can know the correct answer with a single query. In order to achieve this, we make use of the Hadamard gate and a control qubit in addition to the input qubit. We send our inputs through the Hadamard gate. Remember that H puts a qubit in a state of superposition. So if we input the pair |0> and |1>, we get the following respective states: (1/√2, 1/√2) , (1/√2, −1/√2). We then pass the target gate through random fₓ.

Since Hadamard is reversible, fₓ should put our qubit in one of the following states:

(1/√2) (|0>+|1>); (1/√2) (|0>−|1>); (−1/√2) (|0>−|1>); (−1/√2) (|0>+|1>)

We pass the control qubit through the Hadamard again in order to reverse the superposition. Since the operations are reversible, we get the following possible outcomes:

f₀ →|0>; f₁ →|1>; f₂ → −|1>; f₃ →−|0>

This means that when we measure the qubit at the very end, if the output is |0> the function is a constant, and if the output is |1>, the function is balanced. Even though the Deutsch Oracle has no practical uses, it provides a powerful example of the advantages of quantum over classical computing.

Deutsch-Jozsa Algorithm

The Deutsch Oracle generalized to multiple variables is called the Deutsch-Jozsa algorithm. The diagram below provides the schematic quantum circuitry of the algorithm.

Shor’s Algorithm

Shor’s algorithm is a quantum algorithm used for factoring large numbers. The algorithm consists of two parts, the first of which is executed in a classical computer, and the second executed in a quantum one that makes use of the quantum Fourier Transform. We will not delve into the mathematical details of this algorithm as they’re complex and therefore beyond the scope of this article.

Shor’s algorithm requires two registers with 1024 and 2048 qubits respectively in order to factor a 1024 bit number with 309 digits. The largest number that has been factored to date has a length of 48 bits, which falls short of the RSA 100 digit semiprime milestone. So far no quantum computer has met any of the RSA number challenges, which consists of a list of identified large numbers that have only two prime factors. RSA numbers are used in public-key cryptography for secure data transmission by governments and financial institutions.

With a sufficiently powerful quantum computer, Shor’s algorithm can be used to decode public-key cryptography, which uses very large primes deemed computationally intractable by classical computers.

Quantum Supremacy & The Future

As we said at the outset, the notion of quantum supremacy refers to the ability of quantum computers to solve classically intractable problems in a reasonable time-frame. In principle, classical computers can solve any theoretically computable algorithm. The problem lies with praxis: limited processing power precludes them from solving certain problems in a useful timeframe. This is where quantum computers promise to bridge the gap. In 2019, Google announced that they had achieved quantum supremacy with their Sycamore, a 53 qubit quantum computer. In their Nature paper titled Quantum Supremacy Using a Programmable Superconducting Processor they claim that Sycamore took 200 seconds to sample one instance of a quantum circuit a million times, a task which, they further claimed, would take a classical supercomputer 10000 years. IBM countered the latter claim by averring that one of their supercomputers could perform that task in 2.5 days, undercutting Google’s claim to the finish line.

The largest quantum computer to date, IBM’s Osprey, sports a 433 qubit processor. Current attempts to build quantum computers with sufficiently large processors are beleaguered by creeping noise, namely the potential of the quantum state to decohere or collapse into a classical state through interaction with its surrounding environment such as changes in temperature and magnetic fields.

The noise-problem constitutes one of the key challenges of scaling quantum computers to the computational potential such as factoring inordinately large primes. Noise-cancelling qubits could offset some of these challenges, but currently the advent of quantum computing is still in its infancy.

References

Bernhardt, Chris. Quantum Computing for Everyone. The MIT Press, 2020.

IBM unveils 400 qubit-plus quantum processor and next-generation IBM Quantum System Two. IBM Newsroom. (n.d.). https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two

Kaye, P., Laflamme, R., & Mosca, M. (2020). An introduction to quantum computing. Oxford University Press.

“Noise-cancelling” qubits can minimize errors in quantum computers. University of Chicago News. (n.d.). https://news.uchicago.edu/story/noise-cancelling-qubits-can-minimize-errors-quantum-computers#:~:text=As%20existing%20quantum%20computers%20are,to%20high%20rates%20of%20error.

Roush, W. (2020, July 13). The google-IBM “Quantum Supremacy” feud. MIT Technology Review. https://www.technologyreview.com/2020/02/26/905777/google-ibm-quantum-supremacy-computing-feud/

Zubairy, Muhammad Suhail. Quantum Mechanics for Beginners: With Applications to Quantum Communication and Quantum Computing. Oxford University Press, 2020.