Adiabatic Quantum Computing for Random Satisfiability Problems

Abstract

The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.

added discussion of discrete adiabatic method, and simulations with 30 bits 8 pages, 8 figures

References in corpus (6)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Search by Local Adiabatic Evolution
• Simulations of the adiabatic quantum optimization for the Set Partition Problem
• Quantum Portfolios
• Solving Random Satisfiability Problems with Quantum Computers

Cited by in corpus (48)

• Simulating chemistry using quantum computers
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Anderson localization casts clouds over adiabatic quantum optimization
• Adiabatic Quantum Simulation of Quantum Chemistry
• First order phase transition in the Quantum Adiabatic Algorithm
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• First-order transitions and the performance of quantum algorithms in random optimization problems
• How to Build the Thermofield Double State
• Decoherence in a scalable adiabatic quantum computer
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• Residual Energies after Slow Quantum Annealing
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Quantum Auctions: Facts and Myths
• An introduction to quantum annealing
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Simulation of many-qubit quantum computation with matrix product states
• Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
• Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Period Finding with Adiabatic Quantum Computation
• Density functional theory and quantum computation
• Error suppression in adiabatic quantum computing with qubit ensembles
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Local Hamiltonians in Quantum Computation
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Quantum adiabatic optimization and combinatorial landscapes
• How Fast Can Quantum Annealers Count?
• Adiabatic quantum algorithm for artificial graphene
• Dynamics of quantum adiabatic evolution algorithm for Number Partitioning
• Adiabatic quantum computation along quasienergies
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• Adiabatic Theorem for Discrete Time Evolution
• Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians
• Solving Satisfiability Problems by the Ground-State Quantum Computer
• Quantum Algorithm to Solve Satisfiability Problems
• A relation between fidelity and quantum adiabatic evolution
• The effect of quantum fluctuations on the coloring of random graphs
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Quantum control without quantum states
• Eigenlevel statistics of the quantum adiabatic algorithm
• Effects of dynamical paths on the energy gap and the corrections to free energy in path integrals of mean-field quantum spin systems