APS » PROLA » Phys. Rev. A » Volume 66 » Issue 3
< Previous article | Next article >

Phys. Rev. A 66, 032314 (2002) [8 pages]

Quantum search by measurement

Download: PDF (102 kB) or Buy this Article (Use Article Pack) Export: BibTeX or EndNote (RIS)

Andrew M. Childs *, Enrico Deotto †, Edward Farhi ‡, and Jeffrey Goldstone §
Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Sam Gutmann **
Department of Mathematics, Northeastern University, Boston, Massachusetts 02115

Andrew J. Landahl ††
Institute for Quantum Information, California Institute of Technology, Pasadena, California 91125

Received 11 April 2002; published 23 September 2002

We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a time-varying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover’s unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms.


©2002 The American Physical Society

URL: http://link.aps.org/doi/10.1103/PhysRevA.66.032314
DOI: 10.1103/PhysRevA.66.032314
PACS: 03.67.Lx, 03.65.Xp

* Electronic address: amchilds@mit.edu
† Electronic address: deotto@mitlns.mit.edu
‡ Electronic address: farhi@mit.edu
§ Electronic address: goldston@mit.edu
** Electronic address: sgutm@neu.edu
†† Electronic address: alandahl@caltech.edu

[ Abstract  |  Previous article  |  Next article  |  Issue 3 ]