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

Abstract

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.

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

Cited by in corpus (13)

• Adiabatic Quantum Computing
• Quantum algorithms: an overview
• An energetic perspective on rapid quenches in quantum annealing
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Quantum annealing in spin-boson model: from a perturbative to a ultrastrong mediated coupling
• Bounding first-order quantum phase transitions in adiabatic quantum computing
• Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians
• Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions
• Energy Spectrum and Exact Cover in an Extended Quantum Ising Model