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

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

2010-10-06

arxiv.org/abs/1010.1221v3

Quantum Information and Computation, Vol. 11, No. 7&8 (2011) 0638-0648

Physics

Quantum Physics

This is the second part of article arXiv:quant-ph/1004.2226. References added

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-428408