The computation calculates the prime factors of 15 to output the answer 3 and 5. Although it sounds simple, finding prime factors is a crucial part of modern encryption schemes, such as those employed for secure internet communications.

While classical computers store and process information as "bits" that can have one of two states – "0" or "1", a quantum computer exploits the ability of quantum particles to be in "superposition" of two or more states at the same time. Such a device could, in principle, outperform a classical computer, potentially storing and processing huge amounts of data extremely quickly. Quantum particles can also become entangled. This allows them to share a much closer relationship than classical mechanics allows, so data is transferred instantaneously between entangled particles regardless of how far apart they are.

Ideal qubits
Photons are ideal for use as quantum bits, or qubits, in a quantum computer because they can travel great distances through optical fibres or even air without losing their quantum nature. This is because individual photons do not normally interact with each other. However, this also means that it is difficult to make devices for processing quantum information, such as logic gates, which rely on two or more photons interacting.

In 2003 Jeremy O'Brien with colleagues at the University of Queensland, Australia, overcame this problem by building the first controlled NOT (CNOT) quantum logic gate for single photons. A CNOT gate has two inputs – "target" and "control" – and is thought to be a fundamental building block of any quantum computer. However, this first gate was made using conventional optical components, such as mirrors and beam splitters, and took up an entire laboratory bench.

A newer version, developed last year, contained hundreds of versions of the same CNOT gate in a piece of silicon just a millimetre in size. This device used coupled waveguides – micron-wide channels of transparent silica that can be grown on silicon substrates using well established industrial processes – instead of mirrors and beam splitters.

First maths calculation
The team has now taken this work a step further by making the device perform the first mathematical calculation (Science 325 1221). Four photons travel through the waveguides and structures called H gates then prepare each qubit in a superposition of 0 and 1, so that the entire state is a superposition of all four-bit inputs. The calculation is then performed by two other, CZ, gates that create a highly entangled output state. Measuring the output states of the first two qubits produces the results of the calculation.

The computation is done using Shor's algorithm, named for mathematician Peter Shor who invented it in 1994. In his work Shor predicted that quantum computers could factor numbers exponentially faster than their classical counterparts.

"Although this task could be done much faster by any school kid, ours is a really important proof-of-principle demonstration," said team member Alberto Politi of the University of Bristol.

"The really exciting thing about the result is that it will enable the development of large scale quantum circuits, which opens up all kinds of possibilities," added O'Brien.

"Just add qubits"
"This certainly is an interesting and important result," commented Boris Blinov of the University of Washington, who was not involved in the study. "Integration will be crucial for any successful quantum information technology and here we witness a major step forward in integrating components of a linear-optical quantum processor. It's a really nice technology – the quantum logic gates are literally built, and all you have to do is just add qubits. And the gate fabrication process seems readily scalable to much larger arrays for more complicated computational tasks (than finding the prime factors of number 15!)"

The "just adding qubits" part could be more complicated than we think though, he stresses, because reliable sources of single photons will be needed – something that is still difficult to achieve. A potential solution could be to combine the linear-optical quantum processor with qubits other than photons. "These include trapped ions or quantum dots – the future of this technology," Blinov told nanotechweb.org.