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:0803.0149 · Physical Review E

Statistical mechanics of the quantum K -satisfiability problem

Sergey Knysh, Vadim Smelyanskiy

Published Dec 24, 2008• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreve.78.061128

Related papers

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•5 citations

Dynamics of classical and quantum spin systems with random fields

D. Boyanovsky, John Cardy

We study the effect of quenched time-independent random fields coupled linearly to the order parameter on the dynamical critical behavior of spin systems. We assume that the dynamics is described by a Langevin equation without conservation of the order parameter. It is shown that the dominant fluctuations are those induced by the random fields and, therefore, thermal fluctuations are irrelevant. This allows us to establish a relation between this model and a quantum spin system in the presence of a quenched random field. Moreover, we find that only static exponents in $D$ dimensions are the same as those of the pure ($D\ensuremath{-}2$)-dimensional theory, but the dynamical exponent $z$ does not satisfy this relation. The quantum system in $D$ dimensions is studied through its ($D+1$)-dimensional equivalent model where the quenched random fields are totally correlated in the additional imaginary-time ($\ensuremath{\tau}$) direction. The system is anisotropic, and there is a new exponent ${z}_{A}$ associated with the scaling behavior in the $\ensuremath{\tau}$ direction. We find the relation $z=2{z}_{A}$ to all orders in perturbation theory. For the zero-temperature quantum model we find that the static (zero-frequency) exponents are the same as those of the ($D\ensuremath{-}3$)-dimensional pure quantum model. At finite temperature, when the classical system is finite in the $\ensuremath{\tau}$ direction, we predict a crossover to $D$-dimensional classical behavior in nonstatic response and correlation functions, with crossover exponent ${({z}_{A}{\ensuremath{\nu}}_{(D\ensuremath{-}2)})}^{\ensuremath{-}1}$, where ${\ensuremath{\nu}}_{(D\ensuremath{-}2)}$ is the exponent $\ensuremath{\nu}$ for the ($D\ensuremath{-}2$)-dimensional pure classical system. The static correlation functions do not have this cross-over behavior and are the same as those of the ($D\ensuremath{-}3$)-dimensional pure quantum model. The dimensional shift in static quantities for both quantum and classical dynamical systems is a consequence of a supersymmetry in the underlying field theory. The exponent ${z}_{A}=1+\ensuremath{\eta}+O(\frac{1}{{N}^{2}})$ in the large-$N$ limit or ${z}_{A}=1+c\ensuremath{\eta}+O({\ensuremath{\epsilon}}^{4})$ in the $\ensuremath{\epsilon}$ expansion where $c=1\ensuremath{-}\frac{3}{4}[\frac{(N+2)}{{(N+8)}^{2}}]\ensuremath{\epsilon}$ and $\ensuremath{\eta}$ is the same as in the ($D\ensuremath{-}2$)-dimensional pure classical system. We also study the above classical random-field Ising problem using the interface approach, but are unable to draw any definite conclusion about the dynamics at the lower critical dimension $D=3$.

Physical review. B, Condensed matter•May 1, 1983•26 citations

Dynamics of order parameters of nonstoquastic Hamiltonians in the adaptive quantum Monte Carlo method

Shunta Arai, Masayuki Ohzeki, Kazuyuki Tanaka

We derive macroscopically deterministic flow equations with regard to the order parameters of the ferromagnetic p-spin model with infinite-range interactions. The p-spin model has a first-order phase transition for p>2. In the case of p≥5, the p-spin model with antiferromagnetic XX interaction has a second-order phase transition in a certain region. In this case, however, the model becomes a nonstoquastic Hamiltonian, resulting in a negative sign problem. To simulate the p-spin model with antiferromagnetic XX interaction, we utilize the adaptive quantum Monte Carlo method. By using this method, we can regard the effect of the antiferromagnetic XX interaction as fluctuations of the transverse magnetic field. A previous study [J. Inoue, J. Phys. Conf. Ser. 233, 012010 (2010)1742-659610.1088/1742-6596/233/1/012010] derived deterministic flow equations of the order parameters in the quantum Monte Carlo method. In this study, we derive macroscopically deterministic flow equations for the magnetization and transverse magnetization from the master equation in the adaptive quantum Monte Carlo method. Under the Suzuki-Trotter decomposition, we consider the Glauber-type stochastic process. We solve these differential equations by using the Runge-Kutta method, and we verify that these results are consistent with the saddle-point solution of mean-field theory. Finally, we analyze the stability of the equilibrium solutions obtained by the differential equations.

arXiv:1810.09943•Physical review. E•Mar 14, 2019•11 citations

Deterministic flows of order-parameters in stochastic processes of quantum Monte Carlo method

Jun-ichi Inoue

