An evaluation of the performance of the quantum adiabatic algorithm on random instances of k-SAT

A quantum computational framework has been developed based on the adiabatic theorem. The theorem guarantees that a system with a time dependent Hamiltonian that is placed into its ground state will remain in its ground state provided that the Hamiltonian of the system varies slowly enough with time. This work investigates the performance of the quantum adiabatic algorithm on random instances of k-SAT. The performance of the algorithm is examined on subsets of k-SAT that are classically easy and on subsets that are classically difficult. The evaluation attempts to determine how the typical time required to solve the problems grows with the size of the problems. This evaluation is done by directly determining the required time from numerical integration of the dynamics of the system and by inferring this time using a result from the adiabatic theorem. This evaluation considers quantum systems composed of up to 23 bits and is performed on several large scale Beowulf clusters. As was seen in previous work, the direct integration studies show what appears to be only a quadratic growth rate in the required running time with the number of bits in problems that classically require exponential time. However, further studies show that these effects are caused by polynomial bounded matrix elements and are not indicative of the asymptotic behavior of the performance of the algorithm. The real asymptotic scaling of the performance of the algorithm is controlled by the ground state energy gap. When this is examined directly it is not currently possible to determine whether the growth rate of the running time of the algorithm is exponential or polynomial.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Physics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2002

Author dc:creator

• McBride, James, 1973-

Advisor dc:contributor.advisor

• Edward 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/29934

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/29934