Shor’s Quantum Factoring Algorithm on a Photonic Chip

See allHide authors and affiliations

Science  04 Sep 2009:
Vol. 325, Issue 5945, pp. 1221
DOI: 10.1126/science.1173731


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 silica-on-silicon chip that guides four single-photon 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, proof-of-principle demonstrations of Shor’s algorithm have so far only been possible with liquid-state 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 small-scale 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 two-qubit gates fabricated from integrated optical waveguides on a silica-on-silicon 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 (35) (Fig. 1A). This algorithm uses five qubits, one of which, x0, is effectively redundant because it remains in a separable state throughout. The physical implementation (Fig. 1B) consists of two nondeterministic controlled-phase (CZ) gates (each with success P = 1/9, conditional on post selection) and six one-qubit 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 |ψin=|0x1|0x2|0f1|1f2 (this does not represent 15 but rather the initialization for the compiled algorithm to compute the factors of 15). The H gates, implemented by 1/2 reflectivity directional couplers, then prepare each qubit in a superposition of 0 and 1, such that the entire state is a superposition of all possible four-bit inputs—part of the massive parallelism that gives rise to quantum speed-up. The core process is then performed by two independent CZ gates, each implemented by a network of three 1/3 directional couplers, that create a highly entangled output state (4, 5). Measurement of the output state of qubits x1 and x2 and classical processing give the results of the computation (9).

Fig. 1

Integrated optical implementation of Shor’s quantum factoring algorithm. (A) The quantum circuit. QFT indicates quantum Fourier transform (9); CNOT, two qubit controlled NOT. (B) Schematic of the waveguide on chip device that implements the quantum computation. The xn qubits carry the result of the algorithm; fn are additional qubits required for the computation to work. (C) Outcomes of the algorithm.

We simultaneously prepared four 790-nm photons via parametric down conversion, coupled them into and out of the chip with butt-coupled 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 x1 and x2; the output statistics (Fig. 1C) show the four binary outcomes: 000, 010, 100, and 110 (including the x0 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 small-scale 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 large-scale quantum circuits on many qubits to be implemented. Any quantum computer is a many-particle, many-path interferometer; the capability to implement such complex interferometers in a stable and miniaturized architecture is therefore critical to the future realization of large-scale quantum algorithms.

Supporting Online Material

Materials and Methods

Fig. S1

  • * These authors contributed equally to this work.

References and Notes

  1. This task lies at the heart of cryptographic security.
  2. Materials and methods are available as supporting material on Science Online.
  3. 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.
View Abstract

Stay Connected to Science

Navigate This Article