In terms of the stochastic process of quantum-mechanical version of Markov chain Monte Carlo method (the MCMC), we analytically derive macroscopically deterministic flow equations of order parameters such as spontaneous magnetization in infinite-range ( d (= ∞ )-dimensional) quantum spin systems. By means of the Trotter decomposition, we consider the transition probability of Glauber-type dynamics of microscopic states for the corresponding ( d + 1)-dimensional classical system. Under the static approximation, differential equations with respect to macroscopic order parameters are explicitly obtained from the master equation that describes the microscopic-law. In the steady state, we show that the equations are identical to the saddle point equations for the equilibrium state of the same system. The equation for the dynamical Ising model is recovered in the classical limit. We also check the validity of the static approximation by making use of computer simulations for finite size systems and discuss several possible extensions of our approach to disordered spin systems for statistical-mechanical informatics. Especially, we shall use our procedure to evaluate the decoding process of Bayesian image restoration. With the assistance of the concept of dynamical replica theory (the DRT), we derive the zero-temperature flow equation of image restoration measure showing some 'non-monotonic' behaviour in its time evolution.

arXiv:1004.2943•Journal of Physics Conference Series•Jun 1, 2010•5 citations

Quantum effects in rotationally invariant spin glass models

Yoshinori Hara, Yoshiyuki Kabashima

This study investigates the quantum effects in transverse-field Ising spin glass models with rotationally invariant random interactions. The primary aim is to evaluate the validity of a quasistatic approach that captures the imaginary-time dependence of the order parameters beyond the conventional static approximation. Using the replica method combined with the Suzuki-Trotter decomposition, we established a stability condition for the replica symmetric solution, which is analogous to the de Almeida-Thouless criterion. Numerical analysis of the Sherrington-Kirkpatrick model estimates a value of the critical transverse field, Γ_{c}, which is consistent with previous Monte Carlo-based estimations. For the Hopfield model, it provides an estimate of Γ_{c}, which has not been previously evaluated. For the random orthogonal model, our analysis suggests that quantum effects alter the random first-order transition scenario in the low-temperature limit. This study supports a quasistatic treatment for analyzing quantum spin glasses and may offer useful insights into the analysis of quantum optimization algorithms.

arXiv:2504.18034•Physical review. E•Oct 7, 2025•1 citation

Quantum effects in the critical properties of the X-Y model in a transverse magnetic field: crossover scaling near zero temperature

Paul R. Gerber

The susceptibility of a quantum X-Y model in a transverse field Gamma is studied in the vicinity of the multicritical point ( Gamma c ,T=0). For dimensions d between two and four we obtain a Hartree type approximation an equation for the corresponding crossover function which is solvable analytically in three dimensions. The critical line Gamma c (T)- Gamma c (0) approximately T psi is asymptotically described by the shift exponent psi =d/2 in accord with self-consistent spin wave theory. For the variable of the crossover scaling function T/( Gamma - Gamma c (T)) phi one obtains the crossover exponent phi =(4-d)/2 which is characteristic for the Gaussian multicritical point. A dimensional-analysis argument suggests that this is valid beyond the approximation.

