Quantum computing is the area where quantum physics meets basic computing. And not where you use computing to define or understand quantum physics, but where you use quantum physics to do computing.
The classical computer boils down to computations made using bits. Bits can have a value of TRUE or FALSE (1 or 0). The CPUs of computers execute instructions based on combined sets of bits (bytes). But nobody actually writes this “machine code” - there is another set of instructions that will assemble these bytes into a slightly more understandable syntax called “assembly language”. From there, other programming languages will create instructions based on their own syntax.
This typically works like this:
Fig. 1. Machine language implementation
Processors that read and act on this machine code can only concurrently use the number of register bits available. For an 8-bit processor, this means that each instruction can only be 8 bits long.
A simple example is a 4-bit register. This has a range of 16 possible binary values from: 0000 to 1111, which translates to decimal values of 0 to 15. The number of possible values (or “states” of the register) is defined by the number of bits available. The relationship is:
Number of possible states = 2n (n = number of bits)
For n = 4 we have 24: 2*2*2*2 = 16. Obviously, more bits is more desirable because you can do more with more information. Our current 64 bit processors have 264 states, or 18,446,744,073,709,551,616. You’d think that would be enough to do whatever we need to... but many applications, especially cryptographic ones, would significantly benefit for more states or more computing power.
Quantum computing is an entirely different architecture than classical computing. It uses properties of the quantum world to represent information and do processing on this information.
The Quantum World
The simplest way to understand these properties of the quantum world is to compare it to light. For many years, experiments with light demonstrated that light had the properties of a wave. An example of this would be how light will diffract around small holes in barriers – similar to what sound waves will do, this is known as the “wave nature” of light. But in 1905, Einstein theorized that light also had some of the properties of a particle, such as momentum. This is known as the “particle nature” of light. Together, they are known as the “particle-wave nature of light”. This was quickly experimentally verified by the results of the “photo-electric effect”, which measured the momentum of a photon.
In the quantum world, all particles can be expressed as waves of some kind and this is the basis for quantum computers. Since waves are generally continuous phenomena and particles are generally discrete phenomena, this duality may seem contradictory, but it is the basis for many of the strange things that happen in the quantum world. Quantum computing exploits these properties to greatly expand the computing power.
It’s true that all particles have associated waves, but the more mass a particle has, the harder it is to measure or even define this wave. But for individual atoms or nuclei, it is not impossible. What is usually expressed is a property that is called “spin” and it is measured and defined as “up” and “down”. This discrete property is clearly a “particle” property. But the “wave” nature of the particle’s spin property can be expressed as some combination of spin up and spin down. The act of measuring the spin experimentally (or interacting with the atom) is what then causes the atom to settle in to one of the two spin states. In between measurements, the atom is in some combination of spins up and spins down.
Schrödinger postulated the famous cat in a box experiment: suppose there is a cat in a box. We don’t know if it is alive or dead until we open the box. It could be either state, or in the quantum world, both states. This is the simple expression of what was mentioned above – we don’t know the spin of the atom until we measure it – we open the box.
Representation of Quantum States
The most common way to represent the quantum property of “spin” is to use notation developed by Dirac. Basically it’s shorthand for a very complicated expression of the Schrödinger wave of the particle.
Spin “up” is represented by: |0>, and spin “down” is represented by: |1>. And so the state of the particle at any given time (prior to a measurement) is a combination of these two expressions:
Particle wave = |0> + |1>
With this representation, we are ready to dive into quantum computing.
The quantum computing equivalent of the classical bit is the “qubit”. Most broadly, a qubit is a particle whose quantum state can be measured and when measured, the particle would be in some defined state, like spin up or down. So a quantum computer can measure the same number of 2n states as a classical computer. The difference is in how the particle gets from one state to another, because when you are not measuring this property, the particle can be in any state, as represented by the wave above. This combination of states is called “a superposition of states”.
People have been theorizing about quantum computing since at least 1980. But it was in the 1990s that significant progress was made. The history of the field is summarized here.
IBM’s 5 Qubit Machine
Earlier this year, IBM gave access to their five qubit quantum computer (IBM 5Q) in the cloud. This is an actual quantum computer and you can run actual code on it. But it is a very basic machine and in order to use it, you have be able to compose in code even more primitive than machine code. This is because unlike classical processors, the 5Q has no defined instruction set, so in order to use it, you would need to write the basic instruction set.
The physical machine is supercooled to a temperature of barely above absolute zero (0.014458 degrees above absolute zero). The heart of the quantum computer is contained in this environment. The chip containing the five qubits looks like this:
Fig. 2. IBM’s 5Q Chip
The five qubits are the five dark squares in the photo.
Programming the IBM 5Q
Classical computers, at the most basic level, use logic gates to perform their instructions. Logic gates are physical structures (like a transistor) that perform logical operations by using an electric current and determining the voltage. For example, the AND gate. An AND gate takes two input bits and send out one output bit based on the values of the two inputs. If the inputs are both true (11), then the output would be true (1). If the inputs are not both true (00, 01 or 10), then the output would be 0. All CPU operations can be devolved to some kind of operation by logic gates on input bits.
Quantum computing has similar “logic” gates, but these exploit the quantum properties. There are gates that can flip the spin of the qubit, or gates that can “rotate” the spin to the X, Y or Z axis, or gates that can take a single, well-defined state and convert it to a superposition of states.
The way you apply these gates to the qubits in the IBM 5Q is by an interface they call the “Composer” (the reason why will be self-evident). Here is what it looks like:
Fig. 3. The 5Q “Composer”
The five qubits (Q0, Q1, Q2, Q3, and Q4) are arranged in lines that look like a musical staff, and time progresses from left to right. Below it are the selection of gates available, and the possible ways to measure outcomes. In the machine, the five qubits all start out in the defined state of |0>. This is like clearing a register on a classical computer prior to beginning an operation.
From here we can add gates to do various operations on the qubits to create a “score”. Then we either run a simulation or submit the score to the actual quantum computer. IBM does not let you submit all the scores you want to the 5Q, they allocate units to you and you use these units to run your scores. These units allow you to make multiple executions of the code to come up with numbers which correspond to the probabilities of the final state(s). The simulation mode is adequate for testing, and with the simulation mode you can choose an Ideal Quantum Processor which generates the theoretical results, or a Real Quantum Processor which uses a 5Q simulator to generate real world results, which are never exactly the theoretical ones.
We can measure the initial state of a qubit and see what it is. We use the measure control that looks like a gauge and add it to the score:
Fig. 4. Physically measuring the state of Q0
Then click the “Simulate” button and it will return the result for Q0:
Fig. 5. Result of physically measuring the state of Q0
As a result of our measurement, Q0 is found to be 100% in the 0 state. In other words, the wave for Q0 is made up entirely of spin “up”: |0>.
What happens when we apply one of the gates to Q0? The gate called “X” is the one that will flip the spin of the qubit. That score would look like:
Fig. 6. Flipping the state of Q0
The theoretical result of applying this gate to a spin up state should be a spin down state. Or |1>. Let’s see the results:
Fig. 7. Result of flipping the state of Q0
100% of Q0 is now in the spin down state.
The other gates do different things to the qubits. Some of them are somewhat equivalent to classic gates, and some are exclusive to quantum computers. The gates available on the 5Q are:
Fig. 8. Quantum gates available on IBM 5Q
- Id: The identity gate simply passes the qubit through with no effect. It’s used to add time delays to the score, which only impact the real world results.
- X, Y & Z: Technically these are “rotation” gates. X will rotate to the X-axis, which is a flip of the state. Y & Z similarly rotate to the Y & Z axes, which is to physically change the phase, and may or may not result in a state flip.
- H: Hamadard gate. This one is used to split the input state into an equal superposition of all states. It’s one of the non-classical gates and is used extensively in quantum computing.
- S and S+: This set of gates change the input state into a state that is called “circular” because it can be described as a superposition based on points on a circle. The difference between the two gates is that the S+ gate has a result that is 180 degrees out of phase with the S gate result.
- +: This is the “Controlled NOT” or CNOT gate. This one is most like a classical gate, the XOR (exclusive OR). There is a target qubit and a control qubit. If the control qubit is spin down, then the target qubit state is flipped. If the control qubit is spin up, then nothing happens to the target qubit.
- T and T+: A purely quantum set of gates that can be used in constructing some classical gates, such as the Toffoli (AND gate).
The big advantage of quantum computers, as mentioned above, is that the qubits are able to be in multiple states at once, and so they can perform some calculations quicker.
IBM states in the tutorial documentation for the 5Q:
"The power of the quantum computer, meanwhile, lies in its much richer repertoire of states. A quantum computer also has bits, just like any computer. But instead of 0 and 1, its quantum bits, or qubits, can represent a 0, 1, or both at once, a property known as superposition. This by itself is not much help, since a computer whose bits can be intermediate between 0 and 1 is just an analog computer, scarcely more powerful than an ordinary digital computer. A quantum computer takes advantage of a special kind of superposition that allows for exponentially many logical states at once, all the states from |00..0> to |11..1>. This is a powerful feat, and no classical computer can achieve it. The vast majority of these quantum superpositions, and the ones most useful for quantum computation, are entangled—they are states of the whole computer that do not correspond to any assignment of digital or analog states of the individual qubits. While not as powerful as exponentially many classical computers, a quantum computer is significantly more powerful than any one classical computer -- whether it be deterministic, probabilistic, or analog. For a few famous problems (such as factoring large numbers), a quantum computer is clearly the winner over a classical computer. A working quantum computer could factor numbers in a day that would take a classical computer millions of years."
The heart of the quantum computer is how it takes advantage of entangled states. These entangled states are somewhat difficult to explain. This is the principle of “spooky action at a distance”, where a quantum system at one location influences or is influenced by another quantum system at another location, which theoretically could be at a vast distance. It’s counterintuitive because it’s not bound by the universal speed limit, the speed of light in a vacuum. This is also the basis of what is known as “Quantum Teleportation”.
This entanglement means that two or more quantum systems are linked by an entangled wave and this can be used to our advantage.
One relatively straightforward application is in searching a list of items for an element that meets specific criteria. Searching an unstructured list is classically done by starting at the first item and comparing it to the pre-defined search criteria. Say you have N items and if you’re lucky you find the match on the first try, on average it should take N/2 times to find the match and at most N times if you have to compare every item with your criteria.
But with quantum computers, the average search can be reduced to the square root of N tries. This is a significant advantage when searching large amounts of objects. Not so much for smaller numbers. If N=3, then N/2=1.5 and the square root of N = 1.73 and for N=4, N/2 = 2 = the square root of N. But suppose you had 64 objects to search. N/2 = 32 and the square root of N = 8. And it just gets more significant as N increases.
How can we do this, you may ask? Classical computing applies algorithms to problems, and so does quantum computing. For searching there is an algorithm called “Grover’s Algorithm”. Applying Grover’s Algorithm to a quantum search can realize this reduction in the average number of items to search.
To apply Grover’s Algorithm, we must first define a function called “the Oracle”. Basically this is our search criteria, like what you would type into Google. The function returns the value of 1 if the element is not what we are looking for, and it returns a value of -1 if it is. We are going to be searching for our element in a quantum state that is a uniform superposition of quantum states that represent all states that we are searching.
Suppose our list has 10 items (N=10). The initial state is a uniform superposition of all 10 states: |Q> = |1> + |2> + |3> + |4> + |5> + |6> + |7> + |8> + |9> + |10>. In our case the average amplitude of the superpositions is 1 because it’s a uniform superposition and every amplitude is the same (here it is arbitrarily 1). A chart of the 10 states might look like this, with the average shown as the black dashed line:
Fig. 9. Ground state of the search list superposition
Imagine that item |7> has the properties of what we are looking for. Now, we apply the Oracle and the superposition becomes: |Q> = |1> + |2> + |3> + |4> + |5> + |6> - |7> + |8> + |9> + |10>. The average amplitude has decreased because of the single value that has become -1, in our case the average amplitude becomes 0.8. This new state can be thought of as a reflection of the |7> state about the x-axis. Our new superposition looks like this, with the new average shown by the yellow dashed line:
Fig. 10. State of the search list superposition after applying the Oracle function
Now we perform another reflection, of the whole |Q>, about the new average (0.8). What this will do is increase our target amplitude and decrease all the other ones. Reflection about the new average for a given amplitude is: (2*Average – Amplitude). So for all the amplitude values of 1.0, the new value becomes 0.6, but for the target amplitude, which started out as -1, it becomes: 2.6, making it much easier to find.
Fig. 11. State of the search list superposition after inverting about the new average value
But it’s still not a sure thing, so we can keep doing this process until the value for our target item becomes significantly larger than anything else in the list. The mathematically optimal number of applications of Grover’s algorithm has been shown to be: (pi/4) multiplied by the square root of N, which in the case of N=10 becomes: 2.48 steps, so we would need somewhere between two and three applications of the algorithm to most efficiently find the target value. If we just searched the list classically we would need a minimum of 1 try and a maximum of 10 tries, with an average of 5 tries.
Actual Quantum Computing
As mentioned above, classical computers process information as bits. There are fairly well known arrangements of simple gates that can be combined to do this processing. One of the simplest is known as the “Half-Adder”. It adds two bits together and produces the result and also a “carry” bit, because a single bit can only be 1 or 0 in binary, which also is 1 or 0 in decimal. But you could add 1 and 1 to get a value of 2, which cannot be expressed as a single binary bit: 1 + 1 = 2 decimal = 10 binary, where the leftmost binary “1” is the carry bit, which indicates that the result has exceeded the value that can be represented by the rightmost bit (or bits).
A half adder is implemented classically by an AND gate and an Exclusive OR (XOR) gate. The logic diagram and truth table for the half-adder is:
Fig. 12. Half-adder logic diagram and truth table
If A and B are 0, then the result is S = 0. If either A or B is 1, then the result S = 1. And if A and B are 1, then S = 0, but C = 1 indicating that we need another bit to express the result (binary 10 = decimal 2). Notice that for A or B = 1, the result is the same (binary 01), and we cannot know which of the inputs was 1 and which was 0 without explicitly knowing A or B.
It is possible to construct both an XOR and an AND gate using gates in a quantum computer. In fact, it is possible to do this using IBM’s 5Q, though we cannot physically make an entire half-adder because of limitations of the configuration (only Q2 is connected to other qubits – if you look at Fig. 2, you see only one of the qubits, the middle one, has a connection to the other four qubits. They are not connected to each other). But this doesn’t prevent us from constructing two independent “scores” representing a quantum AND gate and a quantum XOR gate and evaluating the results.
But we can start with the ideal quantum processor, which does have all five qubits connected to each other. Our score for the ideal half-adder looks like:
Fig. 13. Quantum half-adder score (ideal simulation)
Here we have the input bits (A and B) going to Q0, Q3 and Q1, Q4 respectively. The sum (S) is the resulting value of Q3 and the carry bit (C) is the resulting value of Q2. We can change the value (state) of input bits by putting the “X” gate at the start of the qubits we want to change, because the X gate flips the state of the qubit, so any qubits passing through the X gate go from |0> to |1> (or from |1> to |0> depending on how they start out).
The truth table for this quantum processor is:
Table 1. Quantum half-adder truth table (ideal simulation)
Note that unlike the classical processor, with the quantum processor you can tell what the states of the inputs A and B are by inspecting the results. If A were 1, then the result would have Q4 = 0, and vice versa. This is known as being “reversible”. All quantum gates have to be reversible by definition, whereas not all classical gates are.
Because the quantum XOR and the quantum AND gates both require a controlled gate (the “+”, or CNOT gate), the physical limitation of the 5Q that only Q2 can interact with and be controlled by other gates means that for real world demonstration purposes we need to split this score into two separate scores, one for the XOR and one for the AND.
The XOR gate score looks like this:
Fig. 14. Quantum XOR gate (CNOT)
And the AND gate score looks like:
Fig. 15. Quantum AND gate (Toffoli)
There are two independent truth tables as well.
What happens when you run these scores on the Real Quantum Processor? If A=0, B=0, for the XOR gate, the Ideal results are:
Fig. 16. Results of the quantum XOR gate (ideal simulation)
The result is all in the 00 state, as expected. But if I run this on the IBM 5Q, we get:
Fig. 17. Results of the quantum XOR gate (real processing)
In the real quantum computer, the probability distribution of states is not perfect. There are physical imperfections in the machine, noise, quantum interference and several other sources of error, including the effects of neighboring qubits on the qubits that are being processed. Both in implementation and in measurements, these errors can cause some of the states to end up other than 00. For this set of runs (4096 times) the average probability for each of the four states (00, 01, 10 and 11) is:
Table. 2. Results for 4096 runs of the XOR gate, input state 00
Here, the probability is highest for the theoretically expected state, but it’s not 1.0. Notice that the probability for all the possible states has to add up to 1.0, which they fortunately do.
The same real world results will occur when we run the AND gate through the 5Q. This time we have three qubits, so there are 23 = 8 possible states from 000 (0) to 111 (7).
Below are the results for both gates, for all input permutations of A, B (remembering that the AND gate has a separate output result for Q2) with expected results in bold:
XOR Gate (Actual - 4096 shots)
Table 3. Results for 4096 runs of the XOR gate, for all input states
AND Gate (Actual - 4096 shots)
Table 4. Results for 4096 runs of the AND gate, for all input states
We cannot get the values for the real quantum processor for the entire half-adder at once because we don’t know the phases of the various states and therefore we can’t combine the results. But the results are consistent with the expected ideal results. The most likely real world result corresponds to the ideal result.
The data that comes back from the 5Q also includes some information on the physical state of the quantum computer:
Fig. 18. IBM 5Q physical state information
There’s information on the operational status of the machine, in this case it is ACTIVE and running at a temperature of 0.014442K and was last calibrated on 2016-06-07 at 00:05. There is also some qubit specific calibration data:
- T1 – Relaxation time: the average lifetime of the qubit, this is how long you have to complete the computation
- T2 – Coherence time: the average time you have to anticipate and apply error correction to the qubit
- eg – Gate errors: rate of error in the gates applied to the qubit
- er – Readout errors: rate of error in reading the qubit
The Future of Quantum Computing
Quantum computing is still in its infancy. The theoretical basis is well defined and much progress is being made in finding new algorithms and new gates to implement them, but the physical implementations are far behind. IBM’s 5Q is a good step forward and there are other groups engineering machines that have more qubits. I believe the current record holder is 84 qubits.
Researchers have even made rudimentary simulations of particle physics on a four qubit quantum computer.
It will be a while before quantum computing hits the mainstream and we’re not going to be writing apps for a quantum tablet any time soon. But there’s no reason to think that this won’t come. After all, the first digital computer was an enormous machine, taking up vast amounts of space and energy to run. The average phone is many, many times more powerful than that today.