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:1302.6861 · Physical Review A

Effect of quantum fluctuations on the coloring of random graphs

Victor Bapst, Guilhem Semerjian, Francesco Zamponi

Published Apr 19, 2013• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.87.042322

Related papers

Quantum versus Classical Annealing: Insights from Scaling Theory and Results for Spin Glasses on 3-Regular Graphs

Chengwei Liu, Anatoli Polkovnikov, Anders W. Sandvik

We discuss an Ising spin glass where each S=1/2 spin is coupled antiferromagnetically to three other spins (3-regular graphs). Inducing quantum fluctuations by a time-dependent transverse field, we use out-of-equilibrium quantum Monte Carlo simulations to study dynamic scaling at the quantum glass transition. Comparing the dynamic exponent and other critical exponents with those of the classical (temperature-driven) transition, we conclude that quantum annealing is less efficient than classical simulated annealing in bringing the system into the glass phase. Quantum computing based on the quantum annealing paradigm is therefore inferior to classical simulated annealing for this class of problems. We also comment on previous simulations where a parameter is changed with the simulation time, which is very different from the true Hamiltonian dynamics simulated here.

arXiv:1409.7192•Physical Review Letters•Apr 7, 2015•55 citations

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

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

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.

•Nov 17, 2009•5 citations

Quantum phase transition in a disordered long-range transverse Ising antiferromagnet

Anjan Kumar Chandra, Jun‐ichi Inoue, Bikas K. Chakrabarti

We consider a long-range Ising antiferromagnet put in a transverse field (LRTIAF) with disorder. We have obtained the phase diagrams for both the classical and quantum cases. For the pure case applying quantum Monte Carlo method, we study the variation in order parameter (spin correlation in the Trotter direction), susceptibility, and average energy of the system for various values of the transverse field at different temperatures. The antiferromagnetic order is seen to get immediately broken as soon as the thermal or quantum fluctuations are added. We discuss generally the phase diagram for the same LRTIAF model with perturbative Sherrington-Kirkpatrick-type disorder. We find that while the antiferromagnetic order is immediately broken as one adds an infinitesimal transverse field or thermal fluctuation to the pure LRTIAF system, an infinitesimal SK spin-glass disorder is enough to induce a stable glass order in the LRTIAF. This glass order eventually gets destroyed as the thermal or quantum fluctuations are increased beyond their threshold values and the transition to paramagnetic phase occurs. Analytical studies for the phase transitions are discussed in details in each case. These transitions have been confirmed by applying classical and quantum Monte Carlo methods. We show here that the disordered LRTIAF has a surrogate incubation property of the SK spin glass phase.

arXiv:1001.3747•Physical Review E•Feb 1, 2010•9 citations

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

A novel quantum transition in a fully frustrated transverse Ising antiferromagnet

Anjan Kumar Chandra, Jun‐ichi Inoue, Bikas K. Chakrabarti

We consider a long-range Ising antiferromagnet (LRIAF) put in a transverse field. Applying quantum Monte Carlo method, we study the variation of order parameter (spin correlation in Trotter time direction), susceptibility and average energy of the system for various values of the transverse field at different temperatures. The antiferromagnetic order is seen to get immediately broken as soon as the thermal or quantum fluctuations are added. We also discuss the phase diagram for the Sherrington-Kirkpatrick (SK) model with the same LRIAF bias, also in presence of a transverse field. We find that while the antiferromagnetic order is immediately broken as one adds an infinitesimal transverse field or thermal fluctuation to the system, an infinitesimal SK spin glass disorder is enough to induce a stable glass order in the antiferromagnet. This glass order eventually gets destroyed as the thermal or quantum fluctuations increased beyond their threshold values and the transition to para phase occurs. Indications of this novel phase transition are discussed. Because of the presence of full frustration, this surrogate property of the LRIAF for incubation of stable spin glass phase in it (induced by addition of a small disorder) should enable eventually the study of classical and quantum spin glass phases by using some perturbation theory with respect to the disorder.

arXiv:0805.4303•Journal of Physics Conference Series•Jan 7, 2009•5 citations

On the quantum spin glass transition on the Bethe lattice

G Mossi, Tommaso Parolini, Sebastiano Pilati +1 more

