Quantum Computing
Created | Updated Jan 21, 2004
Computers today follow the standard laws of classical physics. However, physicists believe that, in principle, it is better to use the laws of quantum physics1 for a computer. The advantages are that the speed of computing would rocket to unimaginable standards, and all-new code-cracking devices could be created. Quantum computers work by using a quantum equivalent of computer bits in the binary maths system, and simple ones have already been built.
A quantum computer exploits a very special law of quantum mechanics in order to allow the system to do calculations simultaneously. A sub-atomic particle2 has a property called its ‘spin’, which can be in two possible states: up or down. But in quantum physics particles can have a state called its ‘superposition’. This means that a particle can be in two places at once (!) or in two states at once, so long as one does not interfere with them or observe them. Doing this would cause ‘decoherence’, in which the particle makes a random decision of which place or state it’s actually in.
It may help to consider an analogy with matchsticks. Imagine two matchsticks that represent the ‘up’ state of an electron, and two that represent the ‘down’ state. It is possible to see each state separately as matchsticks, but, if the sticks are arranged to form a square, then you could see the ‘up’ and ‘down’ states simultaneously. This represents the superposition, but in reality if you looked at this superposition, half of the matchsticks would vanish so that you only saw one state.
Conventional classical physics computers use binary numbers to carry out calculations. With a quantum computer, you can use the spin to determine a binary number. The ‘up’ state can take the place of the ‘0’; the ‘down’ state, ‘1’. But we have established that there is a third possibility: the superposition of 0 and 1 (i.e. both values simultaneously). It is this superposition that makes all the difference. In classical computers, these values are called ‘bits’; in quantum computers, they are called quantum bits, or ‘qubits’.
Suppose there is a quantum computer with four qubits. With this, one can have 2^4 (2 to the power of 4) possible values, or 16. This is 4 times as much as a classic computer can handle – an improvement in itself. This improvement grows exponentially with a quantum computer that has more and more qubits. So with a 32-qubit quantum computer, you get 4 294 967 296 possible values. Therefore, this quantum computer could be set up to do over 4 thousand million calculations simultaneously.
How would it work?
To create the superposition, pulses of laser light are shone on an electron for a a specific amount of time. There would then be a fifty-fifty chance of the electron indicating 0 or 1. The results of any quantum computer experiment are read as interference patterns on a screen - this is called a sum over histories diagram.
What actually happens is that in a superposition, the electron that is in the 'up' state is in one universe, while the 'down' state electron is in another. These are parallel universes, part of the quantum 'many worlds' theory where every possible outcome of a quantum decision is played out in a separate universe. Basically, electrons are doing calculations in slightly different ways in different universes simultaneously, and when they come back they interfere, which is when we see the interference pattern.
Suppose there is a quantum computer with just one qubit for simplicity. Thus, there are four possible values: 00, 01, 10 and 11 (0, 1, 2 and 3 respectively). Suppose there are four objects in a box that we can’t see, and that one of them would shift a photon by 180 degrees on its course. With classical physics, all it is possible to do is send a photon through all of them and see whether the photon changes course by 180 degrees. But quantum computers can do better.
The quantum computer in this example would have a sequence of beam splitters within the box. If a photon is fired from a laser into the box then the photon has a choice of which path to take and it is not known what its decision is. So in the laws of quantum physics, it actually takes a superposition of all of the paths, or all four paths simultaneously. That means that one photon can go through all four objects at the same time! Therefore, whichever object in the box is the 180 degree-photon-turner culprit, the quantum computer will always tell you the correct result.
Looking into the box in the example given would destroy the quantum nature of the photon used – i.e. decoherence. In a more complex quantum computer care is required to ensure that the sub-atomic particles used do not impede other molecules that could decohere them. This requires a new technique that is, effectively, teleportation.
For this, quantum physics needs to be exploited again, and this time it is a property called ‘entanglement’. This is when two sub-atomic particles share a common property. It would be possible to send these particles to opposite ends of the galaxy, and on observation of one, the other would instantaneously take on the opposite of their common property (even Einstein described this feature of the quantum world as ‘spooky’).
So, take two entangled photons. Send one to a station that will be used for transmission; the other to a receiving station. Now get another independent photon that you wish to teleport from the transmitting station to the receiving station. Now make a joint observation of the state of the two photons at the transmitting station, thus causing decoherence and meaning the photon at the receiving station changes to the opposite state. Send the result of the observation to the receiving station by conventional communication (ring up a friend there, for example). This forces the photon at the receiving station to change its state again so that it has an identical state to the photon you wanted to transport, whilst meanwhile the photon in question at the sending station changes again completely. This is effectively teleportation.
If the method of teleporting by entanglement could be compacted and simplified to work within a computer environment then you could send information wherever it was needed without it being met by decoherence. The qubit system within such a quantum computer can be made with photons, or with ions inside electromagnetic fields. One of the most popular methods is called Nuclear Magnetic Resonance where the value of a qubit is represented by a nucleus’s alignment with respect to the direction of a surrounding magnetic field. At Los Alamos National Laboratory, led by Raymond Laflamme in 1998, a single qubit was spread across three nuclear spins in each molecule of a solution of alanine or trichloroethylene.
Can It Be Done?
It has been done! Quantum computers have been built with up to seven qubits. Scientists can sustain a superposition within such a quantum computer long enough to take measurements that prove the theories, and at the NEC Fundamental Research Laboratories in Ibaraki, Japan, a 2-qubit quantum chip was created with standard silicon techniques (this is similar to classical microprocessors that are used). The teleporter technique described has been tried in Innsbruck, Austria, where there was a 25 percent success rate. This is exceedingly encouraging, but still a long way off there being mass production of quantum computers.
What Uses Does A Quantum Computer Have?
Classical computers take a long time to find a particular item from a database. Suppose there is a database of the six thousand million people (approx.) on planet Earth, and a particular record is needed. A classical computer would analyse each and every record in the database separately until it found the one matching the requirements. A 32-qubit quantum computer3 could analyse 4 294 967 296 of the records simultaneously and therefore would have a chance that exceeds fifty-percent of finding the required record in one instant of calculation! Parallel search methods (using ‘Grover’s quantum algorithm’) would mean that even a simple quantum computer might only take 80 000 attempts to find a record out of 6 000 000 000.
Quantum computers can also be used effectively to factorise numbers (finding two numbers that, when multiplied together, form a particular target number). This is a technique that can be used to crack the world’s most devious codes, and a quantum computer that can factorise small numbers has actually been built for demonstration purposes. Shor's algorithm is used to do this.
There are many more algorithms, such as the Deutsch-Jozsa algorithm that is used to distinguish certain types of functions. At present, these algorithms cannot be linked together to do very diverse computing, and parts of the theory may require updating as experiments are carried out. This produces unfortunate limitations on the whole concept that will need major work. The quantum world, by definition, deals with probability and uncertainty. It is difficult to produce accurate, feasible and practical machines that use such uncertain physics.
As a conclusion, it is possible to see how - eventually - quantum computers could change the world of computing forever. With speeds that are today unimaginable, they would certainly revolutionise communication.
For Further Information...
Background reading about quantum mechanicsThe Basic Parallel Universe IdeaInformation on Research Into Quantum Computers.A Detailed Article on Quantum Computing.An Additional Article.1See the Quantum Mechanics article for more details.2I.e. the smallest components of atoms such as an electron.3This only applies to serial searches.
