Content area
Full Text
LETTERS
PUBLISHED ONLINE: 21 OCTOBER 2012 | http://www.nature.com/doifinder/10.1038/nphoton.2012.259
Web End =DOI: 10.1038/NPHOTON.2012.259
Experimental realization of Shors quantum factoring algorithm using qubit recycling
Enrique Martn-Lpez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou and Jeremy L. OBrien*
Quantum computational algorithms exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms13. Shors quantum algorithm4 for fast number factoring is a key example and the prime motivator in the international effort to realize a quantum computer5. However, due to the substantial resource requirement, to date there have been only four small-scale demonstrations69. Here, we address
this resource demand and demonstrate a scalable version of Shors algorithm in which the n-qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one-third of that required in the standard protocol10,11. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N 5 21. The algorithmic output is distinguishable from noise, in contrast to previous demonstrations. These results point to larger-scale implementations of Shors algorithm by harnessing scalable resource reductions applicable to all physical architectures.
Shors factoring algorithm consists of a quantum order-nding algorithm, preceded and succeeded by various classical routines. While the classical tasks are known to be efcient on a classical computer, order nding is understood to be intractable classically. However, it is known that this part of the algorithm can be performed efciently on a quantum computer. To determine the prime factors of an odd integer N, one chooses a co-prime of N, x. The order r relates x to N according to xrmod N 1, and
can be used to obtain the factors given by the greatest common
divisor gcd(xr/2+1,N).
The quantum order-nding circuit involves two registers: a work register and a control register. In the standard protocol, the work register performs modular arithmetic with m log2 N qubits,
enough to encode the number N, and the n-qubit control register provides the algorithmic output, with n bits of precision.
Measuring the control register in the computational basis will yield a result of k2n/r, where k is an integer between 0 and r 2 1, with the value of k occurring probabilistically. Dividing the result by 2n gives the rst n...