In the December 21 issue of the scientific journal Physical Review Letters a combined Australian-Canadian research team from Brisbane and Toronto have reported the first-ever unambiguous execution of a quantum calculation. By manipulating quantum mechanically entangled photons—the fundamental particles of light—the prime factors of the number 15 were calculated.

Although the answer to this problem could have been obtained much more quickly by querying a bright 8 year old, the result is significant because it was calculated using a quantum-mechanical program called Shor's algorithm (named after its discoverer, Prof. Peter Shor of the Massachusetts Institute of Technology). Previous theoretical work has shown that this program, when applied to larger numbers, could be used to crack cryptographic codes that are unbreakable using conventional computers. An essential ingredient of the power of quantum computers is entanglement: the apparently nonsensical correlations between particles that Einstein famously called "spooky action at a distance". The Australian-Canadian team showed that entanglement was present throughout their calculation.

Shor's Algorithm
Think of a number—15, for example—what are its prime factors? Recalling from your school days that primes are numbers divisible only by themselves and 1, then the prime factors of 15 are 3 and 5. But as the number becomes bigger and bigger the problem becomes more and more difficult: what are the prime factors of 133, or 1633 or 2934331? (Answers: 133=7x19, 1633=23x71, and 2934331=911x3221). What is difficult for your brain is also difficult for conventional computers. This is not just a problem of interest to pure mathematicians: the computational difficulty of factoring very large numbers forms the basis of widely used internet encryption systems. An efficient solution to this problem will have very far-reaching implications for communications security—quantum computers will be able to crack these codes.

In any computer a problem must be broken down into manageable chunks: classical computers use two-level systems called bits (binary digits); quantum computers use two-level quantum-mechanical systems called qubits (quantum bits). A qubit is like a coin that can be heads (on), tails (off) or simultaneously heads AND tails (on and off) or any possible combination in-between! This is impossible with normal bits. One qubit is described by three pieces of information, two qubits by fifteen; three qubits by sixty-three, and so on: quantum memory sizes grow exponentially with the number of qubits. Performing an operation on just one of these qubits—for example swapping 1 and 0—simultaneously performs an operation on all possible configurations of the quantum memory. In effect, using the combination of an exponentially large memory and massive quantum parallelism, provided by entanglement, allows simultaneous storage of all possible outcomes of a mathematical procedure, with clever down-selection giving the correct result.

The experiment
In the Brisbane experiment, single photons were used as qubits, with up to four being manipulated at once. Using a complex configuration of optical elements—by which photons can be created, sent into multiple paths simultaneously, then recombined—a simplified version of the factoring algorithm was performed, equivalent to factoring the number 15. The initial proposal for optical approach to quantum computing was made by Dr. Emmanuel Knill (of the National Institute of Standards and Technology, Boulder, Colorado), Prof. Raymond Laflamme (director of the Institute for Quantum Computing at the University of Waterloo, Ontario, Canada) and Prof. Gerard Milburn (University of Queensland, Australia).

In addition to executing the quantum computer program, for the first time the true quantum mechanical nature of the device was confirmed at every step of the experiment. Pushing this envelope and identifying the best, most scalable architecture for a quantum computer is a very active area of research, with teams around the world working on a diverse range of technologies: photons, ions in silicon, atoms or ions in vacuum chambers, and superconducting electrical circuits to name just a few. The Australian-Canadian team are part of two international efforts to make a quantum computer: the Australian Centre for Quantum Computer Technology, led by Prof. Robert Clark at the University of New South Wales, and the US program for Optical Quantum Computing, led by Prof. Paul Kwiat at the University of Illinois.

Almost sixty years ago to the day, the team of Bardeen, Brattain, and Shockley revealed the first transistor to the world, an ungainly device consisting of a wire whisker touching a chunk of metal. Now millions of times smaller, transistors are found by the billions in applications undreamed of by the original inventors: from cell phones in the middle of Africa to iPods at the local bus stop. Functional large-scale quantum computers may be as many years away as the transistor is from the modern computer, and it is equally hard to know how they will change the world—but change our world they will.