Physics – Quantum Physics
Scientific paper
2004-09-15
Phys. Rev. A 71 052324 (2005)
Physics
Quantum Physics
9 pages, 7 figures
Scientific paper
10.1103/PhysRevA.71.052324
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 non-adiabatic 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.
Adami Christoph
Lue Waynn
Mitchell David R.
Williams Colin P.
No associations
LandOfFree
A Random Matrix Model of Adiabatic Quantum Computing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Random Matrix Model of Adiabatic Quantum Computing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Random Matrix Model of Adiabatic Quantum Computing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-622076