20 December 2001. Thanks to SD.

Related news reports:

http://www.nytimes.com/2001/12/20/science/20QUAN.html

See also Lov Grover's excellent description of quantum computing:

http://cryptome.org/qc-grover.htm

*Nature* magazine has published
today:

**by Lieven M. K. Vandersypen*†, Matthias Steffen*†, Gregory
Breyta*, Costantino S. Yannoni*, Mark H. Sherwood* & Isaac L.
Chuang*†**

* IBM Almaden Research Center, San Jose, California 95120, USA

† Solid State and Photonics Laboratory, Stanford University, Stanford,
California 94305-4075, USA

[Abstract]

The number of steps any classical computer requires in order to find the
prime factors of an *l*-digit integer *N* increases exponentially
with *l*, at least using algorithms known at
present^{1}. Factoring large integers is therefore
conjectured to be intractable classically, an observation underlying the
security of widely used cryptographic codes^{1,
2}. Quantum
computers^{3}, however, could factor integers in
only polynomial time, using Shor's quantum factoring
algorithm^{4-6}. Although important for the study
of quantum computers^{7}, experimental demonstration
of this algorithm has proved elusive^{8-10}. Here
we report an implementation of the simplest instance of Shor's algorithm:
factorization of *N* = 15 (whose prime factors are 3 and 5). We use
seven spin-1/2 nuclei in a molecule as quantum
bits^{11, 12}, which can be
manipulated with room temperature liquid-state nuclear magnetic resonance
techniques. This method of using nuclei to store quantum information is in
principle scalable to systems containing many quantum
bits^{13}, but such scalability is not implied
by the present work. The significance of our work lies in the demonstration
of experimental and theoretical techniques for precise control and modelling
of complex quantum computers. In particular, we present a simple, parameter-free
but predictive model of decoherence
effects^{14} in our system.

**References**

1. | Knuth,
D. E. The Art of Computer Programming Vol. 2 (Addison-Wesley, Reading, Massachusetts, 1998)., Seminumerical
Algorithms |

2. | Koblitz,
N. A Course in Number Theory and Cryptography (Springer, New York,
1994). |

3. | Bennett,
C. H. & DiVincenzo, D. P. Quantum information and computation.
Nature 404, 247-255
(2000). | Article | PubMed | ISI | |

4. | Shor,
P. in Proc. 35th Annu. Symp. on the Foundations of Computer Science
(ed. Goldwasser, S.) 124-134 (IEEE Computer Society Press, Los Alamitos,
California, 1994). |

5. | Shor,
P. Polynomial-time algorithms for prime factorization and discrete logarithms
on a quantum computer. SIAM J. Comput. 26, 1484-1509
(1997). | ISI | |

6. | Ekert,
A. & Jozsa, R. Quantum computation and Shor's factoring algorithm. Rev.
Mod. Phys. 68(3), 733-753
(1996). | ISI | |

7. | Beckman,
D., Chari, A. N., Devabhaktuni, S. & Preskill, J. Efficient networks
for quantum factoring. Phys. Rev. A 54, 1034-1063
(1996). | Article | PubMed | ISI | |

8. | Jones,
J. A. NMR quantum computation. Prog. NMR Spectrosc. 38, 325-360
(2001). | ISI | |

9. | Vandersypen,
L. M. K. et al. Experimental realization of an order-finding algorithm
with an NMR quantum computer. Phys. Rev. Lett. 85, 5452-5455
(2000). | Article | PubMed | ISI | |

10. | Knill,
E., Laflamme, R., Martinez, R. & Tseng, C.-H. An algorithmic benchmark
for quantum information processing. Nature 404, 368-370
(2000). | Article | PubMed | ISI | |

11. | Gershenfeld,
N. & Chuang, I. L. Bulk spin-resonance quantum computation.
Science 275, 350-356
(1997). | Article | PubMed | ISI | |

12. | Cory,
D. G., Fahmy, A. F. & Havel, T. F. Ensemble quantum computing by NMR
spectroscopy. Proc. Natl Acad. Sci. 94, 1634-1639
(1997). | PubMed | ISI | |

13. | Schulman,
L. & Vazirani, U. in Proc. 31st ACM Symp. on Theory of Computing
322-329 (Association for Computing Machinery, New York, 1999). |

14. | Chuang,
I. L., Laflamme, R., Shor, P. & Zurek, W. H. Quantum computers, factoring,
and decoherence. Science 270, 1633-1635
(1995). | ISI | |

**Acknowledgements.**
We thank X. Zhou and J. Preskill for discussions, J. Smolin for the use of
his IBM workstation, D. Miller for help with spectral analysis, A. Schwartz
and his team for their technical assistance, and J. Harris, W. Risk and H.
Coufal for their support. L.V. acknowledges a Yansouni Family Stanford graduate
fellowship. This work was supported in part by the QuARC project under a
DARPA Quantum Information Science and Technology grant.

Cryptome has purchased a copy of the 5-page article for $15.00 and makes
it available to those who cannot afford to buy it -- but only until
*Nature*, a most distinguished public interest journal, politely asks
to stop doing it.

http://cryptome.org/shor-nature.pdf (390KB)