A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation

A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation

Phys. Rev. Lett. 101, 220405 (2008)

Xinhua Peng1, Zeyang Liao1, Nanyang Xu1, Gan Qin1, Xianyi Zhou1, Dieter Suter2, and Jiangfeng Du1
Hefei National Laboratory for Physical Sciences at Microscale and Department of Modern Physics,
University of Science and Technology of China, Hefei, Anhui 230026, People’s Republic of China and
Fakult¨at Physik, Technische Universit¨at Dortmund, 44221 Dortmund, Germany
(Dated: August 14, 2008)
We propose an adiabatic quantum algorithm capable of factorizing numbers, using fewer qubits
than Shor’s algorithm. We implement the algorithm in an NMR quantum information processor
and experimentally factorize the number 21. Numerical simulations indicate that the running time
grows only quadratically with the number of qubits.
PACS numbers: 87.23.Cc, 05.50.+q, 03.65.Ud




Using quantum mechanical systems as computational devices may be a possible way to build computers that
are qualitatively more powerful than classical computers [1]. The algorithms that are adapted to the special capabilities of these devices are called quantum algorithms.


One of the best known quantum algorithms is Shor’s algorithm for integer factorization [2]. Since no efficient
factorization algorithm is known for classical computers [3], various cryptographic techniques rely on the difficulty
of finding the prime factors of large numbers [4]. However, in 1994, Peter Shor developed a quantum algorithm
that can factorize large numbers in polynomial time [2]. This discovery was one of the main reasons for the subsequent strong interest in quantum computation. An experimental implementation of Shor’s algorithm was
demonstrated by Vandersypen et al. [5], using nuclear spins as qubits to find the prime factors of 15. More recent experiments by Lu et al. [6] and Lanyon et al. [7] used photons as qubits and found the same factors.
While Shor’s algorithm and its experimental implementation are based on the circuit (or network) model
of quantum computing, different models have been proposed later. Here, we consider the adiabatic quantum
computing model proposed by Farhi et al [8], The basis of this model is the quantum adiabatic theorem: A quantum system remains in its instantaneous eigenstate if the system Hamiltonian varies slowly enough and if
there is a gap between this eigenvalue and the rest of the Hamiltonian’s spectrum [9, 10]. It has been proved to be equivalent to the conventional circuit model [11]. Several adiabatic quantum algorithms have been discussed, such as 3SAT and search of unstructured databases [8, 12, 13]. Compared to the network model, the adiabatic scheme appears to offer lower sentivitiy to some perturbations
and thus improved robustness against errors due to dephasing, environmental noise and some unitary control
errors [14, 15].
In this paper, we propose a factorization algorithm that uses the adiabatic approach to quantum information
processing. We also implement this algorithm experimentally, using nuclear spin qubits to factorize the
number 21.



[1] M. A. Nielsen and I . L. Chuang, Quantum Computation
and Quantum Information, Cambridge University Press,
UK, 2000.
[2] P. Shor, in Proc. 35th Annu. Symp. on the Foundations of
Computer Science, editted by S.Goldwasser (IEEE Computer
Society Press, Los Alamitos, California, 1994), p.
124-134.
[3] D.E. Knuth, The Art of Computer Programming Vol.
2, Seminumerical Algorithms (Addison-Wesley Reading,
Massachusetts, 1998).
[4] N. Koblitz, A Course in Number Theory and Cryptography(
Springer, New York, 1994).
[5] L.M.K. Vandersypen et al, Nature 414, 883 (2001).
[6] C. Lu et al, Phys. Rev. Lett 99, 250504 (2007).
[7] B.P. Lanyon et al, Phys. Rev. Lett 99, 250505 (2007).
[8] E. Farhi et al, Science 292, 472 (2001).
[9] A. Messiah, Quantum Mechanics, North-Holland, Amsterdam
1962.
[10] T. Kato, J. Phys. Soc. Jpn. 5, 435 (1950).
[11] A. Mizel, D.A. Lidar and M. Mitchell, Phys. Rev. Lett
99, 070502 (2007).
[12] L.K. Grover, Phys. Rev. Lett 79, 325 (1997).
[13] J. Roland and N.J. Cerf, Phys. Rev. Lett 90, 067903
(2003).
[14] A.M. Childs and E. Farhi, Phys. Rev. A 65, 012322
(2001).
[15] J. Roland and N.J. Cerf, Phys. Rev. A 71, 032330 (2005).
[16] G. Schaller and R. Schutzhold, quant-ph/0708.1882v1
(2007).
[17] E. Farhi and J. Goldstone, “A Numerical Study of the
Performance of a Quantum Adiabatic Evolution Algorithm
for Satisfiability”, quant-ph/0007071v1.
[18] M. Steffen et al, Phys. Rev. A 65, 042308 (2002).
[19] A. Mitra et al, Journal of Magnetic Resonance 177, 285
(2005).
[20] D.G. Cory, A.E Fahmy and T.R Havel, Proc. Natl. Acad.
Sci. 94, 1634 (1997).
[21] N.A. Gershenfeld and I.L. Chuang, Science 275, 350
(1997).
[22] X. Peng, J. Du and D. Suter, Phys. Rev. A 71, 012307