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.
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.
Phase transitions and their associated critical phenomena are of fundamental importance and play a crucial role in the development of statistical physics for both classical and quantum systems. Phase transitions embody diverse aspects of physics and also have numerous applications outside physics, e.g., in chemistry, biology, and combinatorial optimization problems in computer science. Many problems can be reduced to a system consisting of a large number of interacting agents, which under some circumstances (e.g., changes of external parameters) exhibit collective behavior; this type of scenario also underlies phase transitions. The theoretical understanding of equilibrium phase transitions was put on a solid footing with the establishment of the renormalization group. In contrast, non-equilibrium phase transition are relatively less understood and currently a very active research topic. One important milestone here is the Kibble-Zurek (KZ) mechanism, which provides a useful framework for describing a system with a transition point approached through a non-equilibrium quench process. I developed two efficient Monte Carlo techniques for studying phase transitions, one is for classical phase transition and the other is for quantum phase transitions, both are under the framework of KZ scaling. For classical phase transition, I develop a non-equilibrium quench (NEQ) simulation that can completely avoid the critical slowing down problem. For quantum phase transitions, I develop a new algorithm, named quasi-adiabatic quantum Monte Carlo (QAQMC) algorithm for studying quantum quenches. I demonstrate the utility of QAQMC quantum Ising model and obtain high-precision results at the transition point, in particular showing generalized dynamic scaling in the quantum system. To further extend the methods, I study more complex systems such as spin-glasses and random graphs. The techniques allow us to investigate the problems efficiently. From the classical perspective, using the NEQ approach I verify the universality class of the 3D Ising spin-glasses. I also investigate the random 3-regular graphs in terms of both classical and quantum phase transitions. I demonstrate that under this simulation scheme, one can extract information associated with the classical and quantum spin-glass transitions without any knowledge prior to the simulation.
Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind. We apply tools from computer science and mathematical physics to study the complexity of simulating quantum systems. In general, our goal is to identify parameter regimes under which simulating quantum systems is easy (efficiently solvable) or hard (not efficiently solvable). This study leads to an understanding of the features that make certain problems easy or hard to solve. We also get physical insight into the behavior of the system being simulated. In the first part of this dissertation, we study the classical complexity of simulating quantum dynamics. In general, the systems we study transition from being easy to simulate at short times to being harder to simulate at later times. We argue that the transition timescale is a useful measure for various Hamiltonians and is indicative of the physics behind the change in complexity. We illustrate this idea for a specific bosonic system, obtaining a complexity phase diagram that delineates the system into easy or hard for simulation. We also prove that the phase diagram is robust, supporting our statement that the phase diagram is indicative of the underlying physics. In the next part, we study open quantum systems from the point of view of their potential to encode hard computational problems. We study a class of fermionic Hamiltonians subject to Markovian noise described by Lindblad jump operators and illustrate how, sometimes, certain Lindblad operators can induce computational complexity into the problem. Specifically, we show that these operators can implement entangling gates, which can be used for universal quantum computation. We also study a system of bosons with Gaussian initial states subject to photon loss and detected using photon-number-resolving measurements. We show that such systems can remain hard to simulate exactly and retain a relic of the "quantumness" present in the lossless system. Finally, in the last part of this dissertation, we study the complexity of simulating a class of equilibrium states, namely ground states. We give complexity-theoretic evidence to identify two structural properties that can make ground states easier to simulate. These are the existence of a spectral gap and the existence of a classical description of the ground state. Our findings complement and guide efforts in the search for efficient algorithms.
Recently, the possibility of investigating single molecule, or single spin observables, as well as the necessity of a better understanding of the mechanisms underlying quantum dynamics in order to obtain nanoscale devices and nanostructered materials suitable for quantum computing tasks, have revived the interest in foundational aspects of quantum statistical mechanics. This thesis aims to give a contribution to this field by re-considering the statistical characterization of a quantum system at the light of some paradigmatic changes in our understanding of quantum theory which have taken place in the last two decades. In particular the impressive development of quantum information theory has changed the perceptions of quantum entanglement: for a long time it has been considered a somewhat paradoxical property of the matter at the atomic scale, but now it is regarded as an essential and ubiquitous phenomenon whose consequences are affecting the very macroscopic world that we experience. Still the decoherence program has brought out the importance of considering a quantum system together with its environment in order to clarify some key aspects of quantum dynamics. Thus, we start from the idea that quantum correlations are ubiquitous and somewhat uncontrollable in systems with many degrees of freedom which are typically considered in statistical mechanics. As a consequence we assume the standpoint that quantum statistical mechanics has not to be based on the underlying idea of a collection of many, independent quantum systems but rather it has to emerge at the level of a global wavefunction (pure state) which describes the system as well as its environment as a whole. In order to investigate the consequences of these assumptions we study the equilibrium distribution of an isolated quantum system. This is defined, in analogy with the ergodic foundations of classical statistical mechanics, on the basis of the time evolution of the quantum state. Then, we study the emergence of thermodynamic properties in a quantum system by studying the probability distribution of some function of interests, as the entropy and the equilibrium state of a subsystem, on Ensembles of Pure States. Such a probability distribution is derived from the geometry of the Hilbert space, and the theoretical tools suitable for its characterization are developed. On the one hand we perform a numerical sampling of the ensemble distributions by employing Monte Carlo techniques, on the other hand simpler analytical approximation of the geometrical distributions are derived by means of a maximum entropy principle. Model systems composed of an ensemble of spins are chosen to illustrate the salient features which emerge from the developed theoretical framework: the main point is that the Ensemble Distributions of “thermodynamic observables” (entropy or equilibrium state of a subsystem) are sharply peaked around a typical value. From the analysis it emerges that each of the overwhelming majority of the wavefunctions which has appreciable weight in the considered ensemble, is characterized by the same value of the “macroscopic” functions. This is a striking evidence of the “typicality” of these properties. In the essence, our impossibility to know the state of the system in detail does not matter, just for the remarkable fact that almost all quantum states behave essentially in the same way. By virtue of this typicality the study of the behaviour of the typical values of the thermodynamic function become meaningful. Notably, under certain conditions, one recovers the results of standard statistical mechanics, that is, the equilibrium average of the state of a subsystem can be cast in the Boltzmann canonical form at the temperature given by the usual thermodynamical relation . In the second part of the thesis we consider the dynamical aspects of the equilibrium state of a subsystem interacting with its environment. The fluctuations around the equilibrium average critically depends on the entanglement between the system and the environment and on the form of the interaction Hamiltonian. The connection between the dynamics of the fluctuations of an observable at the equilibrium and the relaxation toward the equilibrium from a “non typical” initial value is also investigated with the aid of simple model systems. The study presented in this thesis was partly motivated by a critical analysis of the statistical methods available for the theoretical modelling of magnetic resonance experiments. One of these, the Stochastic Liouville Equation, has been employed in a work completed during the first year of my Ph.D. program in order to interpret some feature of a two dimensional electron spin resonance experiment, [Fresch B., Frezzato D., Moro G. J., Kothe G., Freed J. H.; J. Phys. Chem. B., 110, 24238, (2006)].
This thesis contains four studies of the effects of disorder and randomness on strongly correlated quantum phases of matter. Starting with an itinerant ferromagnet, I first use an order-by-disorder approach to show that adding quenched charged disorder to the model generates new quantum fluctuations in the vicinity of the quantum critical point which lead to the formation of a novel magnetic phase known as a helical glass. Switching to bosons, I then employ a momentum-shell renormalisation group analysis of disordered lattice gases of bosons where I show that disorder breaks ergodicity in a non-trivial way, leading to unexpected glassy freezing effects. This work was carried out in the context of ultracold atomic gases, however the same physics can be realised in dimerised quantum antiferromagnets. By mapping the antiferromagnetic model onto a hard-core lattice gas of bosons, I go on to show the importance of the non-ergodic effects to the thermodynamics of the model and find evidence for an unusual glassy phase known as a Mott glass not previously thought to exist in this model. Finally, I use a mean-field numerical approach to simulate current generation quantum gas microscopes and demonstrate the feasibility of a novel measurement scheme designed to measure the Edwards-Anderson order parameter, a quantity which describes the degree of ergodicity breaking and which has never before been experimentally measured in any strongly correlated quantum system. Together, these works show that the addition of disorder into strongly interacting quantum systems can lead to qualitatively new behaviour, triggering the formation of new phases and new physics, rather than simply leading to small quantitative changes to the physics of the clean system. They provide new insights into the underlying physics of the models and make direct connection with experimental systems which can be used to test the results presented here.
A broad range of quantum optimization problems can be phrased as the question of whether a specific system has a ground state at zero energy, i.e., whether its Hamiltonian is frustration-free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms to, at least, partially answer this question. Here we prove a general criterion-a sufficient condition-under which a local Hamiltonian is guaranteed to be frustration-free by lifting Shearer's theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hardcore lattice gas at negative fugacity on the Hamiltonian's interaction graph, which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics that permit us to obtain new bounds on the satisfiable to unsatisfiable transition in random quantum satisfiability. We are then led to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this work underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.
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.