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.
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.
This paper proves optimal tradeoffs between the locality and parameters of quantum error-correcting codes. Quantum codes give a promising avenue towards quantum fault tolerance, but the practical constraint of locality limits their quality. The seminal Bravyi-Poulin-Terhal (BPT) bound says that a [[n,k,d]] quantum stabilizer code with 2D-locality must satisfy kd2≤O(n). We answer the natural question: for better code parameters, how much "non-locality" is needed? In particular, (i) how long must the long-range interactions be, and (ii) how many long-range interactions must there be? We give a complete answer to both questions for all n,k,d: above the BPT bound, any 2D-embedding must have at least Ω(#∗) interactions of length Ω(ℓ∗), where #∗=max(k,d) and ℓ∗=max(nd,(nkd2)1/4). Conversely, we exhibit quantum codes that show, in strong ways, that our interaction length ℓ∗ and interaction count #∗ are asymptotically optimal for all n,k,d. Our results generalize or improve all prior works on this question, including the BPT bound and the results of Baspin and Krishna. One takeaway of our work is that, for any desired distance d and dimension k, the number of long-range interactions is asymptotically minimized by a good qLDPC code of length Θ(max(k,d)). Following Baspin and Krishna, we also apply our results to the codes implemented in the stacked architecture and obtain better bounds. In particular, we rule out any implementation of hypergraph product codes in the stacked architecture.
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.
Abstract For quantum error-correcting codes to be realizable, it is important that the qubits subject to the code constraints exhibit some form of limited connectivity. The works of Bravyi and Terhal (2009 New J. Phys. 11 043029) (BT) and Bravyi et al (2010 Phys. Rev. Lett. 104 050503) (BPT) established that geometric locality constrains code properties—for instance [ [ n , k , d ] ] quantum codes defined by local checks on the D-dimensional lattice must obey k d 2 / ( D − 1 ) ⩽ O ( n ) . Baspin and Krishna (2022 Quantum 6 711) studied the more general question of how the connectivity graph associated with a quantum code constrains the code parameters. These trade-offs apply to a richer class of codes compared to the BPT and BT bounds, which only capture geometrically-local codes. We extend and improve this work, establishing a tighter dimension-distance trade-off as a function of the size of separators in the connectivity graph. We also obtain a distance bound that covers all stabilizer codes with a particular separation profile, rather than only LDPC codes.
The existence of quantum locally generated codes is a long standing open problem in quantum information theory. In this thesis, we consider a bound concerning this conjecture as well as a few constructions with codes that are `barely non-local'. We establish a complementary result to Bravyi and Terhal, and show quantum codes which are ``strongly'' not embeddable into finite dimensional lattices must also have poor distance. Along the way we derive some results concerning "pseudorandom" classical codes.\nGiven that quantum codes seem to be difficult to construct, it seems useful to examine "bad" quantum codes for applications in information and communication. Indeed, most of the work in quantum error correction by researchers today is in this direction. We construct a "nearly local" quantum erasure code which can achieve the capacity of the quantum erasure channel. This code has very poor (adversarial) distance, but still manages to correct random erasure errors with high probability. The codes use random Erdos-Renyi graphs to construct quantum states which are nearly local, but also highly entangled across fixed cuts with high probability. We derive some new results concerning classical codes with log-sparse parity check matrices which may be of independent interest.\nInspired by this construction, we are able to construct new approximate unitary 2-designs or "scramblers". The study of scrambling is the study of the mixing properties of different distributions of random unitaries. There is an inherent duality between the study of scrambling and the study of error correction: A good quantum code will make a good scrambler and vice versa. We study the scrambling properties of our random Erdos-Renyi graph state encoding circuits. We are able to show that these circuits, when supplemented by some local "Expander Graph" quantum circuits, form approximate unitary 2-designs. This construction, strictly speaking, does not achieve more efficient parameters than existing approximate 2-designs, but might have implementation advantages over other designs and points to a conjecture which could yield approximate unitary designs with time independent qubit-to-qubit coupling. This would be an extremely interesting construction in the context of experimental randomized benchmarking.
Quantum error-correcting codes are a cornerstone of quantum computing, with broad and profound connections to physics and mathematics. In this work, we introduce the notion of intrinsic locality dimension of stabilizer codes, which is independent of the underlying geometry of quantum codes and naturally extends to non-integer values. Drawing on mathematical tools from fractal geometry and geometric measure theory, the intrinsic locality dimension accommodates flexible architectures and provides a quantitative measure of code connectivity, encompassing both topological codes and algebraic constructions such as bivariate-bicycle-type codes. We show how the intrinsic dimension serves as a fundamental organizing parameter that unifies code properties. In particular, we prove general limitations on code parameters and compatible fault-tolerant logical gates induced by the intrinsic dimension, generalizing the Bravyi--Poulin--Terhal and Bravyi--König bounds for regular topological codes, respectively. Furthermore, we consider implications on thermal properties: toward fully characterizing the geometry requirement for self-correcting quantum memories (SCQMs), we present a conditional no-go result for SCQMs in dimension 3−ε and take stock of existing results on low-dimensional SCQMs. Our theory provides a unifying mathematical framework for understanding the fundamental capabilities and geometric implementations of quantum error correction and fault tolerance.
This thesis provides bounds on the performance of quantum error correcting codes when used for quantum communication and quantum key distribution. The first two chapters provide a bare-bones introduction to classical and quantum error correcting codes, respectively. The next four chapters present achievable rates for quantum codes in various scenarios. The final chapter is dedicated to an upper bound on the quantum channel capacity. Chapter 3 studies coding for adversarial noise using quantum list codes, showing there exist quantum codes with high rates and short lists. These can be used, together with a very short secret key, to communicate with high fidelity at noise levels for which perfect fidelity is impossible. Chapter 4 explores the performance of a family of degenerate codes when used to communicate over Pauli channels, showing they can be used to communicate over almost any Pauli channel at rates that are impossible for a nondegenerate code and that exceed those of previously known degenerate codes. By studying the scaling of the optimal block length as a function of the channel's parameters, we develop a heuristic for designing even better codes. Chapter 5 describes an equivalence between a family of noisy preprocessing protocols for quantum key distribution and entanglement distillation protocols whose target state belongs to a class of private states called "twisted states." In Chapter 6, the codes of Chapter 4 are combined with the protocols of Chapter 5 to provide higher key rates for one-way quantum key distribution than were previously thought possible. Finally, Chapter 7 presents a new upper bound on the quantum channel capacity that is both additive and convex, and which can be interpreted as the capacity of the channel for communication given access to side channels from a class of zero capacity "cloning" channels. This "clone assisted capacity" is equal to the unassisted capacity for channels that are degradable, which we use to find new upper bounds on the capacity of a depolarizing channel.