These are lecture notes from a weeklong course in quantum complexity theory taught at the Bellairs Research Institute in Barbados, February 21-25, 2016. The focus is quantum circuit complexity---i.e., the minimum number of gates needed to prepare a given quantum state or apply a given unitary transformation---as a unifying theme tying together several topics of recent interest in the field. Those topics include the power of quantum proofs and advice states; how to construct quantum money schemes secure against counterfeiting; and the role of complexity in the black-hole information paradox and the AdS/CFT correspondence (through connections made by Harlow-Hayden, Susskind, and others). The course was taught to a mixed audience of theoretical computer scientists and quantum gravity / string theorists, and starts out with a crash course on quantum information and computation in general.
These are lecture notes from a weeklong course in quantum complexity theory taught at the Bellairs Research Institute in Barbados, February 21-25, 2016. The focus is quantum circuit complexity---i.e., the minimum number of gates needed to prepare a given quantum state or apply a given unitary transformation---as a unifying theme tying together several topics of recent interest in the field. Those topics include the power of quantum proofs and advice states; how to construct quantum money schemes secure against counterfeiting; and the role of complexity in the black-hole information paradox and the AdS/CFT correspondence (through connections made by Harlow-Hayden, Susskind, and others). The course was taught to a mixed audience of theoretical computer scientists and quantum gravity / string theorists, and starts out with a crash course on quantum information and computation in general.
The AdS/CFT correspondence and quantum entanglement (or quantum information). This is one of topics exciting many physicists in this decade. And black holes always play a role of inspiring lab in many cases. In this thesis, we will discuss about scrambling of quantum entanglement and complexity of states in AdS/CFT. In both topics, black holes are expected to be the fastest processors of quantum information. This thesis contains brief reviews of each topics and our own works. One work is an explicit calculation of fast scrambling time in two dimensional holographic CFTs and three dimensional BTZ black holes using the two-sided mutual information. This calculation is a first CFT counterpart of Shenker-Stanford’s work in the gravity dual and an extension of their shock-wave approximation to finite time region in the gravity side. Another work is about socalled optimization procedure of Euclidean path- integrals in CFTs. The optimization procedure gives us a new way to extract dual geometries only from CFT data. And it also gives a new proposal for the definition of complexity of states in CFTs.
We present a collection of recent results concerning quantum information theory applied to quantum gravity. We first study the entanglement structure of Euclidean path integral states in SU(2) Chern-Simons theory, where we elucidate a connection between topological entanglement and quantum mechanical entanglement. We prove that the topology of certain three-manifolds controls the entanglement structure of the resulting quantum state, and conjecture a more general relationship for arbitrary three-manifolds. We then analyze the quantum circuit complexity of the time evolution operator in the Sachdev-Ye-Kitaev model, a theory of near-extremal black hole microstates. We find that this complexity grows linearly for a time exponential in the entropy, modulo a caveat concerning global obstructions to the growth of the distance function along geodesics, which we do not rule out. This constitutes a partial proof of Susskind’s conjecture about the complexity growth of black holes. Finally, we address the black hole information paradox in three dimensions by considering a toy model of black hole microstates in the form of an end-of-the-world brane. This brane carries a quantum theory which is itself holographic, and we compute entanglement entropies in the glued dual geometry by using a Ryu-Takayanagi formula where the minimal entropy surface can pass through the gluing surface.
Abstract Quantum computational complexity estimates the difficulty of constructing quantum states from elementary operations, a problem of prime importance for quantum computation. Surprisingly, this quantity can also serve to study a completely different physical problem – that of information processing inside black holes. Quantum computational complexity was suggested as a new entry in the holographic dictionary, which extends the connection between geometry and information and resolves the puzzle of why black hole interiors keep growing for a very long time. In this pedagogical review, we present the geometric approach to complexity advocated by Nielsen and show how it can be used to define complexity for generic quantum systems; in particular, we focus on Gaussian states in QFT, both pure and mixed, and on certain classes of CFT states. We then present the conjectured relation to gravitational quantities within the holographic correspondence and discuss several examples in which different versions of the conjectures have been tested. We highlight the relation between complexity, chaos and scrambling in chaotic systems. We conclude with a discussion of open problems and future directions. This article was written for the special issue of EPJ-C Frontiers in Holographic Duality.
These notes introduce a handful of core ideas from quantum information science that figure prominently in modern research on quantum gravity. The central concept that forms the base of these notes is that of a quantum channel; that is, the most general physically-reasonable map between quantum states and between operators on Hilbert space. After reviewing some fundamentals, we will study channels and their properties, and then go on to formulate quantum error correction in terms of quantum channels. Along the way, we will see how a handful of problems in high energy physics, such as the black hole information problem and bulk reconstruction in AdS/CFT, can be cast in the information-theoretic language being set up.
Entanglement and circuit complexity are fundamental concepts in quantum information theory which turned out to have considerable applications in various contexts ranging from many-body systems and condensed matter theory to quantum gravity and black hole physics. In order to find connections between these aspects, an insightful approach consists in comparing the complexity with some entanglement measures of a given bipartition, as for instance the Von Neumann entanglement entropy. Since, for a system in a given quantum state, the bipartite entanglement can be determined once a spatial subsystem and its complement are chosen, this comparison has to be made considering the complexity of reduced density matrices. This motivates the development of techniques for determining the circuit complexity of mixed states. In this thesis, focussing on free bosonic systems, we study the circuit complexity of mixed Gaussian states by employing the Fisher information geometry for the covariance matrices. This approach allows computing the complexity between reduced density matrices (subsystem complexity), as well as the complexity between thermal states. It also leads to a precise prescription for computing the spectrum and the basis complexity and the temporal evolution of the subsystem complexity after global and local quantum quenches. The study of the subsystem complexity of a given bipartition and a complete characterisation of its entanglement requires the detailed knowledge of the corresponding reduced density matrix, or, equivalently, of the entanglement Hamiltonian. A part of this thesis is devoted to determining the entanglement Hamiltonians in free theories. At equilibrium, we consider gapless systems, with the aim of recovering the underlying CFT results, and gapped lattice models. The evolution of entanglement Hamiltonians in quantum chains after a global quench is also studied. In addition, other entanglement quantifiers, as the entanglement spectrum and the contour for the entanglement entropies, are discussed in some of these settings. Finally, motivated by theoretical and experimental advances, we also address the issue of how the entanglement splits into the different charge sectors of a system endowed with a U(1) symmetry. We focus in particular on massive theories, either continuous or on the lattice, and we try to understand whether the entanglement equipartition, which is known to characterise gapless systems, survives away from criticality.
This thesis studies the complexity, thermalization, and entanglement properties of quantum mechanical systems and the implications of their behavior in high energy and condensed matter models. In Chapter 2, we use the geometry of Lie groups to study the circuit complexity of quantum mechanical systems and develop the technology to analytically predict the appearance of the obstruction to the complexity growth of integrable systems. We simulate the spin and fermionic systems, in which the amount of chaos can be controlled, and conjecture the close relation between quantum complexity and thermalization. In Chapter 3, we apply quantum information theory to an evaporating black hole in Jackiw-Teitelboim gravity in the context of AdS/CFT as a quantum error correction protocol. By calculating the entropy measures using gravitational path integrals, we establish the criterion for an error in the Hawking radiation to be correctable and identify the transition in the reversibility of the error channel as the Page transition. In Chapter 4, we study a 1+1 dimensional random circuit with measurement and dissipation. We map this type of quantum system to a classical Ising model analytically and show that the entanglement dynamics can be understood as the thermodynamics of the domain wall formed in the spin model, as one of the spatial dimensions stretches. We then confirm the calculated time scales in the classical theory qualitatively with simulations of realistic qubit circuits. Overall, we present a holistic picture of quantum systems, from those evolving with pure unitary, to those evolving also with influence from the environment. The complexity of the theory and entanglement of the states exhibit universal behavior at early times (∼ O(N)) and distinct long-time behavior, determined by their thermalization properties in spin chains, toy models of black holes in AdS/CFT, and monitored random circuits with dissipation.