Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Bulletin of the American Physical Society

Quantum Phase Transitions and Typical Case, Polynomial Time Solution of Randomly Generated NP-Complete Problems via Adiabatic Quantum Computation

William M. Kaminsky, Seth Lloyd

Published Mar 16, 2006• 0 citations
OpenAlex

Related papers

Adiabatic quantum computation and quantum phase transitions (5 pages)

José Ignacio Latorre

Physical Review A•Jan 1, 2004•0 citations

Different adiabatic quantum optimization algorithms for the NP-complete exact cover problem

Vicky Choi

One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.

arXiv:1010.1221•Proceedings of the National Academy of Sciences•Jan 28, 2011•38 citations

Quantum Phase Transition and complexity of adiabatic quantum algorithm for Constraint Satisfaction problem

Sergei Knysh, Vadim Smelyanskiy

Bulletin of the American Physical Society•Mar 16, 2006•0 citations

Different adiabatic quantum optimization algorithms

Vicky Choi

One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van-Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.

Quantum Information and Computation•Jul 1, 2011•18 citations

A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.

arXiv:quant-ph/0007071•Jul 19, 2000•44 citations

Adiabatic Quantum Computation and the Theory of Quantum Phase Transitions

William M. Kaminsky, Seth Lloyd

Bulletin of the American Physical Society•Mar 8, 2007•0 citations
One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.
One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van-Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.