Quantum Computers
God does not play dice with the universe. Albert Einstein
The 2012 Nobel Prize in Physics was awarded to Serge Haroche and David Wineland for Quantum Entanglement, which is a phenomenon that enables the manipulation and measurement of individual quantum systems without destroying them. This may pave the way for superfast computers, called quantum computers. Some of the smartest physicists, mathematicians and information theorists today are driving this development. Quantum computers may find applications in inverse problems, like those which the industry is trying to solve in geophysics. Give it 20–30 years, and you will have quantum computer desktops.
Will we ever have the amount of computing power that we need or want? What is the next era of computing? If we agree with Moore’s Law, the years 2020-2030 will find the circuits on a microprocessor measured on an atomic scale. The logical next step will be to develop quantum computers which tap directly into the field of quantum mechanics to speed computation. As of 2016, the development of quantum computers is still in its infancy, but experiments have been carried out in which quantum computational operations were executed on a very small number of quantum bits. Academic research labs and universities around the world and companies such as IBM, NASA, Google, Microsoft, and Lockheed Martin have been working on the basic building blocks of a quantum computer for some years. But most people, like us, do not really understand what quantum computing is and isn’t. We will not even attempt to give a full explanation, but only an introduction.
Computers require data to be encoded into binary digits (bits). A bit is the basic unit of information in computing and can have only one of two values: 0 and 1. A quantum computer exploits quantum mechanical phenomena, such as superposition and entanglement to perform operations. Instead of bits, quantum bits or qubits that can be zero and one at the same time are used.
Recall that a conventional computer stores information as 0s or 1s. Most real numbers are stored with a set of 64 zeroes or ones – i.e. bits. However, the quantum computer uses quantum bits, or qubits – which can be a 1 or a 0 or both at the same time, a condition known as a superposition. Qubits represent particles – atoms, ions, photons, or electrons – and their respective control devices work together to act as computer memory and a processor. Because qubits can exist in quantum superposition, or multiple states simultaneously, the quantum computer has the potential to be millions of times more powerful than today’s most powerful supercomputers. But – of course – this real speedup remains to be demonstrated.
Quantum computing exploits two principles offered by the laws of quantum mechanics to perform operations on data: the principle of superposition of states and the concept of entanglement. Superposition is a one-particle property while entanglement is a phenomenon associated with two or more separated but connected particles.
Superposition
Superposition is essentially the ability of a quantum system to be in multiple states at the same time. A well-known example of a two-state system is the spin of a spin-1/2 particle such as an electron, where the spin can point in two opposite directions, say ‘up’ or ‘down’, and the spin states can be denoted as |1〉 and |0〉. By the laws of quantum mechanics, the electron can exist in a superposition of these two states, written as: |f〉= a|0〉 + b|1〉, where a and b are related to the probability of finding the electron in state |0〉 and |1〉, respectively, satisfying |a|2 + |b|2 = 1. |f〉 is called a qubit. A single qubit thus can represent 1, 0, or any superposition of these two qubit states. As such, a qubit might seem to contain an infinite amount of information. But the information must be extracted by a measurement. When it is measured, quantum physics requires that the result is an ordinary bit – either |1〉 or |0〉.
Entanglement
In quantum physics, entanglement is an extremely strong correlation that exists between quantum particles — so strong, in fact, that two or more quantum particles can ‘dance’ in instantaneous, perfect unison, even when placed at opposite ends of the universe. This seemingly impossible connection inspired Einstein to describe entanglement as ‘spukhafte Fernwirkung’ or ‘spooky action at a distance.’ The quantum state of each particle cannot be described independently – instead, they are to be considered as a whole.
Consider two entangled electrons; the sum of their spins is null. When entangled, their spins are linked by photons acting as the messengers of the electron’s spin. If entanglement had an analog in classical physics when you spin coins, then if you spun a coin in London clockwise, an entangled second coin in Trondheim would start to spin counter-clockwise.
Cartoon helping to explain the idea of ‘entangled particles.’ Alice and Bob represent photon detectors. (Source: NASA/JPL-Caltech)
Two spatially separated qubits can be in any superposition of 22 = 4 states: |0〉|0〉, |0〉|1〉, |1〉|0〉, |1〉|1〉. Of these, the four states 1/√2(|0〉|0〉 ± |1〉|1〉), 1/√2(|0〉|1〉 ± |1〉|0〉) are called the ‘maximally entangled Bell states’ (see https://quantiki.org/wiki/bell-state). They have the peculiar property that the particles always ‘know’ about each other, even if they are separated by large distances. Consider the first Bell state, and assume that the two separated qubits are held by Alice (A) and Bob (B). The state is 1/√2(|0〉A|0〉B + |1〉A|1〉B), meaning the qubit held by Alice can be 0 as well as 1. If Alice performs a measurement on her qubit the outcome would be perfectly random, either possibility having probability 1/2. But now the fate of Bob’s qubit is sealed; the outcome would be the same as the one Alice got. So, if Alice tells Bob the result of her measurement, Bob instantly knows what the result of measuring his qubit would be – he doesn’t need to bother doing the actual measurement.
You may say that this is nothing special: maybe, when the pair was created (before the qubits were separated), the two particles ‘agreed’ in advance which outcome they would show in case of a measurement. Following Einstein, Podolsky, and Rosen in 1935 in their famous ‘EPR paper’, there is something missing in the description of the qubit pair given above – namely this ‘agreement’, called more formally a hidden variable. Then, in another famous paper from 1964, John S. Bell showed by simple probability theory arguments that these correlations cannot be explained by the use of any ‘pre-agreement’ stored in some hidden variables – but that quantum mechanics predicts perfect correlations.
Entanglement such as this is a basic ingredient of quantum computing. Three qubits will be in any superposition of 23=8 states: 000, 001, 010, 011, 100, 101, 110, 111. Generally, n qubits can be in a superposition of 2n states. In quantum one-way computers the computation is decomposed into a sequence of one-qubit measurements applied to a highly entangled initial or cluster state. The calculation ends with a measurement, collapsing the system of qubits into one of the 2n pure states, where each qubit is zero or one. The outcome can therefore be at most n classical bits of information. Quantum algorithms are often non-deterministic, in that they provide the correct solution only with a certain known probability.
Sorry Albert, but it looks like the universe is one big dice game. Recent studies have confirmed that the ‘spooky action at a distance’ that so upset Einstein — the notion that two entangled particles separated by long distances can instantly affect each other — has been proven to work. (Source: Rik57|Dreamstime.com)
The Holy Grail
The time needed to solve a problem increases with the problem’s size. For a conventional computer the time needed to factor a number explodes almost exponentially with the number of digits. The idea behind quantum computing is that its compute time will grow much more slowly; for the factorization problem that time should grow as the number of digits cubed. This is a ‘quantum speedup’. To date (May 2016), the largest number factored on a quantum device is 200,099. (The factors of a number are all those numbers that can divide evenly into the number with no remainder.)
It is the quantum computer’s advantage of using 1s, 0s and ‘superpositions’ of 1s and 0s that can make it outperform classic supercomputers. Its basic feature is its ability to operate simultaneously on a collection of states, thereby performing many operations in the time. Certain complex calculations can be done exponentially faster than a classical computer.
The difference between quantum computing and classical computing can be illustrated by the optimization problem of finding the lowest point in a landscape with mountains and valleys, like the waveform inversion problem that geophysicists have been working on for decades. Every possible altitude of the landscape at a point, or the ‘energy’’ or ‘cost’ of the solution, is mapped to coordinates on the landscape. Classical computers running classical algorithms can only ‘walk over the landscape’. Quantum computers can tunnel through the landscape thus making it faster to find the lowest point. Particularly for highly irregular (or non-smooth) surfaces, this type of tunneling might speed up the optimization process significantly.
But what more can quantum computers do than searching through a space of potential solutions for the best one? Quantum computers will be able to efficiently simulate quantum systems, which has been said to be a ‘holy grail’ of quantum computing: it will allow us to study, in great detail, the interactions between atoms and molecules. This could help design new drugs and new materials.
More creepy is the fact that quantum computers can learn from experience and do self-corrections. This concept is called machine learning. It is much more sophisticated than your Facebook news that feeds changes based on which posts you ‘like’.
If you feel that quantum computers sound like witchcraft, you’re not alone. The future uses are bound only by imagination.
