Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems

Understand

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.