| Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. | |
| | |
MedLine Citation:
|
PMID: 22304085 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm. |
| | |
Authors:
|
Itay Hen; A P Young |
Related Documents
:
|
17342605 - Antibiotics from algae xxxvii. rhodomelol and methylrhodomelol from polysiphonia lanosa1. 7497395 - Psychologic scars remain 50 years after dieppe raid, study of canadian veterans finds. 5636555 - Studies on streptococcal bacteriophages. i. burst size and intracellular growth of grou... 1299705 - Generations and paradigms: mainstreams in lesbian and gay studies. 9865035 - Metaphrase: an aid to the clinical conceptualization and formalization of patient probl... 10346255 - The 1997 iahss survey--crime in hospitals. |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-12-29 |
Journal Detail:
|
Title: Physical review. E, Statistical, nonlinear, and soft matter physics Volume: 84 ISSN: 1550-2376 ISO Abbreviation: - Publication Date: 2011 Dec |
Date Detail:
|
Created Date: 2012-2-6 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101136452 Medline TA: Phys Rev E Stat Nonlin Soft Matter Phys Country: - |
Other Details:
|
Languages: ENG Pagination: 061152 Citation Subset: - |
Affiliation:
|
Department of Physics, University of California, Santa Cruz, California 95064, USA. |
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: Self-consistent inhomogeneous steady states in Hamiltonian mean-field dynamics.
Next Document: Bounds and correlation approximation for the effective conductivity of heterogeneous plates.