Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
arXiv:1004.2226
Abstract
The problem Hamiltonian of the adiabatic quantum algorithm for the maximum-weight independent set problem (MIS) that is based on the reduction to the Ising problem (as described in [Choi08]) has flexible parameters. We show that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS on CK graphs, we can prevent the first order quantum phase transition and significantly change the minimum spectral gap. We raise the basic question about what the appropriate formulation of adiabatic running time should be. We also describe adiabatic quantum algorithms for Exact Cover and 3SAT in which the problem Hamiltonians are based on the reduction to MIS. We point out that the argument in Altshuler et al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithm failed with high probability for randomly generated instances of Exact Cover does not carry over to this new algorithm.
20 pages, 7 figures, 2 tables
References in corpus (13)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- First order phase transition in the Quantum Adiabatic Algorithm
- Error correcting codes for adiabatic quantum computation
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
- Sufficiency Criterion for the Validity of the Adiabatic Approximation
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Quantum Adiabatic Evolution Algorithms with Different Paths
- An Elementary Proof of the Quantum Adiabatic Theorem
- Validity of the Adiabatic Approximation
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
- Adiabatic theorems for linear and nonlinear Hamiltonians
- The role of symmetries in adiabatic quantum algorithms
Cited by in corpus (14)
- Ising formulations of many NP problems
- Adiabatic Quantum Computing
- Simulating chemistry using quantum computers
- Adiabatic Quantum Simulation of Quantum Chemistry
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
- An energetic perspective on rapid quenches in quantum annealing
- Encoding-Independent Optimization Problem Formulation for Quantum Computing
- Monte Carlo Search for Very Hard KSAT Realizations for Use in Quantum Annealing
- Using copies to improve precision in continuous-time quantum computing
- Decoding quantum error correction with Ising model hardware
- Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
- Quantum Searches in a Hard 2SAT Ensemble
- An Overview of Approaches to Modernize Quantum Annealing Using Local Searches
- Approximate Approximation on a Quantum Annealer