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 10502947. http://resolver.caltech.edu/CaltechAUTHORS:MITpra05

PDF
 Published Version
See Usage Policy. 450Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:MITpra05
Abstract
We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3SAT (an NPcomplete 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., Wignertype) distributions of normalized nearestneighbor spacings. We find that for hard problem instancesi.e., those having a critical ratio of clauses to variablesthe 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 LandauZenertype 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.
Item Type:  Article  

ORCID: 
 
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. DAAD190310207.  
Subject Keywords:  quantum computing; fluctuations; interpolation; ground states; chaos; energy level crossing; probability  
Record Number:  CaltechAUTHORS:MITpra05  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:MITpra05  
Alternative URL:  http://dx.doi.org/10.1103/PhysRevA.71.052324  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  2059  
Collection:  CaltechAUTHORS  
Deposited By:  Tony Diaz  
Deposited On:  06 Mar 2006  
Last Modified:  18 Mar 2015 22:14 
Repository Staff Only: item control page