A quantum computer made of five trapped ions has been used by physicists in Austria and the US to implement Shor’s factoring algorithm. While the system performed the trivial task of factoring the number 15, the researchers say that it could be scaled-up to factor much larger numbers. It is the first implementation of Shor’s algorithm in which prior knowledge of the factors was not used to simplify the computational procedure.

Finding the integer factors of a large odd number is a very time-consuming problem. While some numbers are easier to factor than others, there is no known algorithm that can factor all numbers efficiently. As a result, large numbers and their factors are used in some cryptography systems – and this makes such systems vulnerable to anyone who can come up with an efficient factoring algorithm.

Periodic problem

In 1994, Peter Shor realized that a quantum computer could be much more efficient at factoring large numbers than a conventional computer. Shor’s factoring algorithm begins by using mathematics to transform the problem of factoring a large number into the problem of finding the period of a function that describes a sequence of numbers. Then a quantum computer calculates the period using a quantum Fourier transform. Mathematics is then used to convert this period into the two factors.

In Shor’s original scheme, a quantum computer with 12 quantum bits (qubits) is needed to factor the number 15. While this might not seem like many, creating a functioning quantum computer with this many qubits is beyond the current capability of physicists. However, in 1995, Alexei Kitaev pointed out that the algorithm can be run with fewer qubits (five qubits when factoring 15) if the answer is output one qubit at a time.

This latest work was done by Thomas Monz and colleagues at the University of Innsbruck, and Isaac Chuang and team at the Massachusetts Institute of Technology. Using five trapped calcium-40 ions as qubits, the collaboration used Kitaev’s version of Shor’s algorithm to factor the number 15.

Laser addressing

Their quantum computer comprises a linear Paul trap in which an electric field holds the five ions in a row. The ions are separated by 5 μm, and each ion can be in one of two spin states, which correspond to qubit values of “0” and “1”. Each ion can be addressed individually using a laser with a spot width of just 1 μm.

The quantum calculation begins by loading the periodic function into four qubits of the quantum computer. Then the quantum Fourier transform is done by firing sequences of laser pulses at individual ions. Four qubits are used to perform the quantum calculation, while the fifth is used to transfer information within the computer and also to output the result one qubit at a time.

Although the output of a single calculation was not perfect, it did allow the user to deduce the factors of the number. However, if a calculation is repeated eight times, the uncertainty in the result drops to below 1%.

Scalable computer

Monz told physicsworld.com that all of the processes used in their implementation of Shor’s algorithm can be scaled-up to factor larger numbers. However, this would require a scalable quantum computer. “Our current linear Paul trap would need to be replaced with a segmented trap,” he explains. “We have those in the lab already, but they are (despite being scalable) harder to control and at an earlier stage of development than our linear Paul trap.”

Indeed, Monz says that the team is now focussing on improving the fidelity of its quantum computer by using better lasers, reducing background noise and gaining better control over magnetic fields.

Barry Sanders of the University of Calgary in Canada believes that the importance of this work by Monz and colleagues is that they did not exploit prior knowledge of the factors of 15 in designing their computational procedure. “Previous experiments used such knowledge and thereby oversimplified the circuit,” he explains.

The calculations are described in Science.

• Peter Shor explains how his eponymous algorithm works in this 100 Second Science Video