Counting on uncertainty

Les chats de Schrödinger savent compter

Quantum computing is based on quantum bits or "qubits". While classical bits can be in either a 0 or 1 state, qubits are a superposition of two quantum states of a system, representing 0 and 1. Qubits thus encapsulate the ambiguous, uncertain world of quantum mechanics. They can be realized by the superposed polarization states of photons, or superposed spin states of electrons, ions or even molecular nuclei.

CCD image

The importance of qubits for computer science arises because of the phenomenon of quantum entanglement. When several qubits interact, their quantum states become correlated. This allows an assembly of qubits to represent a lot of information. For example, whereas two bits of information can represent only one of four binary numbers, 00, 10, 01 or 11, two entangled qubits can represent all four at the same time. N qubits can thus represent 2^N binary numbers. By operating on an assembly of entangled qubits in a suitable manner - for example putting spin-based qubits in a magnetic field - parallel computations can effectively be carried out on all the binary numbers at once.

Observing the qubyte

This exponential growth in information content and processing power with the number of qubits means that quantum computers are uniquely efficient at certain tasks that their classical counterparts find excessively time consuming. This is the case for the factorization of large numbers. An algorithm developed for quantum computation by Peter Shor of Bell Labs in 1994 allows factorization of a number with N digits in a time that scales as the log(N)³, whereas the best classical algorithms take times that grow exponentially with N.

Density matrix

Shor's algorithm means that factorizing a number of several hundred digits could be done on a fairly simple quantum computer in less than a year, whereas it might take billions of years on one of today's best supercomputers. This has major implications for "public key" cryptography, which relies on the difficulty of factorizing large numbers to encode digital data securely. Another potentially practical development is a quantum database-search method known as Grover's algorithm, invented by Lov Grover of Bell Labs in 1996, which also produces significant speed-ups over classical methods.

To exploit these theoretical breakthroughs, the challenge is to make quantum computation work in practice. The announcement of the first qubyte, or eight qubits, in December 2005, by a group at the University of Innsbruck characterized the state-of-the-art in assembling qubits (Häffner et al. 2005). The group used eight calcium ions in a magnetic ion trap to achieve this feat. However, in practice, the nuclear spins of molecules in a liquid, which can be addressed using NMR technology, have proved the most fertile ground for testing the principles of quantum computation. The reason for this is that by having huge numbers of identical molecules carry out the same quantum calculation, the system is much more robust against the phenomenon of decoherence, where any interaction of a qubit with the environment - even with a single photon - causes a quantum computation to crash.

The massive redundancy offered by a macroscopic ensemble of molecules means that although many individual molecules may be affected by decoherence, a quantum calculation can still be carried out in a few seconds. In 2001, IBM's Almaden Research Center and Stanford University used NMR to demonstrate Shor's algorithm experimentally for the first time: they factorized the number 15 into 5 and 3.

Great expectations

This was admittedly a modest start. But Nicolas Gisin from the University of Geneva, one of the pioneers of quantum computing, remarks, "Over the last few years the field developed very rapidly and a lot of progress was achieved both in quantum computing and quantum communication. There are a tremendous number of ideas, and we are optimistic that we will see huge progress." Indeed, in 2001, a spin-off from Gisin's research group called id Quantique was the first company to put commercial quantum cryptography on the market.

Quantum cryptography involves encoding information in the form of polarized photons, in such a way that any attempt to eavesdrop on a communication between two parties will result in a measurement of the photon polarization. This inevitably changes the state of some of the photons, and can thus be detected. The approach is much more robust than traditional public-key cryptography. Ironically, the reason some companies and government organizations are showing interest in quantum cryptography is the fear that, some years from now, practical quantum computers may be able to crack public-key systems by factorizing large numbers rapidly. Last year, id Quantique began offering turn-key secure communications service to Swiss firms, by partnering with Fibrelac, a provider of the optical-fibre links that are needed for quantum-cryptography-based communications.

On the research front, Gisin's group is already investigating combining quantum computing and quantum communication. In September they described how qubits could be transferred from one place to another, using photons as the natural "flying" qubit states (Tanzilli et al. 2005). This involves translating the information in stationary atomic qubits - in this case alkaline atoms that absorb and emit at 800 nm wavelength - into photon wavelengths that can travel down typical optical fibres at 1310 nm or 1550 nm. This proof-of-principle is another step down the long road to useful quantum computers.

"Experiments are limited to small numbers of qubits at the moment and not only the number is important, but also the quality," says Gisin. "We need to develop a laboratory model of quantum processors, including error correction, to bring the different fields together with further advances in theory: new computational models and architectures, further understanding of entanglement and decoherence."

On the positive side, great strides are being made in assembling long-lived registers of qubits. For example, researchers at the Max Planck Institute for Quantum Optics have cooled single rubidium atoms in every direction of motion and kept them for an average of 17 s in an optical resonator (Nußmann et al. 2005). This enables experiments to study the interaction of individual atoms with individual photons. The trapped atoms can in principle be used to store qubits, and the photons they emit effectively carry out the quantum computing operations.

In another breakthrough, a group at the National Institute of Standards and Technology (NIST) has demonstrated a quantum physics version of computer memory lasting more than 10 s (Langer et al. 2005). The researchers used superposition of two internal energy levels of a beryllium ion to create their qubits, and by choosing the energy levels carefully, maintained superposition 100,000 times longer than in previous experiments on such ions. On the other hand, theoreticians at Leiden University have discovered that the coherence of qubits will spontaneously disappear over time (van Wezel et al. 2005), challenging even the most sophisticated efforts to avoid decoherence.

Hope remains, however, that a full-scale quantum computer may still produce reliable results, even if its components perform no better than today's experimental qubits. The idea is to correct errors faster than they occur, and theoretical considerations show this will work even if the correction mechanism itself is not error-free. One proposed route to achieving this uses the phenomenon of quantum teleportation. This Star Trek-like process transmits the quantum properties of one photon instantaneously to another far-removed photon, while at the same time destroying the state of the original photon. It is an extreme case of quantum entanglement operating over large distances.

The idea proposed by Emanuel Knill at NIST last year is to use quantum teleportation of information at regular intervals from an assembly of qubits, to double-check continuously the accuracy of qubit values (Knill 2005). This both tracks how errors are affecting the qubit assembly and transfers stored information to other qubits not yet affected by decoherence. The proposed procedure is to create a hierarchy of qubits at various levels of validation, and only the top-tier - the most accurate qubits - are actually used for computations.

While researchers pursue different avenues to solving the many challenges facing quantum computing, a comprehensive roadmap has already been published tracing the anticipated progress of the field towards practical applications (see http://qist.lanl.gov/qcomp_map.shtml). It is unlikely that "QC inside" will adorn your laptop anytime soon. But the field promises to remain rich in both scientific and technological opportunities for many years to come.

Further reading

H Häffner et al. 2005 Nature 438 643.
S Tanzilli et al. 2005 Nature 437 116.
S Nu&szling;mann et al. 2005 Nature Physics 1 122.
C Langer et al. 2005 Phys. Rev. Lett. 95 060502.
J van Wezel et al. 2005 Phys. Rev. Lett. 94 230401.
E Knill 2005 Nature 434 39.