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.
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.
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.
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 low-density parity-check (LDPC) codes are a promising avenue to reduce the cost of constructing scalable quantum circuits. However, it is unclear how to implement these codes in practice. Seminal results of Bravyi et al. [Phys. Rev. Lett. 104, 050503 (2010)] have shown that quantum LDPC codes implemented through local interactions obey restrictions on their dimension k and distance d. Here we address the complementary question of how many long-range interactions are required to implement a quantum LDPC code with parameters k and d. In particular, in 2D we show that a quantum LDPC code with distance $d\ensuremath{\propto}{n}^{1/2+ϵ}$ requires $\mathrm{\ensuremath{\Omega}}({n}^{1/2+ϵ})$ interactions of length $\stackrel{\texttildelow{}}{\mathrm{\ensuremath{\Omega}}}({n}^{ϵ})$. Further, a code satisfying $k\ensuremath{\propto}n$ with distance $d\ensuremath{\propto}{n}^{\ensuremath{\alpha}}$ requires $\stackrel{\texttildelow{}}{\mathrm{\ensuremath{\Omega}}}(n)$ interactions of length $\stackrel{\texttildelow{}}{\mathrm{\ensuremath{\Omega}}}({n}^{\ensuremath{\alpha}/2})$. As an application of these results, we consider a model called a stacked architecture, which has previously been considered as a potential way to implement quantum LDPC codes. In this model, although most interactions are local, a few of them are allowed to be very long. We prove that limited long-range connectivity implies quantitative bounds on the distance and code dimension.
Quantum Low-Density Parity-Check (LDPC) codes provide a promising solution to protect quantum information from errors and are therefore considered an important step in the realisation of a fullscale fault-tolerant quantum computer. In this thesis, we study quantum LDPC codes under three different approaches, providing insights into renormalisation decoding for Kitaev’s toric code, establishing bounds on the minimum distance of geometrically-local codes, and constructing small instances of quantum Tanner codes. Kitaev’s toric code is a prominent quantum LDPC code that is currently the most widely pursued for experimental implementation. We focus on the probabilistic renormalisation decoders introduced by Duclos- Cianci and Poulin, a family of decoders that exhibit one of the best trade-offs between accuracy and efficiency. We study how they handle adversarial errors by introducing a deterministic renormalisation decoder that does not use a priori probabilities of the error model. We find that this renormalisation decoder allows for fractal-like uncorrectable error patterns, and we obtain a lower bound on the weight of such errors. Due to physical constraints, a lot of attention has gone into quantum LDPC codes whose stabilisers act only on a limited number of nearby qubits. We extend the well-known Bravyi-Terhal bound to quantum codes defined by local constraints on a lattice quotient, providing a crucial insight into the limitations of geometrically-local stabiliser codes. As an application, we provide upper bounds on the minimum distance of Abelian Two-Block Group Algebra codes, a family of quantum LDPC codes for which the minimum distance is currently unknown. In recent years, asymptotically good quantum LDPC codes were constructed, but provable results on their minimum distances only apply to impractically long codes. Following the effort in the design of near-term implementable codes, we construct short instances of quantum Tanner codes using square complexes obtained from lifted products of regular graphs. Several explicit instances of these codes exhibit minimum distances surpassing the square root of the code length.