As our demand for computational power grows, we encounter the question: "What are the physical limits to computation?" An answer is necessarily incomplete unless it can incorporate physics at the smallest scales, where we expect our near-term high-performance computing to occur. Microscopic physics -- namely, quantum mechanics -- behaves counterintuitively to our everyday experience, however. Quantum matter can occupy superpositions of states and build stronger correlations than are possible classically. This affects how quantum computers and quantum thermodynamic engines will behave. Though these properties may seem to overwhelmingly defeat our attempts to build a quantum computer at-first-glance, what is remarkable is that they can also be immensely helpful to computation. Quantum mechanics hinders and helps computation, and the nuanced details of how we perform computations are important. In this dissertation, we examine the transition between these two behaviors and connect it to a well-studied behavior in condensed matter physics, known as the many-body-localization transition. Our idea utilizes the fact that quantum many-body systems have an intrinsic fastest speed at which signals can travel. When this speed is maximal, we expect arbitrary universal quantum computation to be achievable, since strong quantum correlations, or entanglement, can be built quickly. When it is limited, however, the difficulty of the computation is classically simulatable. We demonstrate a similar transition in the amount of thermodynamic work that can be performed by a quantum system when entanglement is present. We first consider computations consisting of the evolution of a single particle or many noninteracting particles. When the number of such noninteracting particles is comparable to the total size of the system, we do not know of any way to simulate such computations classically. However, we find that we can still determine the fastest signal speed in such systems. We extend our result to interacting particles, which are universal for quantum computation, and observe a many-body-localization transition in a simple computational model using our algorithm. Finally, we apply ideas from quantum information to simulate the thermodynamic performance of a simple quantum system, showing that quantum effects can enable it to outperform its classical counterpart.
As our demand for computational power grows, we encounter the question: "What are the physical limits to computation?" An answer is necessarily incomplete unless it can incorporate physics at the smallest scales, where we expect our near-term high-performance computing to occur. Microscopic physics -- namely, quantum mechanics -- behaves counterintuitively to our everyday experience, however. Quantum matter can occupy superpositions of states and build stronger correlations than are possible classically. This affects how quantum computers and quantum thermodynamic engines will behave. Though these properties may seem to overwhelmingly defeat our attempts to build a quantum computer at-first-glance, what is remarkable is that they can also be immensely helpful to computation. Quantum mechanics hinders and helps computation, and the nuanced details of how we perform computations are important. In this dissertation, we examine the transition between these two behaviors and connect it to a well-studied behavior in condensed matter physics, known as the many-body-localization transition. Our idea utilizes the fact that quantum many-body systems have an intrinsic fastest speed at which signals can travel. When this speed is maximal, we expect arbitrary universal quantum computation to be achievable, since strong quantum correlations, or entanglement, can be built quickly. When it is limited, however, the difficulty of the computation is classically simulatable. We demonstrate a similar transition in the amount of thermodynamic work that can be performed by a quantum system when entanglement is present. We first consider computations consisting of the evolution of a single particle or many noninteracting particles. When the number of such noninteracting particles is comparable to the total size of the system, we do not know of any way to simulate such computations classically. However, we find that we can still determine the fastest signal speed in such systems. We extend our result to interacting particles, which are universal for quantum computation, and observe a many-body-localization transition in a simple computational model using our algorithm. Finally, we apply ideas from quantum information to simulate the thermodynamic performance of a simple quantum system, showing that quantum effects can enable it to outperform its classical counterpart.
We review the mathematical speed limits on quantum information processing in many-body systems. After the proof of the Lieb-Robinson Theorem in 1972, the past two decades have seen substantial developments in its application to other questions, such as the simulatability of quantum systems on classical or quantum computers, the generation of entanglement, and even the properties of ground states of gapped systems. Moreover, Lieb-Robinson bounds have been extended in non-trivial ways, to demonstrate speed limits in systems with power-law interactions or interacting bosons, and even to prove notions of locality that arise in cartoon models for quantum gravity with all-to-all interactions. We overview the progress which has occurred, highlight the most promising results and techniques, and discuss some central outstanding questions which remain open. To help bring newcomers to the field up to speed, we provide self-contained proofs of the field's most essential results.
Locality constrains the flow of information between different parts of many-body quantum systems. In quantum computers, this affects the ability to perform arbitrary interactions for quantum information processing tasks. A crucial challenge for scalable quantum architectures is thus to minimize the overheads due to locality constraints. Locality constraints also affect the way information and entanglement can be spread in many body quantum systems, and our ability to make predictions about such systems. One way to implement arbitrary interactions in locality-constrained architectures is by permuting qubits, also known as performing quantum routing. In the first part of this thesis, we investigate quantum routing strategies using emerging architectural capabilities beyond swap gates. We first investigate the use of mid-circuit measurements and classical feedback, which enable quantum teleportation. We prove upper bounds on the speedup afforded by the use of quantum teleportation for routing. We also design architectural connectivities which can exploit teleportation-based speedups. We then consider quantum routing by continuous-time Hamiltonian evolution, designing a routing algorithm that achieves a polynomial speedup in routing time over gate-based routing methods in architectures with a bottleneck, which is an intermediate region that constrains interactions between the rest of the device. We improve the lower bound on the time taken for routing in such systems, and develop a matching upper bound on the closely related task of generating and distributing entanglement. In the second part of this thesis, we investigate the behavior of finite-sized systems evolving by local Hamiltonians for a long duration. A major direction of research in condensed matter physics is the investigation of whether isolated systems thermalize (i.e., reach a state of thermal equilibrium). Various theoretical proposals such as information scrambling, entanglement between subsystems, and the eigenstate thermalization hypothesis have attempted to explain the conditions under which systems equilibrate. At the same time, notable counter-examples to thermalization have been found, such as systems that are integrable, exhibit many-body localization, or quantum many-body scars. We approach this question from a complexity-theoretic perspective. We show that the problem of deciding whether or not observables equilibrate to a givenvalue is PSPACE-complete. We also show that deciding whether observables relax to the thermal equilibrium value is contained in PSPACE, and is PSPACE-hard under quantum polynomial time reductions. These problems are thus intractable even for a quantum computer. Our results indicate that the proposed conditions leading to thermalization are either difficult to decide, or are not generic indicators of thermalization.
At the interface of quantum information and condensed matter physics, the study of entanglement in quantum many-body systems requires a new toolset which combines concepts from each. This thesis introduces a set of computational methods to study phases and phase transitions in lattice models of quantum systems, using the Renyi entropies as a means of quantifying entanglement. The scaling of entanglement entropy can give valuable insight into the phase of a condensed matter system. It can be used to detect exotic types of phases, to pinpoint transitions between phases, and can give us universal information about a system. \nThe first approach in this thesis is a technique to measure entanglement in finite size \nlattice systems using zero-temperature quantum Monte Carlo simulations. The algorithm \nis developed, implemented, and used to explore anomalous entanglement scaling terms in \nthe spin-1/2 Heisenberg antiferromagnet. \nIn the second part of this thesis, a new and complementary numerical technique is introduced to study entanglement not just in finite size systems, but as we approach the thermodynamic limit. This “numerical linked-cluster expansion” is used to study two different systems at their quantum critical points — continuous phase transitions occurring at zero temperature, at which these systems exhibit universal properties. Remarkably, these universal properties can be reflected in the scaling of entanglement. \nEntanglement offers a new perspective on condensed matter systems, one which takes us closer to genuinely understanding what goes on in these materials at the quantum mechanical level. This thesis demonstrates the first steps in developing an extensive list of computational tools that can be used to study entanglement over a wide range of interacting quantum many-body systems. With the ever increasing computational power available, it may be only a matter of time before these tools are used to create a comprehensive framework for the characterization of condensed matter phases and phase transitions.
Quantum mechanics led us to reconsider the scope of physics and its building principles, such as the notions of realism and locality. More recently, quantum theory has changed in an equally dramatic manner our understanding of information processing and computation. On one hand, the fundamental properties of quantum systems can be harnessed to transmit, store, and manipulate information in a more efficient and secure way than possible in the realm of classical physics. On the other hand, the development of systematic procedures to manipulate systems of a large number of particles in the quantum regime, crucial to the implementation of quantum-based information processing, has triggered new possibilities in the exploration of quantum many-body physics and related areas. In this thesis, we present new results relevant to two important problems in quantum information science: the development of a theory of entanglement, intrinsically quantum correlations, and the exploration of the use of controlled quantum systems to the computation and simulation of quantum many-body phenomena. In the first part we introduce a new approach to the study of entanglement
THESIS SUMMARYTEXT:This thesis is made of two parts. In the first one, the issue of entanglement in many body systems is addressed. The concept of entanglement and some of the recent progress on the study of entropy of entanglement in many body quantum systems are reviewed. Emphasis is placed on the scaling properties of entropy for one-dimensional models at quantum phase transitions. Then, we focus on the area-law scaling of the entanglement entropy. An explicit computation in arbitrary dimensions of the entanglement entropy of the ground state of a discretized scalar free field theory that shows the expected area law result is also presented. For this system, it is shown that area law scaling is a manifestation of a deeper reordering of the vacuum produced by majorization relations.To finish this first part, the issue of how simple can a quantum system be such as to give a highly entangled ground state is addressed. In particular, we propose a Hamiltonian of a XX model with a ground state whose entropy scales linearly with the size of the block. It provides a simple example of a one dimensional system of spin-1/2 particles with nearest neighbour interactions that violates area-law for the entanglement entropy.The second part of this thesis deals with the problem of simulating quantum mechanics for highly entangled systems. Two different approaches to this issue are considered. One consists of using ultra-cold atoms systems as quantum simulators. With this aim, some experimental techniques related to cold atoms that allow to simulate strongly correlated many body quantum systems are reviewed an explicit example of simulation is presented. In particular, we analyze how to achieve a Mott state of Laughlin wave functions in an optical lattice and study the consequences of considering anharmonic corrections to each single site potential expansion that were not taken into account until now.Finally, a different approach to simulate strongly correlated systems is considered: to use small quantum computers to simulate them. An explicit quantum algorithm that creates the Laughlin state for an arbitrary number of particles n in the case of falling fraction equal to one is presented. We further prove the optimality of the circuit using permutation theory arguments and we compute exactly how entanglement develops along the action of each gate. We also discuss its experimental feasibility decomposing the qudits and the gates in terms of qubits and two qubit-gates as well as the generalization to arbitrary falling fraction.KEYWORDS: Entanglement, Many body quantum systems, Quantum Information Condensed Matter, Cold atoms, Spin chains, Quantum simulator, Quantum computation.
The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. On a fundamental level, such an investigation sheds light on the intrinsic computational power that is harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-ups over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. On the other hand, classical simulation of many-body systems is a challenging task, as the dimension of the Hilbert space scales with the number of particles. Therefore, to understand the properties of the systems, suitable approximation methods need to be employed. The lectures will be divided into two parts. In the first part we discuss classical simulation of quantum computation from several perspectives. We review a number of well-known examples of classically simulatable quantum computations, such as the Gottesman-Knill theorem, matchgate simulation and tensor contraction methods. We further discuss simulation methods that are centred on classical sampling methods (‘weak simulation’), and illustrate how these techniques outperform methods that rely on the exact computation of measurement probabilities (‘strong simulation’). The second part focuses on "Entanglement and variational wavefunctions in quantum many body physics". We review the idea of entanglement in quantum many-body systems and how it helps us to understand the success of numerical renormalization group methods. In particular we will discuss a few variational wave-function based methods for simulating strongly correlated quantum systems, which include (1) matrix product states (2) multiscale entanglement renormalization ansatz (3) projected entangled pair states and (4) continuous matrix product states for quantum field theories.