English News

Factoring 15 = 3 × 5 performed on a light-based quantum computer

Date: 2007-12-24
C.-Y. Lu et al. Phys. Rev. Lett., 99, 250504 (2007)


Demonstration of a complied version of Shor’s quantum factoring algorithm using photonic qubits
Shor’s algorithm (discovered in 1995 by Peter W. Shor, now professor of MIT), the most spectacular discovery in  quantum computing to date, shows that a quantum computer can factor large composite numbers in polynomial  time while there is no efficient classical solution. It has spurred the interest of quantum computing since 1990s for  at least two reasons. First, it provides the most striking evidence that quantum computers are inherently more  powerful than classical computers. Second, and most importantly from a practical standpoint, this algorithm can  be used as a killer application to break the widely used cryptographic codes, such as the RSA public key  cryptographic system (for more details see en.wikipedia.org/wiki/Shors_algorithm).

Successful implementation of this algorithm in a scalable quantum system is one of the ultimate dreams of  quantum computation. Obviously, currently we have not yet been able to do that. However, the fast-developing  quantum control technique now enables demonstration of the very simplest instance of Shor’s quantum factoring  algorithm, which could prove the underlying principle of this algorithm and provide interesting insights into more- fledged implementation in the future. Toward this goal, in our present work, we have realized the simplest  meaningful instance of Shor’s algorithm, that is, factorization of 15, using single photon qubits (for the first time)  controlled by a linear optical network. This approach of quantum factoring using photons might be promising  because of the photons’ intrinsic advantages such as the robustness against decoherence, the relative ease with  which it can be manipulated with high precision, cheapness, and the in-principle scalability to many qubits.

Compared to the previous pioneering implementation of this algorithm using the liquid-state nuclear magnetic  resonance (NMR) technique (L. Vandersypen et al. Nature 414, 883 (2001) in I. Chuang’s group Standard  University), our work might seem as only an alternative approach, the implications are actually quite profound.
Some issues concerning the NMR experiment have been raised (see e.g. ref. 6 of our manuscript). First, one can  not prepare pure states using the NMR technique. So the situation there is quite different from the original  quantum computation protocols where pure quantum states are used, which makes the quantum nature of NMR  computing a little ambiguous. Second, the NMR computing experiments exhibit no entanglement. However, it is  proved that the presence of entanglement is a necessary condition if the quantum algorithm is to offer the  expected exponential computational speed-up over classical computation. Third, the inherent limitations of the  NMR technique prevent the scaling to many qubits. In our present work, we have made some progresses on  these issues. We have used pure quantum states of single photons as the basic qubits in our experiment, and we  have observed multi-particle quantum interference and genuine entanglement—the very weird phenomenon in  the quantum world—during the computation, which have for the first time well demonstrated the quantum nature  of the implementation of Shor’s algorithm.

However, there is still a long way to go before quantum factoring of real non-trivial large numbers. Although  photonic qubits are in-principle scalable, such scalability is however not directly implied in our proof-of-principle  experiment. The main reason is that, the technique we based on, called as spontaneous parametric down- conversion, produces entangled photons probabilistically. However, this drawback can be overcome by further  technical advances such as on-demand single photons or quantum storage, which are fast-developing. Also,
extensive efforts should be undertaken to the development of high-efficiency single photon detectors, more  complex multiqubit gates and quantum error correction.

Independently, a related work (published on PRL together) was done in Andrew White’s group from the
University  of Queensland using also photons (see their press release at

Professor Jian-Wei Pan (jian-wei.pan(at)physi.uni-heidelberg.de)
Chao-Yang Lu (cylu(at)mail.ustc.edu.cn)
University of Science and Technology of China, Hefei
In collaboration with Dan Browne from University of Oxford, UK

popular media coverage:

New Scientist: “Quantum threat to our secret data”


Science News: “15 = 3 × 5: Photons do their first quantum math”


Innovations report: “Quantum computer breakthrough”


Slashdot: “Time running out for public key encryption”

The Register: “Quantum computing spectre looms over ecommerce”


darkREADING: “Quantum research could threaten encryption schemes”