Mitchell, David R. and Adami, Christoph and Lue, Waynn and Williams, Colin P. (2005) Random matrix model of adiabatic quantum computing. Physical Review A, 71 (5). Art. No. 052324. ISSN 1050-2947. http://resolver.caltech.edu/CaltechAUTHORS:MITpra05
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:MITpra05
We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3-SAT (an NP-complete problem) in terms of random matrix theory (RMT). We determine the global regularity of the spectral fluctuations of the instantaneous Hamiltonians encountered during the interpolation between the starting Hamiltonians and the ones whose ground states encode the solutions to the computational problems of interest. At each interpolation point, we quantify the degree of regularity of the average spectral distribution via its Brody parameter, a measure that distinguishes regular (i.e., Poissonian) from chaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor spacings. We find that for hard problem instances-i.e., those having a critical ratio of clauses to variables-the spectral fluctuations typically become irregular across a contiguous region of the interpolation parameter, while the spectrum is regular for easy instances. Within the hard region, RMT may be applied to obtain a mathematical model of the probability of avoided level crossings and concomitant failure rate of the adiabatic algorithm due to nonadiabatic Landau-Zener-type transitions. Our model predicts that if the interpolation is performed at a uniform rate, the average failure rate of the quantum adiabatic algorithm, when averaged over hard problem instances, scales exponentially with increasing problem size.
|Additional Information:||©2005 The American Physical Society. Received 15 September 2004; published 20 May 2005. The research described in this paper was performed at the Jet Propulsion Laboratory (JPL), California Institute of Technology, under contract with the National Aeronautics and Space Administration (NASA). We thank the JPL Supercomputing Project for the use of the Cray supercomputer used in computations. D.M. received support through from NASA. C.P.W. thanks the Advanced Research and Development Activity and the National Security Agency for support. C.A. is supported by the Army Research Office’s Grant No. DAAD19-03-1-0207.|
|Subject Keywords:||quantum computing; fluctuations; interpolation; ground states; chaos; energy level crossing; probability|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||06 Mar 2006|
|Last Modified:||18 Mar 2015 22:14|
Repository Staff Only: item control page