This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable $X$ into a sum of $n$ iid random variables $Y_i$, i.e. $X=\sum_{i=1}^n Y_i$, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable X into a sum of n iid random variables Yi, i.e. X=∑i=1nYi, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
This dissertation concerns the quantum many-body problem, which is the problem of predicting the properties of systems of several quantum particles from the first principles of quantum mechanics. Included under this umbrella are various problems of fundamental importance in quantum chemistry, condensed matter physics, and materials science. Of particular interest is the electronic structure problem, the problem of determining the state of the electrons in a system with fixed atomic nuclei. Since direct numerical solution of the many-body Schrödinger equation is intractable even for systems of moderate size, a diverse array of approximate methods has been developed. The broad goals of this dissertation are to improve the mathematical understanding of certain widely-used approximations, as well as to propose new methods. Roughly speaking, we consider three (overlapping) categories of methods: Green's function methods, embedding methods, and variational methods.One can understand Green's function methods in terms of many-body perturbation theory, which computes series expansions of physical quantities about a non-interacting reference system. These expansions can be expressed graphically in terms of Feynman diagrams, which can in turn be reorganized, in some cases, into an expansion in terms of so-called bold diagrams. Green's function methods can be specified by choosing a subset of bold diagrams to approximate the sum. At the same time, such methods can be understood in terms of an object known as the Luttinger-Ward (LW) functional, which admits a representation in terms of the bold diagrams. Many aspects of these constructions are purely formal, and indeed the existence of the fermionic LW functional as a single-valued functional has recently been called into question. To contribute to the understanding of these issues, we provide rigorous proofs of the combinatorial construction and analytic interpretation of the bold diagrams in the simplified setting of a classical field theory. In this setting we also provide a rigorous non-perturbative construction of the LW functional via convex duality and prove several key properties, including continuity up to the boundary of its domain and asymptotics in the limit of large interaction.Quantum embedding methods, meanwhile, view a large system as being composed of smaller fragments that are treated with high accuracy and embedded in the larger system in a mutually consistent way. Inspired by a connection between the boundary analysis of the LW functional and embedding, we perform similar analysis for the 1-RDM theory for fermionic systems, which is also developed via convex duality, illustrating a relation to fermionic embedding methods such as the density matrix embedding theory (DMET).Another embedding method of note is the dynamical mean-field theory (DMFT), which is at the same time a Green's function method that can be understood in terms of the LW functional. DMFT relies on the solution of impurity problems, which specify the embedding of an interacting system into a non-interacting bath. Underlying DMFT is a result about the sparsity pattern of the self-energy matrix for impurity problems, which to our knowledge has not been proved in the literature. We provide a rigorous proof of this result in various classical and quantum settings. We go on to investigate the fermionic DMFT in depth, identifying the key mathematical structures that appear in the algorithmic loop for solving it and using these to prove the well-posedness of this loop, in a certain sense.Finally, we introduce a suite of new approaches to the quantum many-body problem that provide variational lower bounds to the ground-state energy. These methods, which combine the themes of convexity and embedding, are based on novel convex relaxations of the variational principles for the ground-state energies of many-body systems. To begin, we recover a second-quantized version of the formalism of strictly correlated electrons (SCE), which yields an exact expression for the exchange-correlation functional in Kohn-Sham density functional theory in the limit of infinite Coulomb repulsion in terms of the solution of a multi-marginal optimal transport problem. We introduce a semidefinite relaxation method for approximately solving this problem and obtaining a lower bound for the ground-state energy. The ideas underlying this relaxation are generalized considerably, outside the context of SCE, to yield much tighter lower bounds, which we validate numerically for both quantum spin systems and fermionic systems. We also describe how these relaxation methods can be interpreted as embedding methods via convex duality.
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.
The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.
A central theme in the field of quantum many-body physics is the characterization of thermal properties, which can be accessed, for instance, through the analysis of the Hamiltonian spectrum. This thesis approaches the problem from both numerical and analytical viewpoints, treating the spectrum as a statistical object whose correlations encode predictive information about the physics of the underlying system. In the first part of this thesis, we review the relation between thermalization, quantum integrability and chaos in one-dimensional quantum many-body systems. We focus on the statistics of energy levels and establish whether quantum integrability can be assessed from a statistical viewpoint. We then consider the problem of intermediate statistics between purely integrable and non-integrable quantum many-body systems. The first contribution of this thesis is an answer to the problem of discriminating between the spectrum of a genuine integrable system and a statistical mixture of, possibly exponentially many, non-ergodic sectors. We show that the spectral decimation algorithm can capture both qualitative and quantitative features of a `characteristic symmetry sector' from an unbiased analysis of numerically available spectral data. When applied to physically relevant systems, the algorithm is able to identify traces of Hilbert space fragmentation and disorder-induced many-body localization. The second part of this thesis is dedicated to a class of Hamiltonians of particular interest to statistical spectroscopy. Such Hamiltonians involve only the permutation of sites without the presence of external interactions. Nonetheless, they generate a highly tunable and numerically implementable class of models. For instance, it is easy to engineer integrability and its breaking while preserving essential structures such as the block-diagonal decomposition. These Hamiltonians are naturally suited to generating unitary random walks on the permutation group, which can, for instance, be compared with their classical counterparts. After a detailed discussion of the numerical implementation of these Hamiltonians and their spectral properties, we depart from the analysis of the system's static properties to answer a genuine out-of-equilibrium question: do quantum coherences accelerate mixing in the computational basis? We consider an exactly solvable class of quantum stochastic walks which, in the absence of quantum coherences, admit a limit coinciding with a classical continuous-time Markov chain. While the trace distance of the associated density matrices from the maximally mixed state remains identical to that in the classical limit, we show that the probability distance in the presence of quantum coherences, which defines mixing in the computational basis, is upper bounded by the classical limit. An analysis of the slowest mode identifies a necessary condition under which quantum coherences and classical mixing become of the same order, thereby defining a slow-mode time scale. Finally, a numerical analysis of quantum stochastic walks based on random transpositions corroborates the analytical findings, in particular the accelerated mixing. We also identify a closed-form expression for the ratio of quantum to classical mixing times, which yields a collapse over numerically accessible system sizes. Overall, this thesis presents a modern approach to the theory of statistical spectroscopy by proposing analytically grounded and numerically implementable protocols to ascertain the thermal properties of a one-dimensional quantum many-body system from the analysis of the spectrum within numerically accessible volumes. It also shows that the analysis of the statistical properties of Hamiltonians can be of practical aid in the study of out-of-equilibrium properties of quantum many-body systems, such as mixing in quantum stochastic walks.
Determining properties of ground states of spin Hamiltonians remains a topic of central relevance connecting disciplines of mathematical, theoretical and applied physics. In the last few decades, ground state properties of physical systems have been increasingly considered as computational resources. This thesis develops parts of the mathematical apparatus to create (program) ground states relevant for quantum and classical computation. The core findings presented in this thesis (now over a decade old) including that (i) logic operations (gates) can be embedded into the low-energy sector of Ising spins whereas three (and higher) body Ising interaction terms can be mimicked through the minimisation of 2- and 1-body Ising terms yet require the introduction of slack spins; (ii) Perturbation theory gadgets enable the emulation of interactions not present in a given Hamiltonian, e.g.~YY interactions can be realized from ZZ, XX, the thesis contains a result from 2007 showing that physically relevant two-body model Hamiltonian's have a QMA-hard ground state energy decision problem. Merged with other results, this established that these models provide a universal resource for ground state quantum computation. More recent findings include the proof that an idealised version of the contemporary variational approach to quantum algorithms enables a universal model of quantum computation. Other related results are also presented as they relate to ground state quantum computation and the minimisation of Hamiltonians by quantum circuits. The topics covered include: Ising model reductions, stochastic versus quantum processes on graphs, quantum gates and circuits as tensor networks, variational quantum algorithms and Hamiltonian gadgets.
A central question in quantum many-body physics is estimating the ground energy of a k-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random n-qubit Hamiltonian system defined as the sum of signed k-local Pauli operators. In particular, we prove that for any constant ℓ, there exists an efficiently computable length nO(ℓ) certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an ε-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on k-XOR refutations to k-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed k-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) Ω(logn)-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to Ω(n)-levels.