Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2106.00765 · Quantum

Connectivity constrains quantum codes

Nouédyn Baspin, Anirudh Krishna

Published May 13, 2022• 33 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2022-05-13-711

Related papers

Low-density parity-check representation of fault-tolerant quantum circuits

Ying Li

In fault-tolerant quantum computing, quantum algorithms are implemented through quantum circuits capable of error correction. These circuits are typically constructed based on specific quantum error correction codes, with consideration given to the characteristics of the underlying physical platforms. Optimizing these circuits within the constraints of today's quantum computing technologies, particularly in terms of error rates, qubit counts, and network topologies, holds substantial implications for the feasibility of quantum applications in the near future. This paper presents a toolkit for designing and analyzing fault-tolerant quantum circuits. We introduce a framework for representing stabilizer circuits using classical low-density parity-check (LDPC) codes. Each codeword in the representation corresponds to a quantum-mechanical equation regarding the circuit, formalizing the correlations utilized in parity checks and delineating logical operations within the circuit. Consequently, the LDPC code provides a means of quantifying fault tolerance and verifying logical operations. We outline the procedure for generating LDPC codes from circuits using the Tanner graph notation, alongside proposing graph-theory tools for constructing fault-tolerant quantum circuits from classical LDPC codes. These findings offer a systematic approach to applying classical error correction techniques in optimizing existing fault-tolerant protocols and developing new ones. As an example, we develop a resource-efficient scheme for universal fault-tolerant quantum computing on hypergraph product codes based on the LDPC representation.

arXiv:2403.10268•Physical Review Research•Jan 30, 2025•2 citations

Improved rate-distance trade-offs for quantum codes with restricted connectivity

Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna +1 more

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.

arXiv:2307.03283•Quantum Science and Technology•Oct 4, 2024•7 citations

Quantum LDPC codes with design rate 1/5 and good performance below 1000 physical qubits

Yifan Hong

Constant-rate quantum low-density parity-check (LDPC) codes promise fault-tolerant quantum computation with constant spatial overhead in the asymptotic limit. Nonetheless, discovering finite-length code instances with good practical performance remains challenging. We introduce a new family of quantum LDPC codes with design rate $1/5$ and check weight $9$ that approaches the teraquop memory regime per qubit-round with several hundred physical qubits, under idling-free circuit-level noise of strength $0.1\%$ and GPU-accelerated Relay-belief-propagation (Relay-BP) decoding with average latencies around 1-2 ms, a regime relevant to trapped-ion and neutral-atom processors. The construction involves the balanced product of classical LDPC codes with design rate $1/2$ that share non-abelian $\mathbb{Z}_\ell \rtimes \mathbb{Z}_m$ group symmetries, which may be of independent interest for classical error correction. We build syndrome extraction circuits tailored to reconfigurable atom arrays using a simple greedy scheduler, with single-round rearrangement times around 30-60 ms using present hardware specifications, and substantial room for future improvements. We also construct logical Pauli bases that are equivariant with respect to the group symmetry, which can significantly compress the design space for code surgery. Together, these results further advance the practicality of constant-rate quantum LDPC codes for near-term, fault-tolerant quantum computers.

quant-pharXiv:2607.27644•Jul 31, 2026•0 citations

Decoding Quasi-Cyclic Quantum LDPC Codes

Louis Golowich, Venkatesan Guruswami

Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.

arXiv:2411.04464•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•1 citation

Good quantum LDPC codes with linear time decoder from lossless expanders

Ting-Chun Lin, Min-Hsiu Hsieh

Quantum low-density parity-check (qLDPC) codes are quantum stabilizer codes where each stabilizer acts on a constant number of qubits and each qubit is acted on by a constant number of stabilizers. We study qLDPC codes constructed from balanced products and lossless expanders. We found that assuming the existence of 2-sided lossless expander graphs with free group action, the resulting qLDPC codes have constant rate, linear distance, and linear time decoders.

arXiv:2203.03581•Mar 7, 2022•13 citations

Hyperbolic color codes with constant rate and polynomial distance

Shun Hasegawa, Hayata Yamasaki

