The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs

Abstract

In this paper we study the performance of the quantum adiabatic algorithm on random instances of two combinatorial optimization problems, 3-regular 3-XORSAT and 3-regular Max-Cut. The cost functions associated with these two clause-based optimization problems are similar as they are both defined on 3-regular hypergraphs. For 3-regular 3-XORSAT the clauses contain three variables and for 3-regular Max-Cut the clauses contain two variables. The quantum adiabatic algorithms we study for these two problems use interpolating Hamiltonians which are stoquastic and therefore amenable to sign-problem free quantum Monte Carlo and quantum cavity methods. Using these techniques we find that the quantum adiabatic algorithm fails to solve either of these problems efficiently, although for different reasons.

20 pages, 15 figures

References in corpus (8)

• Bounds for the adiabatic approximation with applications to quantum computation
• Stochastic series expansion method for quantum Ising models with arbitrary interactions
• 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
• Simple Glass Models and their Quantum Annealing
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Cavity method for quantum spin glasses on the Bethe lattice
• A solvable model of quantum random optimization problems

Cited by in corpus (2)

• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The effect of quantum fluctuations on the coloring of random graphs