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

http://quantum.info/shors/).

**Contact**:

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”

http://technology.newscientist.com/article/mg19526216.700

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

http://www.sciencenews.org/articles/20071208/fob4.asp

Innovations report: “Quantum computer breakthrough”

http://www.innovations-report.de/html/berichte/physik_astronomie/bericht-99247.html

Slashdot: “Time running out for public key encryption”

http://it.slashdot.org/article.pl?sid=07/09/13/1720251

The Register: “Quantum computing spectre looms over ecommerce”

http://www.theregister.co.uk/2007/09/14/quantum_computing

darkREADING: “Quantum research could threaten encryption schemes”

http://www.darkreading.com/document.asp?doc_id=133847&f_src=darkreading_default