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.
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.
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.
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.
Quantum low-density parity-check (LDPC) codes are an important class of quantum error correcting codes. In such codes, each qubit only affects a constant number of syndrome bits, and each syndrome bit only relies on some constant number of qubits. Constructing quantum LDPC codes is challenging. It is an open problem to understand if there exist good quantum LDPC codes, i.e. with constant rate and relative distance. Furthermore, techniques to perform fault-tolerant gates are poorly understood. We present a unified way to address these problems. Our main results are a) a bound on the distance, b) a bound on the code dimension and c) limitations on certain fault-tolerant gates that can be applied to quantum LDPC codes. All three of these bounds are cast as a function of the graph separator of the connectivity graph representation of the quantum code. We find that unless the connectivity graph contains an expander, the code is severely limited. This implies a necessary, but not sufficient, condition to construct good codes. This is the first bound that studies the limitations of quantum LDPC codes that does not rely on locality. As an application, we present novel bounds on quantum LDPC codes associated with local graphs in D -dimensional hyperbolic space.
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 (qLDPC) codes can be implemented by measuring only low-weight checks, making them compatible with noisy quantum hardware and central to the quest to build noise-resilient quantum computers. A fundamental open question is how constraints on check weight limit the achievable parameters of qLDPC codes. Here, we study stabilizer and subsystem codes with constrained check weight, combining analytical arguments with numerical optimization to establish strong upper bounds on their parameters. We show that stabilizer codes with checks of weight at most three cannot have nontrivial distance. We also prove tight tradeoffs between rate and distance for broad families of CSS stabilizer and subsystem codes with checks of weight at most four and two, respectively. Notably, our bounds are applicable to general qLDPC codes, as they rely only on check-weight constraints without assuming geometric locality or special graph connectivity. In the finite-size regime, we derive numerical upper bounds using linear programming techniques and identify explicit code constructions that approach these limits, delineating the landscape of practically relevant qLDPC codes with tens or hundreds of physical qubits.
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.