In this thesis we present two results relating to the intersection between quantum information theory and quantum many-body physics. The first pertains to quantum algorithms, where few computational problems are believed to exhibit exponential separation between quantum and classical performance. For those that are, natural generalizations remain elusive. One speedup that has especially resisted generalization is the use of quantum walks to traverse the welded tree graph, due to Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman. We show how to generalize this to a large class of hierarchical graphs in which the vertices are grouped into “supervertices” that are arranged according to a d-dimensional lattice. Supervertices can have different sizes, and edges between supervertices correspond to random connections between their constituent vertices. The traversal time of quantum walks on these graphs are related to (a) the existence of small subspaces within which the quantum walk evolves and (b) the localization properties of the quantum walk within these subspaces. We find examples of hierarchical graphs that yield provable speedups over classical algorithms ranging from superpolynomial to exponential, depending on the underlying dimension and the random graph model. We also discuss how to relax criterion (a) to the existence of a small and approximate subspace by using techniques from graph sparsification. The second result pertains to fault-tolerant quantum memories. Storing a qubit in a noisy environment is crucial for developing full-scale quantum computers. While constructions of fault-tolerant quantum memories exist, they often assume that quantum operations are not local and assisting classical computation operates instantaneously and noislessly. In particular, constructing a topological quantum memory below four dimensions with local quantum and classical operations that is fault-tolerant under both quantum and classical noise is an open problem. We construct a local quantum memory for the 2D toric code using ideas from the classical cellular automata of Tsirelson and Gács. Our memory preserves a logical state for exponential time in the presence of both classical and quantum noise below a constant noise rate. While our 2D quantum memory is built from operations that depend on space and time, we construct a fault-tolerant quantum memory in 3D using stacks of 2D toric codes that can be built with time-independent operations.
In this thesis we present two results relating to the intersection between quantum information theory and quantum many-body physics. The first pertains to quantum algorithms, where few computational problems are believed to exhibit exponential separation between quantum and classical performance. For those that are, natural generalizations remain elusive. One speedup that has especially resisted generalization is the use of quantum walks to traverse the welded tree graph, due to Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman. We show how to generalize this to a large class of hierarchical graphs in which the vertices are grouped into “supervertices” that are arranged according to a d-dimensional lattice. Supervertices can have different sizes, and edges between supervertices correspond to random connections between their constituent vertices. The traversal time of quantum walks on these graphs are related to (a) the existence of small subspaces within which the quantum walk evolves and (b) the localization properties of the quantum walk within these subspaces. We find examples of hierarchical graphs that yield provable speedups over classical algorithms ranging from superpolynomial to exponential, depending on the underlying dimension and the random graph model. We also discuss how to relax criterion (a) to the existence of a small and approximate subspace by using techniques from graph sparsification. The second result pertains to fault-tolerant quantum memories. Storing a qubit in a noisy environment is crucial for developing full-scale quantum computers. While constructions of fault-tolerant quantum memories exist, they often assume that quantum operations are not local and assisting classical computation operates instantaneously and noislessly. In particular, constructing a topological quantum memory below four dimensions with local quantum and classical operations that is fault-tolerant under both quantum and classical noise is an open problem. We construct a local quantum memory for the 2D toric code using ideas from the classical cellular automata of Tsirelson and Gács. Our memory preserves a logical state for exponential time in the presence of both classical and quantum noise below a constant noise rate. While our 2D quantum memory is built from operations that depend on space and time, we construct a fault-tolerant quantum memory in 3D using stacks of 2D toric codes that can be built with time-independent operations.
Quantum information science explores ways in which quantum physical laws can be harnessed to control the acquisition, transmission, protection, and processing of information. This field has seen explosive growth in the past several years from progress on both theoretical and experimental fronts. Essential to this endeavor are methods for controlling quantum information. In this thesis, I present three new approaches for controlling quantum information. First, I present a new protocol for continuously protecting unknown quantum states from noise. This protocol combines and expands ideas from the theories of quantum error correction and quantum feedback control. The result can outperform either approach by itself. I generalize this protocol to all known quantum stabilizer codes, and study its application to the three-qubit repetition code in detail via Monte Carlo simulations. Next, I present several new protocols for controlling quantum information that are fault-tolerant. These protocols require only local quantum processing due to the topological properties of the quantum error correcting codes upon which they are built. I show that each protocol's fault-dependence behavior exhibits an order-disorder phase transition when mapped onto an associated statistical-mechanical model. I review the critical error rates of these protocols found by numerical study of the associated models, and I present new analytic bounds for them using a self-avoiding random walk argument. Moreover, I discuss fault-tolerant procedures for encoding, error-correction, computing, and decoding quantum information using these protocols, and calculate the accuracy threshold of fault-tolerant quantum memory for protocols using them. I end by presenting a new class of quantum algorithms that solve combinatorial optimization problems solely by measurement. I compute the running times of these algorithms by establishing an explicit dynamical model for the measurement process. This model, the digitized version of von Neumann's measurement model, is recognized as Kitaev's phase estimation algorithm. I show that the running times of these algorithms are closely related to the running times of adiabatic quantum algorithms. Finally, I present a two-measurement algorithm that achieves a quadratic speedup for Grover's unstructured search problem.
A quantum computation can be described by the evolution of a collection of quantum bits, or qubits, according to the laws of quantum mechanics, from an initial state encoding the input of a problem, to its solution represented by the final state. A machine capable of performing this task, a quantum computer, must be robust against errors caused by the inherent imperfections in the fabrication and control of such complex systems. This thesis examines the theory of fault‑tolerant quantum computation, tailored to the physical constraints of today’s leading platforms, most notably superconducting circuits and neutral‑atom arrays.A fault-tolerant quantum computation requires to correct errors in real time, at the cost of a dedicated architectural layer whose integration may introduce additional noise. A possible simplification uses a quantum memory model where information is encoded in a pair of configurations of a multi-qubit system, stabilized by the uniform application of a simple local rule fitting within the theory of cellular automata. We propose a short-term solution, the shearing-rule which protects a one-dimensional repetition code against errors with good performance but lacks a threshold. This shortcoming is addressed by adding small local classical memories, used to define the signal-rules decoders, where error correction relies on exchanging binary signals. Combined with biased-noise qubits, such as cat qubits, these local decoders define a fully local one-dimensional quantum memory.The final part of the manuscript addresses the advantage of quantum machines over their classical counterparts. We emphasize that any such demonstration must account for the presence of noise to be meaningful — for example, while exact sampling from the output distribution of circuits drawn from certain families is believed to be hard for classical computers, the task may become tractable if one allows for an approximate solution that reflects the presence of noise. In this context, we propose a constant-depth quantum circuit that solves a sampling problem in a fault-tolerant manner. Because our approach is particularly well-suited to the atom rearrangement capabilities of neutral-atom array platforms, we hope it will contribute to a future experimental demonstration of a fault-tolerant quantum advantage.
This thesis is devoted to the study of coherent storage of quantum information as well as its potential applications.Quantum memories are crucial to harnessing the potential of quantum physics for information processing tasks.They are required for almost all quantum computation proposals.However, despite the large arsenal of theoretical techniques and proposals dedicated to their implementation, the realization of long-lived quantum memories remains an elusive task.Encoding information in quantum states associated to many-body topological phases of matter and protecting them by means of a static Hamiltonian is one of the leading proposals to achieve quantum memories.While many genuine and well publicized virtues have been demonstrated for this approach, equally real limitations were widely disregarded.In the first two projects of this thesis, we study limitations of passive Hamiltonian protection of quantum information under two different noise models.Chapter 2 deals with arbitrary passive Hamiltonian protection for a many body system under the effect of local depolarizing noise.It is shown that for both constant and time dependent Hamiltonians, the optimal enhancement over the natural single-particle memory time is logarithmic in the number of particles composing the system.The main argument involves a monotonic increase of entropy against which a Hamiltonian can provide little protection.Chapter 3 considers the recoverability of quantum information when it is encoded in a many-body state and evolved under a Hamiltonian composed of known geometrically local interactions and a weak yet unknown Hamiltonian perturbation.We obtain some generic criteria which must be fulfilled by the encoding of information.For specific proposals of protecting Hamiltonian and encodings such as Kitaev's toric code and a subsystem code proposed by Bacon, we additionally provide example perturbations capable of destroying the memory which imply upper bounds for the provable memory times.vi
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.
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 thesis is concerned with fault-tolerant quantum information processing using quantum error-correcting codes. It contains two major pieces of work. The first is a study of coherent noise in the context of stabilizer error-correcting codes. The second is a proposed scheme for a universal set of fault-tolerant logical gates in a particular code family built out of the 3D toric code. Chapter 1 provides an introduction to quantum computation and fault tolerance. Many basic concepts in error-correcting codes are defined. Special attention is paid to the set of code properties that are most likely to determine how easily a given fault-tolerant scheme might be implemented on a physical device. These include the fault-tolerant noise threshold and the overhead. In Chapters 2 and 3 we study the effectiveness of quantum error correction against coherent noise. Coherent errors (for example, unitary noise) can interfere constructively, so that in some cases the average infidelity of a quantum circuit subjected to coherent errors may increase quadratically with the circuit size; in contrast, when errors are incoherent (for example, depolarizing noise), the average infidelity increases at worst linearly with circuit size. We consider the performance of quantum stabilizer codes against a noise model in which a unitary rotation is applied to each qubit, where the axes and angles of rotation are nearly the same for all qubits. In Chapter 2 we introduce coherent noise and incoherent noise and a number of methods that are useful for the study of coherent noise. We study the repetition code as a basic example, and we also study a correlated noise model. In Chapter 3 we show that for the toric code subject to such independent coherent noise, and for minimal-weight decoding, the logical channel after error correction becomes increasingly incoherent as the length of the code increases, provided the noise strength decays inversely with the code distance. A similar conclusion holds for weakly correlated coherent noise. Our methods can also be used for analyzing the performance of other codes and fault-tolerant protocols against coherent noise. However, our result does not show that the coherence of the logical channel is suppressed in the more physically relevant case where the noise strength is held constant as the code block grows, and we recount the difficulties that prevented us from extending the result to that case. Nevertheless our work supports the idea that fault-tolerant quantum computing schemes will work effectively against coherent noise, providing encouraging news for quantum hardware builders who worry about the damaging effects of control errors and coherent interactions with the environment. Chapter 4 is connected to another aspect of fault tolerance, fault-tolerant logical gates. The toric code is a promising candidate for fault-tolerant quantum computation because of its high threshold and low-weight stabilizers. A universal gate set in the toric code generally requires magic state distillation, which can incur a significant qubit overhead. In this work we construct an error-correcting code in three dimensions based on the toric code that features a fault-tolerant T gate with no magic state distillation required. We further describe a subsystem version of our code which supports a universal set of fault-tolerant gates. This code can be converted into the stabilizer version using gauge-fixing. We also argue that our code can be converted to a (2+1)-D protocol, where a 2D lattice undergoes a measurement-based protocol over time. In this way, a fault-tolerant logical T gate can be realized in a 2D toric code structure.