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.
In this thesis we present new results relevant to two important problems in quantum information science: the development of a theory of entanglement and the exploration of the use of controlled quantum systems to the simulation of quantum many-body phenomena. In the first part we introduce a new approach to the study of entanglement by considering its manipulation under operations not capable of generating entanglement and show there is a total order for multipartite quantum states in this framework. We also present new results on hypothesis testing of correlated sources and give further evidence on the existence of NPPT bound entanglement. In the second part, we study the potential as well as the limitations of a quantum computer for calculating properties of many-body systems. First we analyse the usefulness of quantum computation to calculate additive approximations to partition functions and spectral densities of local Hamiltonians. We then show that the determination of ground state energies of local Hamiltonians with an inverse polynomial spectral gap is QCMA-hard. In the third and last part, we approach the problem of quantum simulating many-body systems from a more pragmatic point of view. We analyze the realization of paradigmatic condensed matter Hamiltonians in arrays of coupled microcavities, such as the Bose-Hubbard and the anisotropic Heisenberg models, and discuss the feasibility of an experimental realization with state-of-the-art current technology.
Quantum information theory is concerned with identifying how quantum mechanical resources, such as entangled quantum states, can be utilized for a number of information processing tasks, including data storage, computation, communication, and cryptography. Efficient quantum algorithms and protocols have been developed for performing some tasks (e.g., factoring large numbers, securely communicating over a public channel, and simulating quantum mechanical systems) that appear to be very difficult with just classical resources. In addition to identifying the separation between classical and quantum computational power, much of the theoretical focus in this field over the last decade has been concerned with finding novel ways of encoding quantum information that are robust against errors, which is an important step toward building practical quantum information processing devices. In this thesis I present some results on the quantum error-correcting properties of oscillator codes (also described as symplectic lattice codes) and toric codes. Any harmonic oscillator system, such as a mode of light, can be encoded with quantum information via symplectic lattice codes that are robust against shifts in the system's continuous quantum variables. I show the existence of lattice codes whose achievable rates match the one-shot coherent information over the Gaussian quantum channel. Also, I construct a family of symplectic self-dual lattices and search for optimal encodings of quantum information distributed between several oscillators. Toric codes provide encodings of quantum information into two-dimensional spin lattices that are robust against local clusters of errors and which require only local quantum operations for error correction. Numerical simulations of this system under realistic error models provide a calculation of the accuracy threshold for quantum memory using toric codes, which can be related to phase transitions in particular condensed matter models. I also present a local classical processing scheme for correcting errors on toric codes, which demonstrates that quantum information can be maintained in two dimensions by purely local quantum and classical resources.
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.
Developing quantum systems which are robust against noise are of prime importance to the realisation of quantum technologies. Without fault tolerance, we will never be able to preserve delicate quantum states for macroscopic time scales, a necessary requirement in the construction of scalable quantum computer. Topologically ordered models offer very beautiful mechanisms for preserving quantum states. In such models, quantum information is encoded globally over a degenerate topological Hilbert space which offers a natural robustness against local environmental noise. Remarkably, topological order is present in certain realistic condensed-matter systems. This provides a platform for accessing topological order in a laboratory. Moreover, considering condensed-matter systems enables us to combine topological features with other physical effects to enhance their behaviour. In this Thesis we study the physics of topologically ordered lattice models with defects. We seek practical applications of lattice defects for the realisation of a fault-tolerant quantum computer. The first result we present shows that anyonic data of point-like lattice defects, called twists, can be found by measuring the entanglement of the ground state of the host system. The data we learn relates to the capacity of a twist defect to perform quantum computational tasks. The second result in this Thesis concerns the dynamics of the qudit toric code model with line-like defects coupled to a thermal bath. We show we can entropically inspire fragile glassy dynamics in the system. Such dynamics qualitatively improve the coherence times of quantum information encoded in the ground state of the lattice. A novel way of achieving fault-tolerant quantum computation is by producing and manipulating twist defects of topologically ordered systems. In many ways, this paradigm of topological quantum computation is analogous to quantum computation using anyons. The first area of study in this Thesis extends the analogy between anyons and twists. Specifically, we show that the anyonic data of twists in Kitaev's toric code model can be extracted using topological entanglement entropy calculations in the same way as the same data can be extracted from anyons. We show this using a rigorously solvable lattice model as an example to produce exact analytic results. In particular, our results show we can extract the quantum dimension of a twist, and that we can study the quantum dimension of their fusion products. We compare the obtained results with the anyonic data of the Ising anyon model, further probing an analogy drawn previously in the literature. The second result presented in this Thesis shows that the application of lattice defects can introduce novel dynamics to a two-dimensional topologically ordered quantum memory where excitations carry different masses. A two-dimensional topological model which supports an anyon model with a splitting structure allowed by its fusion channels should be able to entropically achieve high-energy excitation configurations before quantum information encoded in its ground state decoheres. We introduce a grid of lattice defects to a local two-dimensional Hamiltonian model, which, when coupled to a thermal bath, will dynamically steer the excitations into high energy configurations with high probability within a suitable temperature regime. We demonstrate the proliferating dynamics using numerical simulations in a low-temperature regime where we show polynomial improvements in coherence times by increasing the system size for small system sizes, as well as coherence times which scale weakly super exponentially with the inverse temperature of the bath. The dynamics we demonstrate provide the first example of a system which entropically steers excitations into high-energy configurations. The dynamics we demonstrate may lead to the development of experimentally tractable architectures for low dimensional quantum memories. The study of thermal stability in this Thesis requires the development of methods of correcting topologically ordered lattices which have suffered errors. Namely, we require a decoding algorithm for the qudit generalisation of Kitaev's toric code. Further work presented in this Thesis compares rigorously two different decoding algorithms which use renormalisation-group techniques to process classical syndrome information about noise suffered by the topological code. In particular, we study the improvement in their thresholds as the local dimension of its physical systems increase. Our numerical results enable us to analyse and identify the limitations of the different methods of decoding.
The superposition principle of quantum mechanics implies that the amount of classical (i.e., non-quantum) information needed to describe a quantum system is in general exponentially large in the size of the system. This makes simulating quantum physics on a classical computer quickly infeasible, even for moderately-sized systems and using the best present-day supercomputers in the world. This is unfortunate, since systems for which quantum effects are relevant are of interest in many areas of science and engineering, ranging from drug design to materials research. In 1982, Richard Feynman gave birth to the idea of a quantum computer, when he realized that simulating quantum physics could be achieved much more efficiently with a computer that was itself a quantum system. Since then, the number of problems for which a quantum computer is known to enjoy an advantage over a classical computer has steadily increased, ranging now far beyond the task of simulating quantum physics. A quantum computation of any interest will need to create complicated superposition states, for otherwise it would not achieve anything that could not be simulated on a classical computer. These superposition states, however, are highly fragile, and this fragility is the main obstacle that the scientific community faces on the road towards a useful quantum computer. Quantum computing will only be possible if it can be performed in a fault-tolerant way. It is due to seminal work by Alexei Kitaev from 1997 that the modern theory of quantum fault-tolerance is closely related to the term topology. Topology, as a sub-field of mathematics, is concerned with the properties of space that are preserved under continuous deformations. Topological order, a purely quantum phenomenon, refers to states which cannot be distinguished or evolved into each other locally, yet are globally distinct. The information that distinguishes between these states is stored in non-local degrees of freedom. If it were possible to store quantum information in these non-local degrees of freedom, this would be hugely attractive from a practical perspective, as it would mean that the information stored this way is immune to many forms of local errors. Two-dimensional topologically ordered states support excitations known as anyons. These are exotic quasi-particles that defy the dichotomy between fermions and bosons that applies to quantum particles in three spatial dimensions. In a topological quantum computer, the non-locally stored quantum information is processed by braiding these anyons around each other. Such a computation would be insensitive to small perturbations of the path along which anyons are braided, but would only depend on its topological properties. An open problem is whether topological order can persist at finite temperature. Equivalently, one can ask whether it is possible to build a system in which quantum information can be stored in a stable manner for arbitrarily long times, without performing active error correction and despite constant influence of a thermal environment. Such a system would constitute a self-correcting quantum memory and would extend the concept of a hard disk drive to the quantum realm. Whether nature allows for such a system to be built is of tremendous interest from both a fundamental and a practical perspective. Two-dimensional topologically ordered systems – those hosting anyons – do not qualify as self-correcting quantum memories; any finite temperature corrupts them in a time that is independent of the size of the system. In the present thesis, we propose and study systems in which the thermal stability of a simple toy model of an anyonic system, Kitaev’s toric code, is enhanced in various ways. We consider coupling it to optical cavity modes, to bosonic particles, or to a ferromagnet. These auxiliary systems then induce long-ranged interactions between the anyons, which allow to increase the finite-temperature lifetime of the stored quantum information arbitrarily by increasing the size of the system. While a topological quantum computer is naturally immune to many forms of imperfections and perturbations, accidental creation of anyonic quasi-particles due to coupling to an external environment is a form of error that requires active correction. This problem has seen surprisingly little attention until recently and is still poorly understood. In this thesis, we develop algorithms that are able to perform this task and provide the first proofs of its in-principle feasibility. Furthermore, we develop a system with the rare property that it both supports anyons that can be used for topological quantum computing, and allows for error correction with well-established techniques. Historically, the first proposals for building a fault-tolerant quantum \ncomputer involved an array of qubits (quantum bits) and a set of elementary operations that can be performed on individual and pairs of qubits. Fault-tolerant qubit-based quantum computing has been inspired tremendously from the insights gained in the study of topological quantum information processing. The surface code, which combines a qubit-based architecture with topological methods, is now at the forefront of the quest towards a fault-tolerant, scalable quantum computer. In the surface code, a large number of measurements are performed on a continuous basis to get some information about what errors have occurred. This information then needs to be converted by a classical algorithm into a prescription for performing error correction. In this thesis, we develop such an algorithm that, at the time of its publication, was the best efficient algorithm known for the surface code. Error correction for qubit-based quantum computers is typically studied with simplistic error models in which the errors on each qubit are independent from each other. We study what kinds of spatial and temporal correlations between the errors arise when a surface code is coupled to a typical model of an environment, and how they affect its correctability.
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.