ar X iv :q ua nt -p h/ 01 12 17 6v 1 3 0 D ec 2 00 1 Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance Lieven M.K. Vandersypen†,∗, Matthias Steffen∗,†, Gregory Breyta†, Costantino S. Yannoni†, Mark H. Sherwood† and Isaac L. Chuang∗,† † IBM Almaden Research Center, San Jose, CA 95120 ∗ Solid State and Photonics Laboratory, Stanford University, Stanford, CA 94305-4075 1 2 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 algo- rithms [1] known at present. Factoring large integers is therefore conjectured to be intractable classically, an observation underlying the security of widely used crypto- graphic codes [1, 2]. Quantum computers [3], however, could factor integers in only polynomial time, using Shor’s quantum factoring algorithm [4, 5, 6]. Although im- portant for the study of quantum compu
