Abstract
Shor’s quantum factoring algorithm finds the prime factors of a large number exponentially faster than any other known method, a task that lies at the heart of modern information security, particularly on the Internet. This algorithm requires a quantum computer, a device that harnesses the massive parellism afforded by quantum superposition and entanglement of quantum bits (or qubits). We report the demonstration of a compiled version of Shor’s algorithm on an integrated waveguide silicaonsilicon chip that guides four singlephoton qubits through the computation to factor 15.
The realization of a quantum computer presents an exciting prospect of modern science. The processing of information encoded in quantum systems admitting quantum superposition and entanglement enables exponentially greater power for particular tasks. Originally conceived in the context of simulating complex quantum systems, it was the development of Shor’s quantum factoring algorithm (1) that showed the capability of factoring the product of two large prime numbers exponentially faster than any known conventional method (2), which has ignited efforts to fabricate such a device.
Despite progress toward this goal, proofofprinciple demonstrations of Shor’s algorithm have so far only been possible with liquidstate nuclear magnetic resonance (3) and bulk optical implementations of simplified logic gates (4, 5), owing to the need for several logic gates operating on several qubits, even for smallscale compiled versions. However, these approaches cannot be scaled to a large number of qubits because of purity, size, and stability limitations of these systems. We demonstrate a compiled version of Shor’s algorithm operating on four qubits in which the processing occurs in a photonic circuit of several one and twoqubit gates fabricated from integrated optical waveguides on a silicaonsilicon chip (6, 7). Whereas the full Shor’s algorithm is designed to factorize any given input, a compiled version is designed to find the prime factors of a specific input.
The quantum circuit our device implements is the compiled version of Shor’s algorithm for factorizing 15 (3–5) (Fig. 1A). This algorithm uses five qubits, one of which, x_{0}, is effectively redundant because it remains in a separable state throughout. The physical implementation (Fig. 1B) consists of two nondeterministic controlledphase (CZ) gates (each with success P = 1/9, conditional on post selection) and six onequbit Hadamard (H) gates (8). The computation proceeds as follows (Fig. 1, A and B): Four photons are input into the “0” or “1” waveguides to prepare the initial state
We simultaneously prepared four 790nm photons via parametric down conversion, coupled them into and out of the chip with buttcoupled arrays of optical fibers, and detected them with silicon avalanche photo diodes at a typical coincidental rate of 100 Hz per measurement (integrated for 30 s). We input the state ψ_{in}〉 and measured the output state of qubits x_{1} and x_{2}; the output statistics (Fig. 1C) show the four binary outcomes: 000, 010, 100, and 110 (including the x_{0} qubit). Outputs 010 and 110 lead to the correct calculation for finding the order r = 4 for the algorithm (9), which then enables efficient classical computation of the factors 3 and 5; 100 gives the trivial factors (1 and 15); and 000 is an expected failure mode inherent to Shor’s algorithm. The measured results have a fidelity of 99 ± 1% with the ideal probability distribution (dashed line).
This demonstration of a smallscale compiled Shor’s algorithm on a chip shows promise for quantum computing in integrated waveguides. Although it currently uses an inefficient single photon source and modest efficiency detectors, ongoing progress to address heralded gates and efficient sources and detectors (8) combined with the results presented here will allow largescale quantum circuits on many qubits to be implemented. Any quantum computer is a manyparticle, manypath interferometer; the capability to implement such complex interferometers in a stable and miniaturized architecture is therefore critical to the future realization of largescale quantum algorithms.
Supporting Online Material
www.sciencemag.org/cgi/content/full/325/5945/1221/DC1
Materials and Methods
Fig. S1

↵* These authors contributed equally to this work.
References and Notes
 ↵
 ↵ This task lies at the heart of cryptographic security.
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵ Materials and methods are available as supporting material on Science Online.
 We thank R. Jozsa, A. Laing, A. Montanaro, S. Takeuchi, M. G. Thompson, and X.Q. Zhou for helpful discussions. This work was supported by Engineering and Physical Sciences Research Council, Quantum Information Processing Interdisciplinary Research Collaboration, Intelligence Advanced Research Projects Activity, and the Leverhulme Trust. J.L.O’B. acknowledges a Royal Society Wolfson Merit Award.