After reviewing the basics of the cavity method in classical systems, we show how its quantum version, with some appropriate approximation scheme, can be used to study a system of spins with random ferromagnetic interactions and a random transverse field. The quantum cavity equations describing the ferromagnetic-paramagnetic phase transition can be transformed into the well-known problem of a classical directed polymer in a random medium. The glass transition of this polymer problem translates into the existence of a 'Griffiths phase' close to the quantum phase transition of the quantum spin problem, where the physics is dominated by rare events. The physical behaviour of random transverse-field ferromagnets on the Bethe lattice is found to be very similar to that found in finite-dimensional systems, and the quantum cavity method gets back the known exact results of the one-dimensional problem.
After reviewing the basics of the cavity method in classical systems, we show how its quantum version, with some appropriate approximation scheme, can be used to study a system of spins with random ferromagnetic interactions and a random transverse field. The quantum cavity equations describing the ferromagnetic-paramagnetic phase transition can be transformed into the well-known problem of a classical directed polymer in a random medium. The glass transition of this polymer problem translates into the existence of a 'Griffiths phase' close to the quantum phase transition of the quantum spin problem, where the physics is dominated by rare events. The physical behaviour of random transverse-field ferromagnets on the Bethe lattice is found to be very similar to that found in finite-dimensional systems, and the quantum cavity method gets back the known exact results of the one-dimensional problem.
We have developed a very efficient numerical algorithm of the strong disorder renormalization group method to study the critical behaviour of the random transverse field Ising model, which is a prototype of random quantum magnets. With this algorithm we can renormalize an N-site cluster within a time NlogN, independently of the topology of the graph, and we went up to N ∼ 4 × 10(6). We have studied regular lattices with dimension D ≤ 4 as well as Erdős-Rényi random graphs, which are infinite dimensional objects. In all cases the quantum critical behaviour is found to be controlled by an infinite disorder fixed point, in which disorder plays a dominant role over quantum fluctuations. As a consequence the renormalization procedure as well as the obtained critical properties are asymptotically exact for large systems. We have also studied Griffiths singularities in the paramagnetic and ferromagnetic phases and generalized the numerical algorithm for other random quantum systems.
The classical statistical mechanical approach to complexity theory proceeds from the study of ensembles of computationally intractable optimization problems as a species of unusual disordered magnetic systems. Over the last thirty years, researchers have used this approach to supplement worst-case hardness results encoded by complexity theory with detailed information about thermodynamic and dynamic phase transitions in the structure of typical cases. This exchange of ideas between classical statistical mechanics and computer science enabled the development of important heuristic algorithms such as simulated annealing and survey propagation and further refined our understanding of glassiness and critical slowing in physical disordered systems. In this thesis, we map out an analogous program in the quantum context. The question is simple: what can quantum statistical mechanics reveal about the difficulty of solving hard quantum optimization problems? Or more directly, what makes those problems hard even for quantum computers? In this pursuit, we introduce the study of ensembles of optimization problems whose complexity status is intrinsically quantum mechanical (Part I) and develop techniques to study quantum spin glasses and the transverse field adiabatic algorithm applied to classically hard random optimization problems (Part II). In particular, we introduce the study of random quantum satisfiability (QSAT) and identify the coarse aspects of its phase diagram, including a new form of entanglement transition. We generalize the cavity method to the study of quantum models and use it to study the transverse field Ising glass and frustrated AKLT models on the Bethe lattice. We further apply the cavity method to extract Griffiths-McCoy singularities in a diluted (classical) ferromagnet and finally observe that there are no Goldstone bosons on the Bethe lattice.
Strong disorder renormalization for the random transverse field Ising model leads to a complicated topology of surviving clusters as soon as d > 1. Even if one starts from a Cayley tree, the network of surviving renormalized clusters will contain loops, so that no analytical solution can be obtained. Here we introduce a modified procedure called 'boundary strong disorder renormalization' that preserves the tree structure, so that one can write simple recursions with respect to the number of generations. We first show that this modified procedure allows one to recover exactly most of the critical exponents for the one-dimensional chain. After this important check, we study the RG equations for the quantum Ising model on a Cayley tree with a uniform ferromagnetic coupling J and random transverse fields with support [ h min , h max ]. We find the following picture: (i) for J > h max , only bonds are decimated, so that the whole tree is a quantum ferromagnetic cluster; (ii) for J < h min , only sites are decimated, so that no quantum ferromagnetic cluster is formed, and the ferromagnetic coupling to the boundary coincides with the partition function of a directed polymer model in a random medium; (iii) for h min < J < h max , both sites and bonds can be decimated, and the quantum ferromagnetic clusters can either remain finite (the physics is then similar to (ii), with a quantitative mapping to a modified directed polymer model) or an infinite quantum ferromagnetic cluster appears. We find that the quantum transition can be of two types: (a) either the quantum transition takes place in the region where quantum ferromagnetic clusters remain finite, and the singularity of the ferromagnetic coupling to the boundary involves the typical correlation length exponent ν typ = 1; (b) or the quantum transition takes place at the point where an extensive quantum ferromagnetic cluster appears, with a correlation length exponent ν ≃ 0.75.
The cavity-field method, recently used for classical spin glasses, is extended to study the infinite-range Ising spin-glass model in a transverse field, by means of the Trotter-Suzuki transformation. Within this approach, which relies on well-known mathematics and deals with quantities that have transparent physical significance by avoiding the replica method, the quantum version of the classical Thouless-Anderson-Palmer equation is obtained. The phase diagram of the model is also obtained and full agreement with previous replica-method results is found.
A real-space renormalization-group treatment of random transverse-field Ising spin chains that was introduced previously is developed and extensively analyzed. It yields results that are asymptotically exact in the critical region near the zero-temperature para-to-ferromagnetic quantum phase transition. In particular, the exact scaling function is obtained for the magnetization as a function of a uniform applied magnetic field and the distance to the critical point, and up to the solution of a linear ordinary differential equation whose solution can be exhaustively analyzed, the scaling function of the average spin-spin correlation function is also obtained. Thus more exact information is obtainable about the critical behavior for this random model than is known for the pure version which is equivalent to the two-dimensional Ising model. The basic reason for this is the extremely broad distribution of energy scales that occurs at low energies near the critical point of the random system. For the random chain the distribution of the magnetization of the first spin in a semi-infinite system is also studied and the results found to agree in the scaling limit with results of McCoy obtained from the exact solution of the closely related McCoy-Wu Ising model; this provides strong justification for the validity of the present approach. The singular properties of the weakly ordered and weakly disordered ``Griffiths' phases'' that occur at zero temperature near the critical point are also studied, as well as the behavior at low but nonzero temperature. Possible extensions of the results and general lessons drawn from them for other random systems are briefly discussed.
For the quantum Ising model with ferromagnetic random couplings J i , j > 0 and random transverse fields h i > 0 at zero temperature in finite dimensions d > 1, we consider the lowest order contributions in perturbation theory in ( J i , j / h i ) to obtain some information on the statistics of various observables in the disordered phase. We find that the two-point correlation scales as , where ξ typ is the typical correlation length, u is a random variable and ω coincides with the droplet exponent ω DP ( D = d − 1) of the directed polymer with D = ( d − 1) transverse directions. Our main conclusions are as follows. (i) Whenever ω > 0, the quantum model is governed by an infinite-disorder fixed point: there are two distinct correlation length exponents related by ν typ = (1 − ω)ν av ; the distribution of the local susceptibility χ loc presents the power-law tail P (χ loc ) ∼ 1/χ 1 + μ loc , where μ vanishes as ξ −ω av so that the averaged local susceptibility diverges in a finite neighborhood 0 < μ < 1 before criticality (Griffiths phase); the dynamical exponent z diverges near criticality as z = d /μ ∼ ξ ω av . (ii) In dimensions d ⩽ 3, any infinitesimal disorder flows toward this infinite-disorder fixed point with ω( d ) > 0 (for instance ω( d = 2) = 1/3 and ω( d = 3) ∼ 0.24). (iii) In finite dimensions d > 3, a finite disorder strength is necessary to flow toward the infinite-disorder fixed point with ω( d ) > 0 (for instance ω( d = 4) ≃ 0.19), whereas a finite-disorder fixed point remains possible for a small enough disorder strength. For the Cayley tree of effective dimension d = ∞, where ω = 0, we discuss the similarities and differences with the case of finite dimensions.