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 (27)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• The Bethe lattice spin glass revisited
• Stochastic series expansion method with operator-loop update
• Bounds for the adiabatic approximation with applications to quantum computation
• Anderson localization casts clouds over adiabatic quantum optimization
• Bond-order-wave phase and quantum phase transitions in the one-dimensional extended Hubbard model
• Consistency of the Adiabatic Theorem
• Stochastic series expansion method for quantum Ising models with arbitrary interactions
• First order phase transition in the Quantum Adiabatic Algorithm
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• A ferromagnet with a glass transition
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Simple Glass Models and their Quantum Annealing
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Adiabatic Quantum Computing for Random Satisfiability Problems
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• 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
• Conjecture on the maximum cut and bisection width in random regular graphs
• The cavity method for quantum disordered systems: from transverse random field ferromagnets to directed polymers in random media
• A solvable model of quantum random optimization problems
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• The quantum Biroli-Mézard model: glass transition and superfluidity in a quantum lattice glass model
• Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations

Cited by in corpus (75)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Quantum annealing with more than one hundred qubits
• Quantum machine learning: a classical perspective
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• What is the Computational Value of Finite Range Tunneling?
• Adiabatic Quantum Simulation of Quantum Chemistry
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Quantum Annealing for Constrained Optimization
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• NISQ Computers: A Path to Quantum Supremacy
• Temperature scaling law for quantum annealing optimizers
• Unraveling Quantum Annealers using Classical Hardness
• MAX 2-SAT with up to 108 qubits
• Driver Hamiltonians for constrained optimization in quantum annealing
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Quantum annealing: the fastest route to quantum computation?
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Quantum algorithm for energy matching in hard optimization problems
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Velocity of excitations in ordered, disordered and critical antiferromagnets
• The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• Practical engineering of hard spin-glass instances
• Quasi-adiabatic quantum Monte Carlo algorithm for quantum evolution in imaginary time
• Stability of the quantum Sherrington-Kirkpatrick spin glass model
• Analog Nature of Quantum Adiabatic Unstructured Search
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Off-Diagonal Expansion Quantum Monte Carlo
• Strange correlations in spin-1 Heisenberg antiferromagnets
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Equation Planting: A Tool for Benchmarking Ising Machines
• Adiabatic Quantum Optimization for Associative Memory Recall
• Nonequilibrium dynamics in deconfined quantum critical point revealed by imaginary-time evolution
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
• Universal short time quantum critical dynamics of finite size systems
• Inhomogeneous quenches as state preparation in two-dimensional conformal field theories
• Cooling arbitrary near-critical systems using hyperbolic quenches
• Hilbert Space Fragmentation and Ashkin-Teller Criticality in Fluctuation Coupled Ising Models
• Calculating the divided differences of the exponential function by addition and removal of inputs
• Permutation Matrix Representation Quantum Monte Carlo
• Ergodic and localized regions in quantum spin glasses on the Bethe lattice
• Continuous-time quantum walks for MAX-CUT are hot
• Adiabatic quantum algorithm for artificial graphene
• Boundary conditions dependence of the phase transition in the quantum Newman-Moore model
• VanQver: The Variational and Adiabatically Navigated Quantum Eigensolver
• On the quantum spin glass transition on the Bethe lattice
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Dual dynamic scaling in deconfined quantum criticality
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• Realizable Quantum Adiabatic Search
• Quantum Monte Carlo Annealing with Multi-Spin Dynamics
• Tensor network method for reversible classical computation
• Obstacles to quantum annealing in a planar embedding of XORSAT
• Short-imaginary-time quantum critical dynamics in the J-Q${}_3$ spin chain
• Exact expression of the energy gap at first-order quantum phase transitions of a non-stoquastic Hamiltonian
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• The effect of quantum fluctuations on the coloring of random graphs
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Optimization via Quantum Preconditioning
• Bayesian Networks based Hybrid Quantum-Classical Machine Learning Approach to Elucidate Gene Regulatory Pathways
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Tensor networks for $p$-spin models
• Quantum-Inspired Tempering for Ground State Approximation using Artificial Neural Networks
• Duality approach to quantum annealing of the 3-XORSAT problem
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Hard combinatorial problems and minor embeddings on lattice graphs
• Imaginary-time Quantum Relaxation Critical Dynamics with Semi-ordered Initial States
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses
• Classical Simulation of High Temperature Quantum Ising Models