(Almost) everything you ever wanted to know about quantum computers
From Schrodinger’s Cat to finding a needle in a haystack
With the recent announcement of IBM Q System One — the first fully-integrated commercial quantum computer — by IBM at CES 2019, quantum computing is soon to enter mainstream computing. Housed in a nine-foot-tall, nine-foot-wide case of half-inch thick glass, it will still take years before these computers become small enough to be lying around in your bedroom.
Fortunately, you don’t need to buy one to start building and testing your own quantum algorithms. Other existing options are currently available, such as cloud based quantum computing systems and qiskit — a framework for writing and running quantum algorithms.
While IBM has certainly secured a footing in making quantum computers accessible to researchers around the globe, it is not alone. The other big players include D-Wave, Microsoft, and Google.
D-Wave was the first to sell hardware with quantum effects and recently launched D-Wave Leap — a software tool that provides real-time access to their D-Wave 2000 Q quantum computer.
Not long ago, Microsoft announced Quantum Development Kit as part of their existing Microsoft Azure services, hailed as full quantum stack.
And the Google AI Quantum team released Cirq — an open-source framework for simulating quantum circuits on Noisy Intermediate Scale Quantum (NISQ) architectures and OpenFermion — another open-source framework for converting problems from material science and chemistry into the ones that can be suitably run on quantum platforms.
With so many interesting activities cropping up, the topic of quantum computing is bound to pique the interest of even the most unconcerned soul.
In this article, I’m going to present the key axioms of quantum mechanics, explain what they mean and how to leverage them for speeding up a classical algorithm for searching in unordered data (finding a needle in a haystack). So regardless of whether you are simply looking for an overview of this field or just need a quick review of the subject, I hope you will find this article helpful in both regards.
While discussing various aspects of quantum mechanics, I will use some linear algebra, assuming you have a basic knowledge of it. If, however, you are unsure, need brushing up or just wanted to have a good visual feeling of the essentials of linear algebra, let me recommend this excellent series Essence of linear algebra on YouTube by 3Blue1Brown.
Below is a list of contents covered in this post:
Two-qubit Gates and Tensor Product
Non-reversible Operations & No-cloning Theorem
Finding a Needle in a Haystack
Without further ado, let’s just jump right into it.
Axioms of Quantum Mechanics
The three main axioms of quantum mechanics are as follows:
1. Superposition principle
2. Measurement
3. Unitary evolution
To understand these axioms, let’s consider the simplest case of a quantum system with only 2 possible configurations, a two-state quantum system. An electron with a spin either in up-spin (↑) or down-spin (↓) configuration describes such a system. Consider another example of 2-state quantum system, a hydrogen atom where the electron has two available states: ground and excited states, as illustrated in the image below:
The electron in the atom can transition from ground to excited state (or vice-versa) by absorbing (or emitting) a photon of light with an energy (hν) equal to the energy difference between the two states ΔE.
Let’s give these states some names: |0⟩ for ground state and |1⟩ for excited state; we will later decide how to express them mathematically. When the state of the electron is measured, e.g. by exposing the atom to a light source with energy hν < ΔE, if the electron is initially in ground or excited state, its state can be measured without any uncertainty (i.e. with probability p=1).
This is unfortunately (or rather fortunately) not a complete story. Due to the quantum effects, the electron does not quite stay in either one or the other state, and in fact can be present in both the states simultaneously in accordance with the first axiom of quantum mechanics: “superposition principle”. According to superposition principle, the actual quantum state of the electron |ψ⟩ can be written as a mixture of ground and excited states in the following way:
Where α and β are complex numbers (known as probability amplitudes) that give information about the probability of the electrons to be found in state |0⟩ or |1⟩ upon measurement. More specifically |α|² (the square of the modulus) or |β|² is the probability of the electron to be found in state |0⟩ or |1⟩, respectively. Since in a two-state system, only two states are available for the electron to occupy, hence the total probability |α|² + |β|² sums to 1.
In a classical sense, the probability |α|² or |β|² would indicate the chance that the electron was present in either state |0⟩ or |1⟩ even before it was measured. But this is where classical and quantum physics part ways.
Quantum mechanically speaking, such an uncertainty in the measurement result is intrinsic to the system. Before a measurement is performed, the electron is partly present in both the states at once, as determined by α and β. How do we distinguish between the classical case where the electron was in one of the states with certain probability and quantum case where electron true state was a superposition of both the available states? Is there some experiment that can differentiate the two cases?
Luckily the answer is Yes: double-slit experiment for electrons. The following diagram shows a setup of the experiment:
The double-slit experiment is typically carried out for light and other waves, which form an interference pattern at the projection screen. In the electron version of the double-slit experiment, an electron gun fires one electron at a time. The electron passes through the screen with two slits and finally marks a spot at the projection screen.
Once the experiment is carried out for sufficient duration, we start to see that spots on the projection screen begin to form a pattern, much like an interference pattern. Since we are firing electrons one at a time, the emergence of such a pattern cannot be explained unless we consider that the single electron passes through both the slits simultaneously in accordance with superposition principle and interferes with itself to produce such a pattern. But is there a way to detect if the electron indeed passes through both the slits together?
This brings us to the second axiom of quantum mechanics “measurement”. Before the measurement, the state of the electron remains in superposition, with, let’s say, equal chance of passing through either slit. The moment we try to find out which slit the electron actually passes through (e.g. using some light source), we give the electron enough kick that it loses its superposition and is detected only at one of the two slits. The interference pattern at projection screen also vanishes. In other words, the act of measurement forces the electron to lose its superposition and collapse into a definite state.
The quantum phenomenon of superposition is so counter-intuitive that it bewildered even Erwin Schrödinger himself who helped develop it.
The absurd nature of quantum mechanics prompted him to suggest a thought experiment, famously known as Schrödinger’s cat experiment, which presents a possibility of cat being alive and dead both at the same time. The figure below illustrates the situation of the experiment. A cat is trapped in a sealed box with an explosive that is triggered by a particle released by a radioactive material during its decay. The material has 50% chance of decaying in the next hour.
The radioactive decay itself is also a quantum process. After 1 hour, the radioactive material attains a superposition of two states |decay⟩ and |no decay⟩, with a 50–50 chance. In the case of a |decay⟩, the emitted particle would trigger the explosive, causing it to explode and kill the cat. In the other case where there was |no decay⟩, the explosive remains intact leaving the cat alive. Therefore, in this case, the fate of the cat gets linked or “entangled” with the superposition state of the decay of radioactive material.
If an observer opens the box (i.e. a measurement is made), the superposition quickly collapses and they see only one of the two possibilities: either there was an explosion and the cat is dead or there was no explosion and cat is still alive.
I’ll defer describing the third axiom to a later section on Quantum Gates.
Quantum Entanglement
We noticed in the above experiment that the state of the cat (alive or dead) becomes entangled with the state of the radioactive material (decay or no decay). The cat most certainly dies in the case of a radioactive decay or remains alive while there is no decay, without leaving room for other possibilities (such as the cat is still alive when there was a decay or cat is dead in the case of no decay). Therefore, we say that the state of the cat is entangled with the state of the radioactive material.
Since the radioactive material has 50% chance of decaying in the next hour, we can combine the states of radioactive material and the cat as: (1/√2)|no decay, alive⟩ + (1/√2)|decay, dead⟩. Since, we can immediately deduce the state of one system, say cat, by knowing the state of other, radioactive material, there is no way to separate out state of the cat from the state of the radioactive material. Such a joint state is famously known as the Bell state.
However, the notion of quantum entanglement goes much farther than this. Consider a pair of two-state quantum systems, each with states |0⟩ and |1⟩, forming a Bell state, i.e. (1/√2)|00⟩ + (1/√2)|11⟩. Here, the first and second digits in |⟩ refer to the state of first and second quantum system, respectively — similar to the joint state of radioactive material and cat in the above experiment. Each system has 50% chance of resulting in |0⟩ or |1⟩ upon measurement.
Now if we try to measure the state of any part of the system and find that it’s in |0⟩ state, the state of the other system also collapses to |0⟩, similar to how the state of the cat (alive or dead) depends upon the measurement outcome of the radioactive material.
But this is where it gets weird. Suppose we separate the two entangled systems thousands of light years apart. These systems continue to remain in entanglement. This is remarkable, because now if we measure the state of one system and find it to be in, let’s say |0⟩, the state of the other system thousands of light years apart also collapses to |0⟩ instantaneously, even though it would take light (the fastest thing in the universe) thousands of years to travel from one system to another.
This strangely intimate connection between the two systems led Einstein to remark: “Spooky action at a distance”, as he dismissed this idea. Since in his view nothing can move faster than the speed of light, in order to carry the information about the change in state of one system, the change in state of the other system would at least have to be delayed by the time it takes light to travel between them.
Since then, many experiments on such spatially distant Bell state pairs have been conducted, making an ever stronger appeal for quantum entanglement that outstrips even the speed of light. The idea of superposition and quantum entanglement are the key machinery behind quantum computers.
Quantum Bit (Qubit)
So far we have been referring to two states of systems with |0⟩ or |1⟩. However, if we want to carry out some operation on the system and predict the result of an operation, we need to come up with a mathematical model that suitably takes into account superposition and other aspects of a quantum system.
Let’s first consider a simpler case of a two-state “classical” system with two states |0⟩ and |1⟩. If we want to represent this system mathematically, we could simply use a scalar number b with two values {0,1} to represent the two states, as this system could only be in one state or another at any given time. As a result, a two-state classical system can encode one bit of information with each state representing one of the two bit values {0,1}.
Such a scalar number representation would not work for a two-state quantum system due to the superposition of states. Let’s instead focus on what we know about a two-state quantum system.
We know that it can take all sorts of intermediary values between |0⟩ and |1⟩ (let’s call them basis states). We can use this fact to represent the basis states as the two dimensions in a Cartesian system. Now if we want to represent a superposition state α|0⟩+ β|1⟩, it can be represented as a “vector” of unit length 1 (since |α|² + |β|² = 1) in the Cartesian system.
Bear in mind, however, that since α and β are complex numbers (with real and imaginary parts), they can only be drawn on a 2-D Cartesian plane, in the special case where the imaginary parts of α and β are zero. This case is plotted in the figure below:
Since a two-state quantum system encodes the whole spectrum of intermediate values between |0⟩ and |1⟩, it inherently contains more information than an equivalent two-system, where only one bit of information can be encoded (the states are mutually exclusive). Due to this fact, we use the term quantum bit or Qubit to represent a two-state quantum system.
Quantum Gates
In classical computing, the bits are manipulated by the operation of the logic gates. How do we manipulate the state of a qubit (two-state quantum system)? What kind of operation would we need to perform such manipulations?
The answer to these questions is encapsulated in the third axiom of quantum mechanics: unitary evolution. Consider the case where we used an atom with two energy levels, which represents a qubit. Also consider that initially the electron is in the ground state, i.e. the qubit is in a basis state given by |ψ⟩=|0⟩.
Suppose now we would like to carry out a “flip” operation to this state (an equivalent of a NOT gate). As we saw in our first figure, this can be achieved by using a photon with energy equal to ΔE (the energy difference between the two energy levels) to excite the electron in |1⟩ state. Similarly, if the electron is in an excited state to begin with, we can again use another photon to force the electron in the excited state to lose its photon and come down to the ground state (similar to the technique of “stimulated emission” employed in lasers).
Effectively, the process of firing a photon achieves our desired “flip” operation on a qubit. Mathematically, this operation can be expressed by a matrix-vector multiplication, as indicated below:
The matrix X represents a quantum bit flip or NOT gate. Notice that if we apply the bit flip operation twice, we get back to the original state. Also note that the two rows or columns of X are orthogonal (i.e. the dot product between the rows or columns is zero) to each other and each row and column is a unit vector.
These properties exist not by sheer fluke or accident. In fact, these are the direct result of the third axiom of quantum mechanics: unitary evolution. In simple words, it tells us that for a matrix, say U, to be a valid quantum mechanical operation, it needs to be a unitary matrix (equivalent of an orthogonal matrix but for complex numbers). That is, it must satisfy UU*=U*U=I, where U* is the conjugate transpose of U. In other words, U* is the inverse of U.
This is because whenever we are changing the state of a quantum system either by exposing it to a light source or by placing it in a magnetic field (if we are using electron spin to encode a qubit), the state of the system evolves in a manner which always remains consistent with a unitary transformation, and hence can be described by a unitary matrix.
In addition to bit flip operation X, below are the matrix representations of some other elementary quantum gates that form the clockwork of the quantum computers:
Observe that the operations constant-0 or constant-1 that always output 0 and 1, respectively, regardless of the input are not valid quantum operations, as their matrices are not unitary.
The implication of this fact are much more profound than they at first seem. Notice that all the valid quantum operations (X, Z, H) discussed thus far transform the input qubit such that original state of qubit can be fully recovered from the output state by again applying the same operation.
For instance, if we apply bit flip (or Z or H) operations twice, we get back to the same state we started from. Put differently, the information that was there in the input qubit remains preserved as it undergoes a unitary transformation via a quantum gate. Since the constant-0 or constant-1 operation destroys the information in original input qubit, such operations violate the fundamental “principle of conservation of information”.
Two-qubit Gates and Tensor Product
Before moving on to quantum gates with two or more input qubits, we first need to understand how to combine states of two qubits to form a joint state.
While covering the topic of quantum entanglement above, we briefly looked at a joint state representation of two qubits in entanglement. Now we will formalise this process for the two qubits whose states are independent of each other.
Consider, we are given two qubits: α₁|0⟩ + α₂|1⟩ and β₁|0⟩ + β₂|1⟩. Our goal is to form a joint state in terms of |00⟩, |01⟩, |10⟩, |11⟩. This is achieved by the tensor product ⨂, which is highlighted in the image below:
The above process looks cleaner in the vector form, performed in the following way:
Check that the joint state continues to be a unit vector with an important difference that now it lies in a 4-dimensional complex vector space. This joint state of two qubits is fed to a two-qubit quantum gate, which now would be a 4x4 unitary matrix (still satisfying the property UU*=U*U=I) to process a 4-dimensional input. The figure below indicates one of the most widely used quantum gates, controlled NOT (CNOT) gate, its representation and corresponding 4x4 matrix as:
Where ⨁ represents XOR operation. Basically what a CNOT does is that it flips the state of target qubit |b⟩ if the state of control qubit |a⟩ is |1⟩. Otherwise, if |a⟩ is |0⟩, it leaves |b⟩ as it is.
This is also evident from the matrix of a CNOT, which is a valid unitary matrix. Constructing such a 4x4 unitary matrix to represent an operation over two qubits should not be too hard. But what happens if we apply two single-qubit gates (say a bit flip on one qubit and a Hadamard to another) to each of the qubit? More specifically, how do we merge the two 2x2 matrices (e.g. for bit flip and Hadamard) to construct a 4x4 matrix?
The answer again lies with the tensor product — but now for the matrices. The following snap shows the tensor product for a general case of any two matrices and a specific case of X and H:
Convince yourself that X⨂H 󠄨≠ H⨂X, since X⨂H represents applying X to first qubit and H to second, while H⨂X represents the other way around. We can also construct the joint state from multiple qubits and form the corresponding matrix transformations by combining multiple smaller matrices, by repetitively applying the tensor product for vectors and matrices.
Creating Entangled States
The weirdness of entanglement allows us to do all sorts of crazy things, such as superdense coding and quantum teleportation. So it is worth pointing out how one can create their own entangled states.
While discussing the Schrodinger’s cat experiment, we realised how the state of the cat got linked to the radioactive material in the box, forming an entangled pair. How do we, in general, achieve such an entanglement between a pair of qubits? Fortunately, with our current understanding of quantum gates, we already have all the tools needed to build an entangled state.
Let’s look at the following diagram, where we start with both the qubits in basis|0⟩ state, and apply a Hadamard to one of the qubits that acts as a control for the other qubit in a CNOT gate. The Hadamard operation transforms the |0⟩ into an equal superposition, thereby forming a joint state with other qubit as (1/√2)|00⟩ + (1/√2)|10⟩, which is fed as the input to the CNOT. As we noted earlier, whenever a CNOT gate sees a |1⟩ at the control qubit it changes the target qubit. So the state of the target qubit in the second term of the joint state gets flipped, resulting in an entangled state.
Non-reversible Operations & No-cloning Theorem
We are coming closer to building more complex quantum circuits, akin to an array of logic gates in classical computers. However, before we move on, it is worth highlighting some crucial differences that exist between classical and quantum gates.
Unlike classical gates, which can, for instance, take two inputs and produce only one output (e.g. a 2x1 AND gate), quantum gates (unitary matrices) can only have the same number of outputs as the inputs. This is due to another aspect of unitary matrix constraints imposed upon valid quantum gates: unitary matrices have to be square matrices, i.e. having the equal number of rows (= number of outputs) and columns (= number of inputs).
Another key distinction is that quantum gates preserve information. Therefore, given the output at any step, we can reverse the steps of the computation to recover the state of the original input.
This prevents the quantum gates from implementing the operations that are non-reversible, e.g. constant-0 or constant-1. However, various scenarios could arise, where we would like the output to be some constant regardless of the input. How do we go about implementing such non-reversible functions then?
The trick is to keep some spare qubits at the input and output to divert unnecessary information at those spare qubits. The figure below illustrates the example for realising constant-1 and constant-0 gates that use one spare qubit:
Another difference between classical and quantum computing is that a superposition state of a qubit cannot be copied. I am not saying that no one has figured out how to do it yet — rather that it has been proven mathematically that replicating a quantum state is not allowed.
This fact is so fundamental that it has a name of its own: No-cloning theorem. It’s just like the case for realising non-reversible operations above, where we are not allowed to destroy information due to the principle of conservation of information. No-cloning theorem is also a direct result of this principle, since replicating a superposition state implies generation of additional information (or creating an exact copy of human or soul?).
Finding a Needle in a Haystack
Having gleaned the required knowledge and armaments straight from the heart of quantum mechanics, we are finally ready to see how we can utilise this power of quantumness to boost a search algorithm beyond what is currently imaginable with classical computing.
Consider we are given a function f(x) that takes an n-bit number x as the input and returns a 1 if and only x = xᵤ, else it results in 0. Our goal is to find this xᵤ. Classically we will have to feed each of the possible N = 2ⁿ (since a bit can take only two possible values) numbers to find out xᵤ. Hence, a classical search will take a maximum of N (big-O complexity = O(2ⁿ)) operations to find out xᵤ, which becomes a task of finding a needle in the haystack as N gets larger.
Let’s analyse a quantum algorithm, Grover’s search algorithm, to tackle this problem. This approach holds the potential to find xᵤ in about √N operations (i.e. with a complexity of O(√2ⁿ)), a quadratic speed-up over a classical algorithm.
The first step in implementing this algorithm is to realise that we can start with n qubits and form a joint state such that it is a uniform superposition over all the N values. To form such a superposition, we start with all the n qubits in |0⟩ state and apply a Hadamard gate to each qubit as shown in the figure below:
Next, this algorithm repeatedly performs two steps: 1) phase inversion and 2) inversion about the mean.
In the first step, the sign of the state |xᵤ⟩ where f(xᵤ)=1 is inverted while the sign of the rest of the states remains unchanged. In the second step, we take the mean of all the coefficients αᵢ and perform an inversion about the mean (μ -(αᵢ -μ) = 2μ - αᵢ). The following image summarises these two operations:
As seen above, the first step applies a phase factor to all the amplitudes, thereby flipping the amplitude αᵤ only for the state |xᵤ⟩, where f(xᵤ) =1. The second step simply transforms all the amplitudes αᵢ by μ -(αᵢ -μ) = 2μ -αᵢ.
After a single iteration of the two steps, the amplitude of the desired state |xᵤ⟩ increases from 1/√N to ≈3/√N (assuming N is very large), achieving a gain of 2/√N, which is twice the initial magnitude of αᵢ. After every subsequent iteration, the amplitude of the state |xᵤ⟩, αᵤ, keeps on rising while the amplitudes of remaining αᵢ keep on shrinking.
To find out how many steps it would take for the algorithm to find xᵤ, let’s get a bit more technical. Suppose, we just need to run the algorithm until the probability of finding xᵤ becomes ½. This corresponds to αᵤ=1/√2 and rest of αᵢ=1/√(2N), implying that αᵢ remains greater than 1/√2N for the entire run of the algorithm. This is because after each iteration, the gain in αᵤ remains greater than twice the minimum value of αᵢ(= 1/√2N), resulting in a minimum value for the gain in αᵤ as 2/√(2N) or √(2/N).
So to achieve αᵤ=1/√2, we need to run the algorithm by (1/√2)/ √(2/N)= √N number of times. Thus, Grover’s algorithm finds xᵤ with just √N number of steps, achieving a quadratic speed-up over a classical search.
Let’s now discuss how to implement these steps with quantum gates. We will start by implementing the function f(x), an n-to-1 function, as it takes n bits as input and produces a single bit as output. As we discussed earlier, all the quantum operations need to have the same number of inputs and outputs. So in order to implement f(x) with quantum gates we would need to use n+1 qubits: n qubits to represent the n-bit number x, and 1 qubit for storing the outcome of f(x), as shown below:
In the above diagram, if |b⟩ = |0⟩, the output of this qubit is simply |f(x)⟩. Next, we need to implement the phase inversion operation, which is actually much simpler than you might imagine. To implement phase inversion, all we need to do is to replace |b⟩ in above diagram by a |–⟩ = (|0⟩ — |1⟩)/√2, as explained in the following image:
As shown in the last row of the table above, feeding a |–⟩ results in the desired phase factor that we would like to attach to |x⟩. However, notice that the joint state at the output already has that phase factor associated with both |x⟩ and |–⟩. Hence, it does not really matter whether we attach the phase factor with |x⟩ or with |–⟩.
The next step is to convert the operation of inversion about the mean (2μ – αᵢ) into a valid quantum operation. Let’s build a unitary matrix that carries out 2μ – αᵢ. This is also quite straightforward, as outlined in the following figure:
Finally, the following image sketches out the Grover’s algorithms that will produce the desired xᵤ with a probability of ½ after √N number of runs.
Final Note
We have come a long way, starting from the basics of quantum mechanics to implementing a full-fledged quantum algorithm — Grover’s search algorithm — that demonstrates a quadratic speedup over classical algorithms.
Even though we have gone through some interesting topics in this post, the quantum world is replete with many more fascinating topics, such as Quantum teleportation, breaking RSA cryptosystem, quantum cryptography, or bringing quantum computers from theory to practice…and so on.
I will continue to write on such topics, so follow along if you’re interested or leave me a suggestion. Lastly, support this work by giving me a clap and share this post with those who are interested.
