Phys. Rev. A 72, 052336 (2005) [7 pages]Eigenlevel statistics of the quantum adiabatic algorithmReceived 18 July 2005; published 30 November 2005 We study the eigenlevel spectrum of quantum adiabatic algorithm for 3-satisfiability problem, focusing on single-solution instances. The properties of the ground state and the associated gap, crucial for determining the running time of the algorithm, are found to be far from the predictions of random matrix theory. The distribution of gaps between the ground and the first excited state shows an abundance of small gaps. Eigenstates from the central part of the spectrum are, on the other hand, well described by random matrix theory. © 2005 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevA.72.052336
DOI:
10.1103/PhysRevA.72.052336
PACS:
03.67.Lx, 05.45.Mt
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.