Quantum information processing in continuous time

Quantum mechanical computers can solve certain problems asymptotically faster than any classical computing device. Several fast quantum algorithms are known, but the nature of quantum speedup is not well understood, and inventing new quantum algorithms seems to be difficult. In this thesis, we explore two approaches to designing quantum algorithms based on continuous-time Hamiltonian dynamics. In quantum computation by adiabatic evolution, the computer is prepared in the known ground state of a simple Hamiltonian, which is slowly modified so that its ground state encodes the solution to a problem. We argue that this approach should be inherently robust against low-temperature thermal noise and certain control errors, and we support this claim using simulations. We then show that any adiabatic algorithm can be implemented in a different way, using only a sequence of measurements of the Hamiltonian. We illustrate how this approach can achieve quadratic speedup for the unstructured search problem. We also demonstrate two examples of quantum speedup by quantum walk, a quantum mechanical analog of random walk. First, we consider the problem of searching a region of space for a marked item. Whereas a classical algorithm for this problem requires time proportional to the number of items regardless of the geometry, we show that a simple quantum walk algorithm can find the marked item quadratically faster for a lattice of dimension greater than four, and almost quadratically faster for a four-dimensional lattice. We also show that by endowing the walk with spin degrees of freedom, the critical dimension can be lowered to two. Second, we construct an oracular problem that a quantum walk can solve exponentially faster than any classical algorithm.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Physics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Childs, Andrew MacGregor, 1977-

Advisor dc:contributor.advisor

• Edward H. Farhi.

• Physics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/16663

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/16663