Journal of Physics C Solid State Physics•Dec 24, 1978•18 citations
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.
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.
We study the effect of quenched time-independent random fields coupled linearly to the order parameter on the dynamical critical behavior of spin systems. We assume that the dynamics is described by a Langevin equation without conservation of the order parameter. It is shown that the dominant fluctuations are those induced by the random fields and, therefore, thermal fluctuations are irrelevant. This allows us to establish a relation between this model and a quantum spin system in the presence of a quenched random field. Moreover, we find that only static exponents in DDD dimensions are the same as those of the pure ($D\ensuremath{-}2$)-dimensional theory, but the dynamical exponent zzz does not satisfy this relation. The quantum system in DDD dimensions is studied through its (D+1D+1D+1)-dimensional equivalent model where the quenched random fields are totally correlated in the additional imaginary-time ($\ensuremath{\tau}$) direction. The system is anisotropic, and there is a new exponent zA{z}_{A}zA​ associated with the scaling behavior in the $\ensuremath{\tau}$ direction. We find the relation z=2zAz=2{z}_{A}z=2zA​ to all orders in perturbation theory. For the zero-temperature quantum model we find that the static (zero-frequency) exponents are the same as those of the ($D\ensuremath{-}3$)-dimensional pure quantum model. At finite temperature, when the classical system is finite in the $\ensuremath{\tau}$ direction, we predict a crossover to DDD-dimensional classical behavior in nonstatic response and correlation functions, with crossover exponent ${({z}_{A}{\ensuremath{\nu}}_{(D\ensuremath{-}2)})}^{\ensuremath{-}1}$, where ${\ensuremath{\nu}}_{(D\ensuremath{-}2)}$ is the exponent $\ensuremath{\nu}$ for the ($D\ensuremath{-}2$)-dimensional pure classical system. The static correlation functions do not have this cross-over behavior and are the same as those of the ($D\ensuremath{-}3$)-dimensional pure quantum model. The dimensional shift in static quantities for both quantum and classical dynamical systems is a consequence of a supersymmetry in the underlying field theory. The exponent ${z}_{A}=1+\ensuremath{\eta}+O(\frac{1}{{N}^{2}})$ in the large-NNN limit or ${z}_{A}=1+c\ensuremath{\eta}+O({\ensuremath{\epsilon}}^{4})$ in the $\ensuremath{\epsilon}$ expansion where $c=1\ensuremath{-}\frac{3}{4}[\frac{(N+2)}{{(N+8)}^{2}}]\ensuremath{\epsilon}$ and $\ensuremath{\eta}$ is the same as in the ($D\ensuremath{-}2$)-dimensional pure classical system. We also study the above classical random-field Ising problem using the interface approach, but are unable to draw any definite conclusion about the dynamics at the lower critical dimension D=3D=3D=3.
We derive macroscopically deterministic flow equations with regard to the order parameters of the ferromagnetic p-spin model with infinite-range interactions. The p-spin model has a first-order phase transition for p>2. In the case of p≥5, the p-spin model with antiferromagnetic XX interaction has a second-order phase transition in a certain region. In this case, however, the model becomes a nonstoquastic Hamiltonian, resulting in a negative sign problem. To simulate the p-spin model with antiferromagnetic XX interaction, we utilize the adaptive quantum Monte Carlo method. By using this method, we can regard the effect of the antiferromagnetic XX interaction as fluctuations of the transverse magnetic field. A previous study [J. Inoue, J. Phys. Conf. Ser. 233, 012010 (2010)1742-659610.1088/1742-6596/233/1/012010] derived deterministic flow equations of the order parameters in the quantum Monte Carlo method. In this study, we derive macroscopically deterministic flow equations for the magnetization and transverse magnetization from the master equation in the adaptive quantum Monte Carlo method. Under the Suzuki-Trotter decomposition, we consider the Glauber-type stochastic process. We solve these differential equations by using the Runge-Kutta method, and we verify that these results are consistent with the saddle-point solution of mean-field theory. Finally, we analyze the stability of the equilibrium solutions obtained by the differential equations.
In terms of the stochastic process of quantum-mechanical version of Markov chain Monte Carlo method (the MCMC), we analytically derive macroscopically deterministic flow equations of order parameters such as spontaneous magnetization in infinite-range ( d (= ∞ )-dimensional) quantum spin systems. By means of the Trotter decomposition, we consider the transition probability of Glauber-type dynamics of microscopic states for the corresponding ( d + 1)-dimensional classical system. Under the static approximation, differential equations with respect to macroscopic order parameters are explicitly obtained from the master equation that describes the microscopic-law. In the steady state, we show that the equations are identical to the saddle point equations for the equilibrium state of the same system. The equation for the dynamical Ising model is recovered in the classical limit. We also check the validity of the static approximation by making use of computer simulations for finite size systems and discuss several possible extensions of our approach to disordered spin systems for statistical-mechanical informatics. Especially, we shall use our procedure to evaluate the decoding process of Bayesian image restoration. With the assistance of the concept of dynamical replica theory (the DRT), we derive the zero-temperature flow equation of image restoration measure showing some 'non-monotonic' behaviour in its time evolution.
This study investigates the quantum effects in transverse-field Ising spin glass models with rotationally invariant random interactions. The primary aim is to evaluate the validity of a quasistatic approach that captures the imaginary-time dependence of the order parameters beyond the conventional static approximation. Using the replica method combined with the Suzuki-Trotter decomposition, we established a stability condition for the replica symmetric solution, which is analogous to the de Almeida-Thouless criterion. Numerical analysis of the Sherrington-Kirkpatrick model estimates a value of the critical transverse field, Γ_{c}, which is consistent with previous Monte Carlo-based estimations. For the Hopfield model, it provides an estimate of Γ_{c}, which has not been previously evaluated. For the random orthogonal model, our analysis suggests that quantum effects alter the random first-order transition scenario in the low-temperature limit. This study supports a quasistatic treatment for analyzing quantum spin glasses and may offer useful insights into the analysis of quantum optimization algorithms.
The susceptibility of a quantum X-Y model in a transverse field Gamma is studied in the vicinity of the multicritical point ( Gamma c ,T=0). For dimensions d between two and four we obtain a Hartree type approximation an equation for the corresponding crossover function which is solvable analytically in three dimensions. The critical line Gamma c (T)- Gamma c (0) approximately T psi is asymptotically described by the shift exponent psi =d/2 in accord with self-consistent spin wave theory. For the variable of the crossover scaling function T/( Gamma - Gamma c (T)) phi one obtains the crossover exponent phi =(4-d)/2 which is characteristic for the Gaussian multicritical point. A dimensional-analysis argument suggests that this is valid beyond the approximation.