Recent advances in quantum hardware relax the strict geometric-locality constraints traditionally imposed on quantum error-correcting codes, motivating interest in high-rate quantum low-density parity-check (qLDPC) codes. At the same time, color codes provide a particularly rich setting for fault-tolerant quantum computation, underlying protocols such as single-shot error correction and self-correcting quantum computation. Hyperbolic color codes provide a class of high-rate qLDPC codes that also retain the structural features of color codes relevant to fault-tolerant quantum computation. However, previous constructions of hyperbolic color codes have achieved at most logarithmic code distance. In this work, we construct hyperbolic color codes with both constant rate and polynomial distance by building on arithmetic hyperbolic manifolds that support polynomial-distance hyperbolic toric codes. Our construction applies in arbitrary dimension \(D\geq 4\). In even dimensions, the resulting type-\(D/2\) color codes have constant encoding rate and polynomial distance, while in other cases the number of logical qubits and the code distance both exhibit polynomial scaling. We further derive explicit exponents for polynomial lower bounds as functions of the dimension and code type. These results establish a family of hyperbolic color codes simultaneously achieving constant rate and polynomial distance and providing a testbed to explore fault-tolerant quantum computation protocols that combine high-rate quantum codes with the structural advantages of color codes.

quant-pharXiv:2609.16125•Sep 16, 2026•0 citations
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.
In fault-tolerant quantum computing, quantum algorithms are implemented through quantum circuits capable of error correction. These circuits are typically constructed based on specific quantum error correction codes, with consideration given to the characteristics of the underlying physical platforms. Optimizing these circuits within the constraints of today's quantum computing technologies, particularly in terms of error rates, qubit counts, and network topologies, holds substantial implications for the feasibility of quantum applications in the near future. This paper presents a toolkit for designing and analyzing fault-tolerant quantum circuits. We introduce a framework for representing stabilizer circuits using classical low-density parity-check (LDPC) codes. Each codeword in the representation corresponds to a quantum-mechanical equation regarding the circuit, formalizing the correlations utilized in parity checks and delineating logical operations within the circuit. Consequently, the LDPC code provides a means of quantifying fault tolerance and verifying logical operations. We outline the procedure for generating LDPC codes from circuits using the Tanner graph notation, alongside proposing graph-theory tools for constructing fault-tolerant quantum circuits from classical LDPC codes. These findings offer a systematic approach to applying classical error correction techniques in optimizing existing fault-tolerant protocols and developing new ones. As an example, we develop a resource-efficient scheme for universal fault-tolerant quantum computing on hypergraph product codes based on the LDPC representation.
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.
Constant-rate quantum low-density parity-check (LDPC) codes promise fault-tolerant quantum computation with constant spatial overhead in the asymptotic limit. Nonetheless, discovering finite-length code instances with good practical performance remains challenging. We introduce a new family of quantum LDPC codes with design rate 1/51/51/5 and check weight 999 that approaches the teraquop memory regime per qubit-round with several hundred physical qubits, under idling-free circuit-level noise of strength 0.1%0.1\%0.1% and GPU-accelerated Relay-belief-propagation (Relay-BP) decoding with average latencies around 1-2 ms, a regime relevant to trapped-ion and neutral-atom processors. The construction involves the balanced product of classical LDPC codes with design rate 1/21/21/2 that share non-abelian Zℓ⋊Zm\mathbb{Z}_\ell \rtimes \mathbb{Z}_mZℓ​⋊Zm​ group symmetries, which may be of independent interest for classical error correction. We build syndrome extraction circuits tailored to reconfigurable atom arrays using a simple greedy scheduler, with single-round rearrangement times around 30-60 ms using present hardware specifications, and substantial room for future improvements. We also construct logical Pauli bases that are equivariant with respect to the group symmetry, which can significantly compress the design space for code surgery. Together, these results further advance the practicality of constant-rate quantum LDPC codes for near-term, fault-tolerant quantum computers.
Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.
Recent advances in quantum hardware relax the strict geometric-locality constraints traditionally imposed on quantum error-correcting codes, motivating interest in high-rate quantum low-density parity-check (qLDPC) codes. At the same time, color codes provide a particularly rich setting for fault-tolerant quantum computation, underlying protocols such as single-shot error correction and self-correcting quantum computation. Hyperbolic color codes provide a class of high-rate qLDPC codes that also retain the structural features of color codes relevant to fault-tolerant quantum computation. However, previous constructions of hyperbolic color codes have achieved at most logarithmic code distance. In this work, we construct hyperbolic color codes with both constant rate and polynomial distance by building on arithmetic hyperbolic manifolds that support polynomial-distance hyperbolic toric codes. Our construction applies in arbitrary dimension D≥4D\geq 4D≥4. In even dimensions, the resulting type-D/2D/2D/2 color codes have constant encoding rate and polynomial distance, while in other cases the number of logical qubits and the code distance both exhibit polynomial scaling. We further derive explicit exponents for polynomial lower bounds as functions of the dimension and code type. These results establish a family of hyperbolic color codes simultaneously achieving constant rate and polynomial distance and providing a testbed to explore fault-tolerant quantum computation protocols that combine high-rate quantum codes with the structural advantages of color codes.