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

First-order transitions for random optimization problems in a transverse field

Thomas Jörg, Florent Krząkała, Guilhem Semerjian, Francesco Zamponi

Published Nov 17, 2009• 5 citations
OpenAlex

Abstract

Using the quantum cavity method, we present an analytical study of the phase diagram of a random optimization problem in a transverse field, in the thermodynamic limit and for a uniformly random distribution of instances. We include the effect of replica symmetry breaking, and unveil the occurrence of a first-order quantum phase transition. We back up our results with Quantum Monte Carlo and Exact Diagonalization methods, and provide evidence that the gap vanishes exponentially with the system size at the transition. This suggests that the Quantum Adiabatic Algorithm requires an exponential time to find the ground state of such problems.

Related papers

First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems

Thomas Jörg, Florent Krząkała, Guilhem Semerjian +1 more

We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.

arXiv:0911.3438•Physical Review Letters•May 20, 2010•100 citations

Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem

Sergey Knysh, Vadim Smelyanskiy

In this paper we show that the performance of the quantum adiabatic algorithm is determined by phase transitions in underlying problem in the presence of transverse magnetic field $Γ$. We show that the quantum version of random Satisfiability problem with 3 bits in a clause (3-SAT) has a first-order quantum phase transition. We analyze the phase diagram $γ=γ(Γ)$ where $γ$ is an average number of clauses per binary variable in 3-SAT. The results are obtained in a closed form assuming replica symmetry and neglecting time correlations at small values of the transverse field $Γ$. In the limit of $Γ=0$ the value of $γ(0)\approx$ 5.18 corresponds to that given by the replica symmetric treatment of a classical random 3-SAT problem. We demonstrate the qualitative similarity between classical and quantum versions of this problem.

arXiv:cond-mat/0602257•Feb 10, 2006•1 citation

On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm

Sergey Knysh, Vadim Smelyanskiy

Two recent preprints [B. Altshuler, H. Krovi, and J. Roland, "Quantum adiabatic optimization fails for random instances of NP-complete problems", arXiv:0908.2782 and "Anderson localization casts clouds over adiabatic quantum optimization", arXiv:0912.0746] argue that random 4th order perturbative corrections to the energies of local minima of random instances of NP-complete problem lead to avoided crossings that cause the failure of quantum adiabatic algorithm (due to exponentially small gap) close to the end, for very small transverse field that scales as an inverse power of instance size N. The theoretical portion of this work does not to take into account the exponential degeneracy of the ground and excited states at zero field. A corrected analysis shows that unlike those in the middle of the spectrum, avoided crossings at the edge would require high [O(1)] transverse fields, at which point the perturbation theory may become divergent due to quantum phase transition. This effect manifests itself only in large instances [exp(0.02 N) >> 1], which might be the reason it had not been observed in the authors' numerical work. While we dispute the proposed mechanism of failure of quantum adiabatic algorithm, we cannot draw any conclusions on its ultimate complexity.

arXiv:1005.3011•May 17, 2010•21 citations

Effect of quantum fluctuations on the coloring of random graphs

Victor Bapst, Guilhem Semerjian, Francesco Zamponi

We present a study of the coloring problem (antiferromagnetic Potts model) of random regular graphs, submitted to quantum fluctuations induced by a transverse field, using the quantum cavity method and quantum Monte Carlo simulations. We determine the order of the quantum phase transition encountered at low temperature as a function of the transverse field and discuss the structure of the quantum spin-glass phase. In particular, we conclude that the quantum adiabatic algorithm would fail to solve efficiently typical instances of these problems because of avoided level crossings within the quantum spin-glass phase, caused by a competition between energetic and entropic effects.

arXiv:1302.6861•Physical Review A•Apr 19, 2013•3 citations

Energy Gap at First-Order Quantum Phase Transitions: An Anomalous Case

Junichi Tsuda, Yuuki Yamanaka, Hidetoshi Nishimori

We show that the rate of closing of the energy gap between the ground state and the first excited state, as a function of system size, behaves in many qualitatively different ways at first-order quantum phase transitions of the infinite-range quantum XY model. Examples include polynomial, exponential and even factorially fast closing of the energy gap, all of which coexist along a single axis of the phase diagram representing the transverse field. This variety emerges depending on whether or not the transverse field assumes a rational number as well as on how the series of system size is chosen toward the thermodynamic limit. We conclude that there is no generically applicable rule to relate the rate of gap closing and the order of quantum phase transitions as is often implied in many studies, in particular in relation to the computational complexity of quantum annealing in its implementation as quantum adiabatic computation.

arXiv:1306.2142•Journal of the Physical Society of Japan•Oct 11, 2013•24 citations

Statistical mechanics of the quantum K -satisfiability problem

Sergey Knysh, Vadim Smelyanskiy