Abstract We investigate the ground-state properties of a disorderd Ising model with uniform transverse field on the Bethe lattice, focusing on the quantum phase transition from a paramagnetic to a glassy phase that is induced by reducing the intensity of the transverse field. We use a combination of quantum Monte Carlo algorithms and exact diagonalization to compute Rényi entropies, quantum Fisher information, correlation functions and order parameter. We locate the transition by means of the peak of the Rényi entropy and we find agreement with the transition point estimated from the emergence of finite values of the Edwards–Anderson order parameter and from the peak of the correlation length. We interpret the results by means of a mean-field theory in which quantum fluctuations are treated as massive particles hopping on the interaction graph. We see that the particles are delocalized at the transition, a fact that points towards the existence of possibly another transition deep in the glassy phase where these particles localize, therefore leading to a many-body localized phase.

arXiv:1606.06462•Journal of Statistical Mechanics Theory and Experiment•Jan 1, 2017•10 citations
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 discuss an Ising spin glass where each S=1/2 spin is coupled antiferromagnetically to three other spins (3-regular graphs). Inducing quantum fluctuations by a time-dependent transverse field, we use out-of-equilibrium quantum Monte Carlo simulations to study dynamic scaling at the quantum glass transition. Comparing the dynamic exponent and other critical exponents with those of the classical (temperature-driven) transition, we conclude that quantum annealing is less efficient than classical simulated annealing in bringing the system into the glass phase. Quantum computing based on the quantum annealing paradigm is therefore inferior to classical simulated annealing for this class of problems. We also comment on previous simulations where a parameter is changed with the simulation time, which is very different from the true Hamiltonian dynamics simulated here.
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.
We consider a long-range Ising antiferromagnet put in a transverse field (LRTIAF) with disorder. We have obtained the phase diagrams for both the classical and quantum cases. For the pure case applying quantum Monte Carlo method, we study the variation in order parameter (spin correlation in the Trotter direction), susceptibility, and average energy of the system for various values of the transverse field at different temperatures. The antiferromagnetic order is seen to get immediately broken as soon as the thermal or quantum fluctuations are added. We discuss generally the phase diagram for the same LRTIAF model with perturbative Sherrington-Kirkpatrick-type disorder. We find that while the antiferromagnetic order is immediately broken as one adds an infinitesimal transverse field or thermal fluctuation to the pure LRTIAF system, an infinitesimal SK spin-glass disorder is enough to induce a stable glass order in the LRTIAF. This glass order eventually gets destroyed as the thermal or quantum fluctuations are increased beyond their threshold values and the transition to paramagnetic phase occurs. Analytical studies for the phase transitions are discussed in details in each case. These transitions have been confirmed by applying classical and quantum Monte Carlo methods. We show here that the disordered LRTIAF has a surrogate incubation property of the SK spin glass phase.
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 consider a long-range Ising antiferromagnet (LRIAF) put in a transverse field. Applying quantum Monte Carlo method, we study the variation of order parameter (spin correlation in Trotter time direction), susceptibility and average energy of the system for various values of the transverse field at different temperatures. The antiferromagnetic order is seen to get immediately broken as soon as the thermal or quantum fluctuations are added. We also discuss the phase diagram for the Sherrington-Kirkpatrick (SK) model with the same LRIAF bias, also in presence of a transverse field. We find that while the antiferromagnetic order is immediately broken as one adds an infinitesimal transverse field or thermal fluctuation to the system, an infinitesimal SK spin glass disorder is enough to induce a stable glass order in the antiferromagnet. This glass order eventually gets destroyed as the thermal or quantum fluctuations increased beyond their threshold values and the transition to para phase occurs. Indications of this novel phase transition are discussed. Because of the presence of full frustration, this surrogate property of the LRIAF for incubation of stable spin glass phase in it (induced by addition of a small disorder) should enable eventually the study of classical and quantum spin glass phases by using some perturbation theory with respect to the disorder.
Abstract We investigate the ground-state properties of a disorderd Ising model with uniform transverse field on the Bethe lattice, focusing on the quantum phase transition from a paramagnetic to a glassy phase that is induced by reducing the intensity of the transverse field. We use a combination of quantum Monte Carlo algorithms and exact diagonalization to compute Rényi entropies, quantum Fisher information, correlation functions and order parameter. We locate the transition by means of the peak of the Rényi entropy and we find agreement with the transition point estimated from the emergence of finite values of the Edwards–Anderson order parameter and from the peak of the correlation length. We interpret the results by means of a mean-field theory in which quantum fluctuations are treated as massive particles hopping on the interaction graph. We see that the particles are delocalized at the transition, a fact that points towards the existence of possibly another transition deep in the glassy phase where these particles localize, therefore leading to a many-body localized phase.