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:2102.00182 · Physical Review Research

Entropic barriers as a reason for hardness in both classical and quantum algorithms

Matteo Bellitti, Federico Ricci‐Tersenghi, Antonello Scardicchio

Published Oct 7, 2021• 23 citations
arXivHTMLPDF

Abstract

We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers. We study, both analytically and numerically, several optimization algorithms, finding that entropic barriers affect in a similar way classical local algorithms and quantum annealing. For the adiabatic algorithm, the difficulty we identify is distinct from that of tunneling under large barriers, but does, nonetheless, give rise to exponential running (annealing) times.

DOI
10.1103/physrevresearch.3.043015

Related papers

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

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

Edward Farhi, David Gosset, Itay Hen +4 more

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.

arXiv:1208.3757•Physical Review A•Nov 29, 2012•118 citations

Adiabatic quantum optimization fails for random instances of NP-complete problems

B. L. Altshuler, Hari Krovi, Jérémie Roland

Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long.

arXiv:0908.2782•Aug 19, 2009•27 citations

Necessary adiabatic run times in quantum optimization

Lucas T. Brady, Wim van Dam

Quantum annealing is guaranteed to find the ground state of optimization problems provided it operates in the adiabatic limit. Recent work [S. Muthukrishnan et al., Phys. Rev. X 6, 031010 (2016)] has found that for some barrier tunneling problems, quantum annealing can be run much faster than is adiabatically required. Specifically, an $n$-qubit optimization problem was presented for which a nonadiabatic, or diabatic, annealing algorithm requires only a constant run time, while an adiabatic annealing algorithm requires a run-time polynomial in $n$. Here we show that this nonadiabatic speedup is the direct result of a specific symmetry in the studied problem. In the more general case, no such nonadiabatic speedup occurs and we show why the special case achieves this speedup compared to the general case. We also prove that the adiabatic annealing algorithm has a necessary and sufficient run time that is quadratically better than the standard quantum adiabatic condition suggests. We conclude with an observation about the required precision in timing for the diabatic algorithm.

arXiv:1611.02585•Physical Review A•Mar 30, 2017•18 citations

Quantum algorithm for energy matching in hard optimization problems

Christopher L. Baldwin, Chris R. Laumann

We consider the ability of local quantum dynamics to solve the ``energy-matching'' problem: given an instance of a classical optimization problem and a low-energy state, find another macroscopically distinct low-energy state. Energy matching is difficult in rugged optimization landscapes, as the given state provides little information about the distant topography. Here, we show that the introduction of quantum dynamics can provide a speedup over classical algorithms in a large class of hard optimization problems. Tunneling allows the system to explore the optimization landscape while approximately conserving the classical energy, even in the presence of large barriers. Specifically, we study energy matching in the random $p$-spin model of spin-glass theory. Using perturbation theory and exact diagonalization, we show that introducing a transverse field leads to three sharp dynamical phases, only one of which solves the matching problem: (1) a small-field ``trapped'' phase, in which tunneling is too weak for the system to escape the vicinity of the initial state; (2) a large-field ``excited'' phase, in which the field excites the system into high-energy states, effectively forgetting the initial energy; and (3) the intermediate ``tunneling'' phase, in which the system succeeds at energy matching. The rate at which distant states are found in the tunneling phase, although exponentially slow in system size, is exponentially faster than classical search algorithms.

arXiv:1803.02410•Physical review. B./Physical review. B•Jun 11, 2018•46 citations

Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability

Marko Žnidarič

We numerically study the quantum adiabatic algorithm for propositional satisfiability. A new class of previously unknown hard instances is identified among random problems. We numerically find that the running time for such instances grows exponentially with their size. The worst case complexity of the quantum adiabatic algorithm therefore seems to be exponential.

arXiv:quant-ph/0502077•Physical Review A•Jun 8, 2005•38 citations
We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers. We study, both analytically and numerically, several optimization algorithms, finding that entropic barriers affect in a similar way classical local algorithms and quantum annealing. For the adiabatic algorithm, the difficulty we identify is distinct from that of tunneling under large barriers, but does, nonetheless, give rise to exponential running (annealing) times.
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.
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.
Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long.
Quantum annealing is guaranteed to find the ground state of optimization problems provided it operates in the adiabatic limit. Recent work [S. Muthukrishnan et al., Phys. Rev. X 6, 031010 (2016)] has found that for some barrier tunneling problems, quantum annealing can be run much faster than is adiabatically required. Specifically, an nnn-qubit optimization problem was presented for which a nonadiabatic, or diabatic, annealing algorithm requires only a constant run time, while an adiabatic annealing algorithm requires a run-time polynomial in nnn. Here we show that this nonadiabatic speedup is the direct result of a specific symmetry in the studied problem. In the more general case, no such nonadiabatic speedup occurs and we show why the special case achieves this speedup compared to the general case. We also prove that the adiabatic annealing algorithm has a necessary and sufficient run time that is quadratically better than the standard quantum adiabatic condition suggests. We conclude with an observation about the required precision in timing for the diabatic algorithm.
We consider the ability of local quantum dynamics to solve the ``energy-matching'' problem: given an instance of a classical optimization problem and a low-energy state, find another macroscopically distinct low-energy state. Energy matching is difficult in rugged optimization landscapes, as the given state provides little information about the distant topography. Here, we show that the introduction of quantum dynamics can provide a speedup over classical algorithms in a large class of hard optimization problems. Tunneling allows the system to explore the optimization landscape while approximately conserving the classical energy, even in the presence of large barriers. Specifically, we study energy matching in the random ppp-spin model of spin-glass theory. Using perturbation theory and exact diagonalization, we show that introducing a transverse field leads to three sharp dynamical phases, only one of which solves the matching problem: (1) a small-field ``trapped'' phase, in which tunneling is too weak for the system to escape the vicinity of the initial state; (2) a large-field ``excited'' phase, in which the field excites the system into high-energy states, effectively forgetting the initial energy; and (3) the intermediate ``tunneling'' phase, in which the system succeeds at energy matching. The rate at which distant states are found in the tunneling phase, although exponentially slow in system size, is exponentially faster than classical search algorithms.