We study the quantum version of the random K -satisfiability problem in the presence of an external magnetic field Gamma applied in the transverse direction. We derive the replica-symmetric free-energy functional within the static approximation and the saddle-point equation for the order parameter: the distribution P[h(m)] of functions of magnetizations. The order parameter is interpreted as the histogram of probability distributions of individual magnetizations. In the limit of zero temperature and small transverse fields, to leading order in Gamma magnetizations m approximately 0 become relevant in addition to purely classical values of m approximately +/-1 . Self-consistency equations for the order parameter are solved numerically using a quasi-Monte Carlo method for K=3 . It is shown that for an arbitrarily small Gamma quantum fluctuations destroy the phase transition present in the classical limit Gamma=0 , replacing it with a smooth crossover transition. The implications of this result with respect to the expected performance of quantum optimization algorithms via adiabatic evolution are discussed. The replica-symmetric solution of the classical random K -satisfiability problem is briefly reexamined. It is shown that the phase transition at T=0 predicted by the replica-symmetric theory is of continuous type with atypical critical exponents.

arXiv:0803.0149•Physical Review E•Dec 24, 2008•5 citations
Using the quantum cavity method, we present an analytical study of the phase diagram of a random optimization problem in a transverse field, in the thermodynamic limit and for a uniformly random distribution of instances. We include the effect of replica symmetry breaking, and unveil the occurrence of a first-order quantum phase transition. We back up our results with Quantum Monte Carlo and Exact Diagonalization methods, and provide evidence that the gap vanishes exponentially with the system size at the transition. This suggests that the Quantum Adiabatic Algorithm requires an exponential time to find the ground state of such problems.
In this paper we show that the performance of the quantum adiabatic algorithm is determined by phase transitions in underlying problem in the presence of transverse magnetic field ΓΓΓ. We show that the quantum version of random Satisfiability problem with 3 bits in a clause (3-SAT) has a first-order quantum phase transition. We analyze the phase diagram γ=γ(Γ)γ=γ(Γ)γ=γ(Γ) where γγγ is an average number of clauses per binary variable in 3-SAT. The results are obtained in a closed form assuming replica symmetry and neglecting time correlations at small values of the transverse field ΓΓΓ. In the limit of Γ=0Γ=0Γ=0 the value of γ(0)≈γ(0)\approxγ(0)≈ 5.18 corresponds to that given by the replica symmetric treatment of a classical random 3-SAT problem. We demonstrate the qualitative similarity between classical and quantum versions of this problem.
Two recent preprints [B. Altshuler, H. Krovi, and J. Roland, "Quantum adiabatic optimization fails for random instances of NP-complete problems", arXiv:0908.2782 and "Anderson localization casts clouds over adiabatic quantum optimization", arXiv:0912.0746] argue that random 4th order perturbative corrections to the energies of local minima of random instances of NP-complete problem lead to avoided crossings that cause the failure of quantum adiabatic algorithm (due to exponentially small gap) close to the end, for very small transverse field that scales as an inverse power of instance size N. The theoretical portion of this work does not to take into account the exponential degeneracy of the ground and excited states at zero field. A corrected analysis shows that unlike those in the middle of the spectrum, avoided crossings at the edge would require high [O(1)] transverse fields, at which point the perturbation theory may become divergent due to quantum phase transition. This effect manifests itself only in large instances [exp(0.02 N) >> 1], which might be the reason it had not been observed in the authors' numerical work. While we dispute the proposed mechanism of failure of quantum adiabatic algorithm, we cannot draw any conclusions on its ultimate complexity.
We present a study of the coloring problem (antiferromagnetic Potts model) of random regular graphs, submitted to quantum fluctuations induced by a transverse field, using the quantum cavity method and quantum Monte Carlo simulations. We determine the order of the quantum phase transition encountered at low temperature as a function of the transverse field and discuss the structure of the quantum spin-glass phase. In particular, we conclude that the quantum adiabatic algorithm would fail to solve efficiently typical instances of these problems because of avoided level crossings within the quantum spin-glass phase, caused by a competition between energetic and entropic effects.
We show that the rate of closing of the energy gap between the ground state and the first excited state, as a function of system size, behaves in many qualitatively different ways at first-order quantum phase transitions of the infinite-range quantum XY model. Examples include polynomial, exponential and even factorially fast closing of the energy gap, all of which coexist along a single axis of the phase diagram representing the transverse field. This variety emerges depending on whether or not the transverse field assumes a rational number as well as on how the series of system size is chosen toward the thermodynamic limit. We conclude that there is no generically applicable rule to relate the rate of gap closing and the order of quantum phase transitions as is often implied in many studies, in particular in relation to the computational complexity of quantum annealing in its implementation as quantum adiabatic computation.
We study the quantum version of the random K -satisfiability problem in the presence of an external magnetic field Gamma applied in the transverse direction. We derive the replica-symmetric free-energy functional within the static approximation and the saddle-point equation for the order parameter: the distribution P[h(m)] of functions of magnetizations. The order parameter is interpreted as the histogram of probability distributions of individual magnetizations. In the limit of zero temperature and small transverse fields, to leading order in Gamma magnetizations m approximately 0 become relevant in addition to purely classical values of m approximately +/-1 . Self-consistency equations for the order parameter are solved numerically using a quasi-Monte Carlo method for K=3 . It is shown that for an arbitrarily small Gamma quantum fluctuations destroy the phase transition present in the classical limit Gamma=0 , replacing it with a smooth crossover transition. The implications of this result with respect to the expected performance of quantum optimization algorithms via adiabatic evolution are discussed. The replica-symmetric solution of the classical random K -satisfiability problem is briefly reexamined. It is shown that the phase transition at T=0 predicted by the replica-symmetric theory is of continuous type with atypical critical exponents.