Physics – Quantum Physics
Scientific paper
2009-08-19
Physics
Quantum Physics
34 pages, 5 color figures. Significant changes compared to v1, including a new section about Anderson Localization
Scientific paper
Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long.
Altshuler Boris
Krovi Hari
Roland Jérémie
No associations
LandOfFree
Adiabatic quantum optimization fails for random instances of NP-complete problems 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 Adiabatic quantum optimization fails for random instances of NP-complete problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adiabatic quantum optimization fails for random instances of NP-complete problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-216618