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)≈ 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
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
zA associated with the scaling behavior in the $\ensuremath{\tau}$ direction. We find the relation
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
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.
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.
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.
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.