This thesis concerns itself with two fundamental tasks in the theory of quantum information: the preparation of ground and low-energy states of local Hamiltonians on a quantum computer and the secure transmission of classical information over a quantum channel. The first part of this thesis addresses the former task and is dedicated in its entirety to quantum many-body physics. We will be focusing on topologically ordered lattice models in two spatial dimensions. It is known that the presence of long-range entanglement in the ground states of these models necessitates local quantum circuits of depth linear in the diameter of the system for their preparation. We study the consequences of this hardness result for the preparation of low-energy states of these models. In particular we show that preparing such states requires local quantum circuits of polynomial depth in the inverse energy density of the states and comment on the relevance of these results to quantum computation in the near term. Our technical contribution is to give a circuit depth lower bound for low-energy states independent of the dimension of the ground space. We then experimentally demonstrate how currently existing ion trap hardware has reached a level of maturity where noisy adaptive circuits of constant depth outperform noiseless, non-adaptive circuits of the same depth for the task of approximating a ground state of the the toric code. In the last part of this thesis, we switch gears to quantum Shannon theory and study private communication over a classical-quantum wiretap channel. We study the problem of non-additivity of the private information for this model. Surprisingly, we find that the private information is non-additive when either of the outputs of the channel is allowed to be quantum, while the input is classical. However, there exists a single-letter formula when the input state is quantum and the outputs are classical due to the private information of the channel becoming additive.
This thesis concerns itself with two fundamental tasks in the theory of quantum information: the preparation of ground and low-energy states of local Hamiltonians on a quantum computer and the secure transmission of classical information over a quantum channel. The first part of this thesis addresses the former task and is dedicated in its entirety to quantum many-body physics. We will be focusing on topologically ordered lattice models in two spatial dimensions. It is known that the presence of long-range entanglement in the ground states of these models necessitates local quantum circuits of depth linear in the diameter of the system for their preparation. We study the consequences of this hardness result for the preparation of low-energy states of these models. In particular we show that preparing such states requires local quantum circuits of polynomial depth in the inverse energy density of the states and comment on the relevance of these results to quantum computation in the near term. Our technical contribution is to give a circuit depth lower bound for low-energy states independent of the dimension of the ground space. We then experimentally demonstrate how currently existing ion trap hardware has reached a level of maturity where noisy adaptive circuits of constant depth outperform noiseless, non-adaptive circuits of the same depth for the task of approximating a ground state of the the toric code. In the last part of this thesis, we switch gears to quantum Shannon theory and study private communication over a classical-quantum wiretap channel. We study the problem of non-additivity of the private information for this model. Surprisingly, we find that the private information is non-additive when either of the outputs of the channel is allowed to be quantum, while the input is classical. However, there exists a single-letter formula when the input state is quantum and the outputs are classical due to the private information of the channel becoming additive.
We prove a nontrivial circuit-depth lower bound for preparing a low-energy state of a locally interacting quantum many-body system in two dimensions, assuming the circuit is geometrically local. For preparing any state which has an energy density of at most ε with respect to Kitaev's toric code Hamiltonian on a two dimensional lattice Λ, we prove a lower bound of Ω(min(1/ε21−α,∣Λ∣)) for any α>0. We discuss two implications. First, our bound implies that the lowest energy density obtainable from a large class of existing variational circuits (e.g., Hamiltonian variational ansatz) cannot, in general, decay exponentially with the circuit depth. Second, if long-range entanglement is present in the ground state, this can lead to a nontrivial circuit-depth lower bound even at nonzero energy density. Unlike previous approaches to prove circuit-depth lower bounds for preparing low energy states, our proof technique does not rely on the ground state to be degenerate.
This dissertation studies the interplay between quantum and classical computational resources through the lens of computational complexity theory. Part I considers low-energy states of quantum systems. We study the complexity of estimating ground- and excited-state energies of local Hamiltonians, given access to a guiding state promised to have non-negligible overlap with the relevant eigenspace. We formalise access models for such guiding states, examine their properties and relations, and study the problem for physically motivated Hamiltonians. We also study the task of obtaining approximate descriptions of ground states, given QMA-oracle access, in the setting of low-locality reduced density matrices. Part II focuses on quantum probabilistically checkable proof systems (QPCPs). We define a general class of QPCPs that allows adaptivity and multiple unentangled provers, and study its relationship to constant-gap local Hamiltonian problems via quantum reductions. Additionally, we investigate quantum–classical PCPs (QCPCPs), where a quantum verifier has either classical or quantum query access to a classical proof. Part III explores alternative complexity measures: unitary query complexity and sample complexity. For unitary query complexity, we develop a lower-bound technique based on unitary channel discrimination. In the context of sample complexity, we introduce and analyse a new sample-to-sample task, called complement sampling, and study the power of quantum computation with quantum samples over their classical counterparts.
We show that the low-energy states of non-Abelian topological orders possess extensive magic which is long-ranged, and cannot be eliminated by a constant-depth local unitary circuit. This refines conventional notions of complexity beyond the linear circuit depth which is required to prepare any topological phase, and provides a new resource-theoretic characterization of topological orders. A central technical result is a no-go theorem establishing that stabilizer states--even up to constant-depth local unitarie--cannot approximate low-energy states of non-Abelian string-net models which satisfy the entanglement bootstrap axioms. Moreover, we show that stabilizer-realizable Abelian string-net phases have mutual braiding phases quantized by the on-site qudit dimension, and that any violation of this condition necessarily implies extensive long-range magic. Extending to higher spatial dimensions, we argue that any state obeying an entanglement area law and hosting excitations with nontrivial fusion spaces must exhibit extensive long-range magic. This applies, in particular, to ground-states and low-energy states of higher-dimensional quantum double models.
Quantum computers hold the potential of solving problems that are intractable using classical means. Yet, to date no quantum computer has actually solved a problem of general interest that could not have been solved otherwise. Bridging this gap from promised theoretical usefulness to practical relevance is an interdisciplinary challenge, requiring experimental progress, solutions of classical software challenges as well as advances in quantum algorithm design. It is these final two points in which this thesis aims to contribute. One of the most promising quantum computing architectures is based on trapping ions in surface-electrode ion-traps. In order to productively operate such trapped-ion quantum computers, we develop and benchmark a compiler that optimizes ion shuttling sequences in order to efficiently map abstract quantum circuits onto a physical trapped-ion chip. This is a necessary component of the infrastructure of a quantum computing setup, however it is alone not sufficient to execute arbitrary quantum algorithms. In particular, a very promising class of quantum algorithms are so-called hybrid quantum-classical algorithms which leverage the computational resources of both quantum and classical computers. To effectively implement such algorithms, a suitable software setup is necessary to allow for tight interplay between the two types of computers without wasting precious coherence time. To solve this challenge, we propose, implement and benchmark our setup for Interpreted Quantum-Classical Computations (IQCCs), demonstrating its feasibility for trapped-ion quantum computers. For the second part of this thesis we focus on the development of quantum algorithms that make use of this setup. As a first application, we investigate quantum simulations of gauge theories. Such theories are prevalent throughout modern physics and are characterized by local constraints that the dynamics are subject to. Errors in noisy simulations of such theories results in these constraints being violated and the simulations becoming unphysical. We show that this problem can be remedied by measuring gauge operators, decoding possible errors on a classical computer and actively correcting them, which reduces simulation errors. Additionally we interpret the scheme as a sympathetic cooling setup, which allows thermal control of the simulation. We finally turn to the task of preparing ground states of frustration-free Hamiltonians in quantum computers. Studying ground states of various systems is of paramount importance for solving optimization problems and understanding phenomena such as magnetism, superconductivity and superfluidity. We frame the ground-state preparation problem as an error correction problem, wherein energy is measured locally, measurements are decoded and corrections are applied to reduce the energy. In physically relevant examples we show up to exponentially improved runtimes over previous, similar algorithms and give a general run-time bound in terms of the Hamiltonian gap.
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum p-spin glasses, random Hamiltonians whose interactions act on p-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement.
We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with n, we prove that, for all sufficiently large fixed p, any circuit preparing an n-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth Ωp(logn). In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed D, a sufficiently large degree prefactor rules out depth-D preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits.
Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
This thesis concerns itself with the role locality plays in the performance of quantum codes. We first address the difficulty of producing codestates from relatively good codes, specifically we investigate the depth of geometrically local encoding circuits. Previous results struggled to produce bounds allowing for general, non-local classical communications in the circuit. We show that, owed to the entanglement hidden in codestates, the depth of encoding circuits is lower bounded, even when allowing for boundless classical computation. We then move on to address a converse question: given a particular code, what can we say about its geometrical structure? We show that implementing stabiliser codes requires satisfying some connectivity requirements that depend on k and d. We quantify these requirements through the notion of graph expansion. Finally, in the last chapter, we ask the question of the achievability of these requirements. The celebrated BPT bound states upper bound on the parameters that can be achieved for codes local in three dimensions. We provide the first construction that matches this bound.