Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1208.3757 · Physical Review A

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

Edward Farhi, David Gosset, Itay Hen, Anders W. Sandvik, Peter W. Shor, A. P. Young, Francesco Zamponi

Published Nov 29, 2012• 118 citations
arXivHTMLPDF

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 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.

DOI
10.1103/physreva.86.052334

Related papers

Quantum adiabatic algorithms, small gaps, and different paths

Edward Farhi, Jeffrey Goldstone, David Gosset +3 more

We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.

Quantum Information and Computation•Mar 1, 2011•57 citations

Quantum Adiabatic Algorithms, Small Gaps, and Different Paths

Edward Farhi, Jeffrey Goldstone, David Gosset +3 more

We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.

arXiv:0909.4766•Sep 25, 2009•3 citations

On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms

Eliot Kapit, Brandon Barton, Sean Feeney +5 more

A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_{\mathrm{unsat}}-N_{\mathrm{sat}}$, spectrally filtered quantum optimization will return states with $E \leq q_m E_{\mathrm{GS}}$ (where $E_{\rm GS}$ is the ground state energy) in sub-quadratic time, where conservatively, $q_m \simeq 0.59$. This is in contrast to $q_m \to 0$ for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

arXiv:2312.06104•Dec 11, 2023•1 citation

Random matrix model of adiabatic quantum computing

David R. Mitchell, Christoph Adami, Waynn Lue +1 more

We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3-SAT (an NP-complete problem) in terms of random matrix theory (RMT). We determine the global regularity of the spectral fluctuations of the instantaneous Hamiltonians encountered during the interpolation between the starting Hamiltonians and the ones whose ground states encode the solutions to the computational problems of interest. At each interpolation point, we quantify the degree of regularity of the average spectral distribution via its Brody parameter, a measure that distinguishes regular (i.e., Poissonian) from chaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor spacings. We find that for hard problem instances---i.e., those having a critical ratio of clauses to variables---the spectral fluctuations typically become irregular across a contiguous region of the interpolation parameter, while the spectrum is regular for easy instances. Within the hard region, RMT may be applied to obtain a mathematical model of the probability of avoided level crossings and concomitant failure rate of the adiabatic algorithm due to nonadiabatic Landau-Zener-type transitions. Our model predicts that if the interpolation is performed at a uniform rate, the average failure rate of the quantum adiabatic algorithm, when averaged over hard problem instances, scales exponentially with increasing problem size.

arXiv:quant-ph/0409088•Physical Review A•May 20, 2005•17 citations

The Overlap Gap Property Limits Limit Swapping in the QAOA

Mark Xin Hong Goh

Abstract The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erdös-Renyi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even q ≥ 4, Max- q -XORSAT is bounded away from optimality when optimized using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth p ≤ ϵ log n , providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max- q -XORSAT problems. We also provide some numerical evidence that the limitation should be extended to odd q by showing that the OGP exists for the Max-3-XORSAT on random regular graphs.

arXiv:2404.06087•Quantum Information and Computation•Aug 1, 2025•2 citations

Quantum adiabatic algorithms, small gaps, and different paths

Edward Farhi, Jeffrey Goldston, David Gosset +3 more

We construct a set of instances of 3SAT which are not solved efficiently using the simplestquantum adiabatic algorithm. These instances are obtained by picking randomclauses all consistent with two disparate planted solutions and then penalizing one ofthem with a single additional clause. We argue that by randomly modifying the beginningHamiltonian, one obtains (with substantial probability) an adiabatic path thatremoves this difficulty. This suggests that the quantum adiabatic algorithm should ingeneral be run on each instance with many different random paths leading to the problemHamiltonian. We do not know whether this trick will help for a random instance of3SAT (as opposed to an instance from the particular set we consider), especially if theinstance has an exponential number of disparate assignments that violate few clauses.We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way tonumerically investigate the ground state as well as the first excited state of our system.Our arguments are supplemented by Quantum Monte Carlo data from simulations withup to 150 spins.

Quantum Information and Computation•Mar 1, 2011•37 citations
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 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.
We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.
We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.
A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be E=Nunsat−NsatE = N_{\mathrm{unsat}}-N_{\mathrm{sat}}E=Nunsat​−Nsat​, spectrally filtered quantum optimization will return states with E≤qmEGSE \leq q_m E_{\mathrm{GS}}E≤qm​EGS​ (where EGSE_{\rm GS}EGS​ is the ground state energy) in sub-quadratic time, where conservatively, qm≃0.59q_m \simeq 0.59qm​≃0.59. This is in contrast to qm→0q_m \to 0qm​→0 for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.
We present an analysis of the quantum adiabatic algorithm for solving hard instances of 3-SAT (an NP-complete problem) in terms of random matrix theory (RMT). We determine the global regularity of the spectral fluctuations of the instantaneous Hamiltonians encountered during the interpolation between the starting Hamiltonians and the ones whose ground states encode the solutions to the computational problems of interest. At each interpolation point, we quantify the degree of regularity of the average spectral distribution via its Brody parameter, a measure that distinguishes regular (i.e., Poissonian) from chaotic (i.e., Wigner-type) distributions of normalized nearest-neighbor spacings. We find that for hard problem instances---i.e., those having a critical ratio of clauses to variables---the spectral fluctuations typically become irregular across a contiguous region of the interpolation parameter, while the spectrum is regular for easy instances. Within the hard region, RMT may be applied to obtain a mathematical model of the probability of avoided level crossings and concomitant failure rate of the adiabatic algorithm due to nonadiabatic Landau-Zener-type transitions. Our model predicts that if the interpolation is performed at a uniform rate, the average failure rate of the quantum adiabatic algorithm, when averaged over hard problem instances, scales exponentially with increasing problem size.
Abstract The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erdös-Renyi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even q ≥ 4, Max- q -XORSAT is bounded away from optimality when optimized using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth p ≤ ϵ log n , providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max- q -XORSAT problems. We also provide some numerical evidence that the limitation should be extended to odd q by showing that the OGP exists for the Max-3-XORSAT on random regular graphs.
We construct a set of instances of 3SAT which are not solved efficiently using the simplestquantum adiabatic algorithm. These instances are obtained by picking randomclauses all consistent with two disparate planted solutions and then penalizing one ofthem with a single additional clause. We argue that by randomly modifying the beginningHamiltonian, one obtains (with substantial probability) an adiabatic path thatremoves this difficulty. This suggests that the quantum adiabatic algorithm should ingeneral be run on each instance with many different random paths leading to the problemHamiltonian. We do not know whether this trick will help for a random instance of3SAT (as opposed to an instance from the particular set we consider), especially if theinstance has an exponential number of disparate assignments that violate few clauses.We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way tonumerically investigate the ground state as well as the first excited state of our system.Our arguments are supplemented by Quantum Monte Carlo data from simulations withup to 150 spins.