Random matrix model of adiabatic quantum computing

DOI10.1103/PHYSREVA.71.052324MaRDI QIDQ3102395zbMATH OpenWikidataFDO

Authors David R. Mitchell, Christoph Adami, Waynn Lue, Colin P. Williams

Publication date 4 December 2011

Published in Physical Review A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0409088

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Quantum computation (81P68)

Abstract: 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.

Recommendations

• Random matrix approach to quantum adiabatic evolution algorithms
• scientific article; zbMATH DE number 1984609
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• The complexity of the quantum adiabatic algorithm
• HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL

Cites work

• A machine program for theorem-proving
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• scientific article; zbMATH DE number 51346 (Why is no real title available?)
• Non-adiabatic crossing of energy levels
• Nuclear Constitution and the Interpretation of Fission Phenomena
• Random Matrices in Physics
• Review of thek-body embedded ensembles of Gaussian random matrices
• Strengths and Weaknesses of Quantum Computing

Cited in

(11)

• Adiabatic elimination in quantum stochastic models
• Realistic cost for the model of coherent computing
• Unstructured randomness, small gaps and localization
• Random matrix approach to quantum adiabatic evolution algorithms
• Noise resistance of adiabatic quantum computation using random matrix theory
• Eigenpath traversal by phase randomization
• SIMULATION OF QUANTUM ADIABATIC SEARCH IN THE PRESENCE OF NOISE
• On the Hamiltonian operators for adiabatic quantum reduction of SAT
• scientific article; zbMATH DE number 1984609 (Why is no real title available?)
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• A study of heuristic guesses for adiabatic quantum computation

This page was built for publication: Random matrix model of adiabatic quantum computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3102395)