| Does Adiabatic Quantum Optimization Fail for NP-Complete Problems? | |
| | |
MedLine Citation:
|
PMID: 21405383 Owner: NLM Status: In-Data-Review |
Abstract/OtherAbstract:
|
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time. |
| | |
Authors:
|
Neil G Dickson; M H S Amin |
Related Documents
:
|
21308403 - Individuals at the center of biology: rudolf leuckart's polymorphismus der individuen a... 21342543 - An ilp solution for the gene duplication problem. 14752893 - Hiv/aids among african americans and us women: minority and young women. |
Publication Detail:
|
Type: Journal Article Date: 2011-02-02 |
Journal Detail:
|
Title: Physical review letters Volume: 106 ISSN: 1079-7114 ISO Abbreviation: Phys. Rev. Lett. Publication Date: 2011 Feb |
Date Detail:
|
Created Date: 2011-03-16 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 0401141 Medline TA: Phys Rev Lett Country: United States |
Other Details:
|
Languages: eng Pagination: 050502 Citation Subset: IM |
Affiliation:
|
D-Wave Systems, Inc., 100-4401 Still Creek Drive, Burnaby, British Columbia, V5C 6G9, Canada. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Modular entanglement.
Next Document: Next-to-Leading-Order QCD Corrections to W^{+}W^{-}bb[over ¯] Production at Hadron Colliders.