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 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∝n1/2+ϵ requires \ensuremathΩ(n1/2+ϵ) interactions of length \ensuremathΩ\texttildelow(nϵ). Further, a code satisfying k\ensuremath∝n with distance d\ensuremath∝n\ensuremathα requires \ensuremathΩ\texttildelow(n) interactions of length \ensuremathΩ\texttildelow(n\ensuremathα/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.
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 low-density parity-check (QLDPC) codes with good parameters are promising candidates for low-overhead fault-tolerant quantum computing, but their non-local stabilizers require long-range connectivity and frequent qubit movement, introducing practical challenges. Prior work has studied the networked implementation of topological codes, where each node only holds one or a few qubits of the entire code, and demonstrated competitive performance under practical constraints such as the quality of network-provided entanglement. However, since these codes are already geometrically local, such a networked setting might not be essential. In this work, we propose and study the networked implementation of better QLDPC codes, specifically bivariate bicycle codes due to their similarity to surface codes and the controlled amount of long-range connections in their stabilizers. We begin by recreating networked surface codes in Stim, with one code qubit per node, and provide additional insights into their circuit-level noise performance. We then extend this approach to bipartitions of bivariate bicycle codes, using balanced min-cut partitioning on their combined X-Z Tanner graph to identify optimal qubit splits. For stabilizers spanning nodes, we implement teleported CNOTs and vary the Bell pair fidelity enabling these gates. Through circuit-level noise simulations with BP-OSD decoding, we provide the first insights into networked realizations of these codes and compare their performance with monolithic implementations. We conclude by outlining advantages, limitations, and future directions.
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.
It is widely accepted that quantum error correction is essential for realizing large-scale fault-tolerant quantum computing. Recent experiments have demonstrated error correction codes operating below threshold, primarily using local planar codes such as the surface code and color code. In parallel, theoretical advances in quantum low-density parity-check (LDPC) codes promise significantly lower overheads, albeit at the cost of requiring non-local parity checks. While these results are encouraging, implementing such codes remains challenging for near-term experiments, creating obstacles to holistic benchmarking of hardware architectures capable of supporting long-range couplers. In this work, we present a simple construction recipe for small quantum LDPC codes based on recent developments in the field. Our codes are approximately twice as efficient as comparable surface codes, yet require only weight-four parity checks, which simplifies experimental realization compared to other quantum LDPC codes. We provide concrete proposals for implementations with superconducting qubits in flip-chip architectures and with semiconductor spin qubits using shuttling-based approaches.
Quantum low-density parity-check (qLDPC) codes are promising candidates for realizing large-scale fault-tolerant quantum computing. Although many codes with favorable theoretical parameters have been developed, their practical adoption must take hardware implementability into account. For mainstream quantum platforms such as superconductors and neutral atoms, the connectivity, the length of non-local couplings, and the complexity of wiring or atom rearrangement are key factors that dictate the difficulty of hardware realization. Here, we propose a new family of qLDPC codes, termed routing codes. Within this family, we find explicit instances whose encoding rates are competitive to those of bivariate bicycle (BB) codes, while systematically reducing qubit connectivity, shortening the length of non-local couplings, and, crucially, making all non-local couplings mutually parallel. This parallelism translates into quantifiable benefits, substantially reducing wiring crossings in superconducting multi-layer architectures and simplifying the scheduling of atom movement in neutral-atom arrays. The weight-7 routing codes maintain a high threshold of 0.7\% and reduce the physical qubit overhead by approximately a factor of 8, compared to surface codes achieving a same logical error rate. Further increasing the weight to 11 yields a [[200, 24, 14]] and [[200, 16, 17]] codes with an encoding rate over 23 times that of the surface code, at the cost of a higher logical error rate. These results establish routing codes as a hardware-centric qLDPC family that bridges the gap between theoretical optimality and near-term physical feasibility.