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:2608.18536

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun

quant-phcond-mat.str-elcs.CCcs.ITSubmitted Aug 19, 2026• Announced Aug 20, 2026• 1 citation
arXivHTMLPDF

Abstract

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

Comments
33 pages, 2 figures, 1 table

Related papers

Approximate Quantum Error Correction with 1D Log-Depth Circuits

Guoding Liu, Zhenyu Du, Zi-Wen Liu +1 more

Efficient and high-performance quantum error correction is essential for achieving fault-tolerant quantum computing. Low-depth random circuits offer a promising approach to identifying effective and practical encoding strategies. In this work, we rigorously prove through information-theoretic analysis that one-dimensional logarithmic-depth random Clifford encoding circuits can achieve high quantum error correction performance. We demonstrate that these random codes typically exhibit good approximate quantum error correction capability by proving that their encoding rate achieves the hashing bound for Pauli noise and the channel capacity for erasure errors. We show that the error correction inaccuracy decays once a threshold of logarithmic depth is exceeded, resulting in negligible recovery errors. This threshold is shown to be lower than that of the simple separate block encoding, and the decay rate is higher. We further establish that these codes are optimal by proving that logarithmic depth is necessary to maintain a constant encoding rate and high error correction performance. To prove our results, we propose decoupling theorems tailored for one-dimensional low-depth circuits. These results also imply strong decoupling and rapid thermalization properties in low-depth random circuits and have potential applications in quantum information science and physics.

arXiv:2503.17759•PRX Quantum•Jan 6, 2026•8 citations

Improved Transversal Non-Clifford Gates from Cup Products

Louis Golowich, Itzhak Tamo, Guanyu Zhu

It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford $C^{r-1}Z$ gate, for every constant $r\geq 3$. In particular, we obtain length-$n$ quantum LDPC codes (with constant-weight stabilizers) of polynomial distance $d\geq n^{(1-ε)/r}$ supporting transversal $C^{r-1}Z$ gates on a close-to-linear number $k\geq n^{1-ε}$ of disjoint tuples of logical qubits, for arbitrarily small $ε>0$. Our construction is the first with constant-weight stabilizers that obtains $dk\gg n$, and as a consequence achieves arbitrarily small magic state overhead exponent $γ=\log(n/k)/\log(d)>0$. Comparable prior constructions instead required at least polylogarithmic stabilizer weight. We also show how to obtain linearly many $k=Ω(n)$ logical $C^{r-1}Z$ gates, though with stabilizer weight and physical circuit depth $n^ε$. We show that our transversal gates also support addressing (i.e. targeting) of specific logical qubits. To obtain our codes, we develop a general transformation based on cup products that maps classical codes satisfying a multiplication property to quantum codes with transversal $C^{r-1}Z$. We apply this transformation to a new family of classical Tanner codes that we construct from punctured tensor products of algebraic codes.

quant-pharXiv:2609.27801•Aug 19, 2026•2 citations

Transversal Clifford and T -Gate Codes of Short Length and High Distance

Shubham P. Jain, Victor V. Albert

The non-local interactions in several quantum device architectures allow for the realization of more compact quantum encodings while retaining the same degree of protection against noise. Anticipating that short to medium-length codes will soon be realizable, it is important to construct stabilizer codes that, for a given code distance, admit fault-tolerant implementations of logical gates with the fewest number of physical qubits. To this aim, we construct three kinds of codes encoding a single logical qubit for distances up to 31. First, we construct the smallest known doubly even codes, all of which admit a transversal implementation of the Clifford group. Applying a doubling procedure arXiv:1509.03239 to such codes yields the smallest known weak triply even codes for the same distances and number of encoded qubits. This second family of codes admit a transversal implementation of the logical T-gate. Relaxing the triply even property, we obtain our third family of triorthogonal codes with an even lower overhead at the cost of requiring additional Clifford gates to achieve the same logical operation. To our knowledge, these are the smallest known triorthogonal codes for their respective distances. While not qLDPC, the stabilizer generator weights of the code families with transversal T-gates scale roughly as the square root of their lengths.

arXiv:2408.12752•IEEE Journal on Selected Areas in Information Theory•Jan 1, 2025•19 citations

Constant-rate quantum codes with low-weight stabilizers and full logical Clifford actions via transversal and fold-transversal gates

Takaya Matsuura, Yohji Chin, Shohei Kiryu +1 more

Low-space-overhead fault-tolerant quantum computation requires not only high-rate quantum error-correcting codes but also space-efficient implementations of logical operations. Transversal and fold-transversal gates are promising since they limit error propagation and require no additional qubits. However, the logical operations they enable are typically restricted, and a central challenge is to construct codes that combine a complete set of logical Clifford gates with favorable code parameters. In this work, we introduce a family of quantum codes with an asymptotically constant encoding rate and sublogarithmically growing stabilizer weight, while supporting the entire logical Clifford group using only transversal and fold-transversal gates. Our construction is based on classical codes whose code spaces are absolutely irreducible Steinberg modules of their Tanner-graph automorphism groups. Taking hypergraph products of these classical codes yields quantum codes for which all logical Clifford operations can be synthesized from a fixed set of transversal and fold-transversal gates. Moreover, the slow growth of the stabilizer weight enables a high error-correcting performance in small instances. These results provide a path toward fault-tolerant quantum computation with low space overhead using transversal and fold-transversal gates.

quant-pharXiv:2609.37699•Sep 30, 2026•1 citation

Synthesis and Optimization of Encoding Circuits for Fault-Tolerant Quantum Computation

Tom Peham, Matthew Steinberg, Robert Wille +1 more

Preparing arbitrary logical states is a central primitive for universal fault-tolerant quantum computation and the cost of encoded-state preparation contributes directly to the overall resource overhead. This makes the synthesis of efficient general-state encoding circuits an important problem, particularly with respect to two-qubit gate count and circuit depth. Yet the synthesis of such encoders has been studied less extensively than general Clifford circuit synthesis or the preparation of specific logical Pauli-eigenstates. In this work, we develop methods for synthesizing efficient encoders for arbitrary stabilizer codes. We formulate encoder synthesis as a search over stabilizer tableaus and introduce greedy and rollout-based algorithms that exploit the freedom among stabilizer-equivalent realizations of the same encoding isometry. For code families with a modular structure, such as generalized concatenated and holographic codes, we show how large encoders can be assembled from optimized local constituent encoders, and we use SMT-based exact synthesis to obtain optimal local circuits for small instances. We further evaluate the proposed methods on a broad set of stabilizer codes, including holographic and quantum low-density parity-check (qLDPC) codes, and compare them against recent encoder-synthesis methods and existing constructions from the literature, obtaining improvements of up to 43% in two-qubit gate count and up to 70% in depth. Our results support the optimization of encoded-state preparation in several fault-tolerant quantum-computing schemes, and all methods are openly available as part of the Munich Quantum Toolkit.

quant-pharXiv:2605.15266•May 18, 2026•1 citation

Short random circuits define good quantum error correcting codes

Winton Brown, Omar Fawzi

We study the encoding complexity for quantum error correcting codes with large rate and distance. We prove that random Clifford circuits with O(nlog2n) gates can be used to encode k qubits in n qubits with a distance d provided k/n23-h(d/n). In addition, we prove that such circuits typically have a depth of O(log3n).

arXiv:1312.7646•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•32 citations
Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth O(log⁡3n)O(\log^3 n)O(log3n). We show that the same asymptotic tradeoff is attained in optimal O(log⁡n)O(\log n)O(logn) depth under a gate distribution with a more restricted support. For every fixed δ>0δ>0δ>0 and sufficiently large nnn, if kn<1−H(dn)−dnlog⁡23−δ\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δnk​<1−H(nd​)−nd​log2​3−δ, we can construct random circuits of depth O(log⁡n)O(\log n)O(logn) which define, with high probability, an [n,k][n,k][n,k] stabilizer code of distance at least d+1d+1d+1, which matches the Ω(log⁡n)Ω(\log n)Ω(logn) light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of TTT independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using n/2n/2n/2 CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.
Efficient and high-performance quantum error correction is essential for achieving fault-tolerant quantum computing. Low-depth random circuits offer a promising approach to identifying effective and practical encoding strategies. In this work, we rigorously prove through information-theoretic analysis that one-dimensional logarithmic-depth random Clifford encoding circuits can achieve high quantum error correction performance. We demonstrate that these random codes typically exhibit good approximate quantum error correction capability by proving that their encoding rate achieves the hashing bound for Pauli noise and the channel capacity for erasure errors. We show that the error correction inaccuracy decays once a threshold of logarithmic depth is exceeded, resulting in negligible recovery errors. This threshold is shown to be lower than that of the simple separate block encoding, and the decay rate is higher. We further establish that these codes are optimal by proving that logarithmic depth is necessary to maintain a constant encoding rate and high error correction performance. To prove our results, we propose decoupling theorems tailored for one-dimensional low-depth circuits. These results also imply strong decoupling and rapid thermalization properties in low-depth random circuits and have potential applications in quantum information science and physics.
It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford Cr−1ZC^{r-1}ZCr−1Z gate, for every constant r≥3r\geq 3r≥3. In particular, we obtain length-nnn quantum LDPC codes (with constant-weight stabilizers) of polynomial distance d≥n(1−ε)/rd\geq n^{(1-ε)/r}d≥n(1−ε)/r supporting transversal Cr−1ZC^{r-1}ZCr−1Z gates on a close-to-linear number k≥n1−εk\geq n^{1-ε}k≥n1−ε of disjoint tuples of logical qubits, for arbitrarily small ε>0ε>0ε>0. Our construction is the first with constant-weight stabilizers that obtains dk≫ndk\gg ndk≫n, and as a consequence achieves arbitrarily small magic state overhead exponent γ=log⁡(n/k)/log⁡(d)>0γ=\log(n/k)/\log(d)>0γ=log(n/k)/log(d)>0. Comparable prior constructions instead required at least polylogarithmic stabilizer weight. We also show how to obtain linearly many k=Ω(n)k=Ω(n)k=Ω(n) logical Cr−1ZC^{r-1}ZCr−1Z gates, though with stabilizer weight and physical circuit depth nεn^εnε. We show that our transversal gates also support addressing (i.e. targeting) of specific logical qubits. To obtain our codes, we develop a general transformation based on cup products that maps classical codes satisfying a multiplication property to quantum codes with transversal Cr−1ZC^{r-1}ZCr−1Z. We apply this transformation to a new family of classical Tanner codes that we construct from punctured tensor products of algebraic codes.
The non-local interactions in several quantum device architectures allow for the realization of more compact quantum encodings while retaining the same degree of protection against noise. Anticipating that short to medium-length codes will soon be realizable, it is important to construct stabilizer codes that, for a given code distance, admit fault-tolerant implementations of logical gates with the fewest number of physical qubits. To this aim, we construct three kinds of codes encoding a single logical qubit for distances up to 31. First, we construct the smallest known doubly even codes, all of which admit a transversal implementation of the Clifford group. Applying a doubling procedure arXiv:1509.03239 to such codes yields the smallest known weak triply even codes for the same distances and number of encoded qubits. This second family of codes admit a transversal implementation of the logical T-gate. Relaxing the triply even property, we obtain our third family of triorthogonal codes with an even lower overhead at the cost of requiring additional Clifford gates to achieve the same logical operation. To our knowledge, these are the smallest known triorthogonal codes for their respective distances. While not qLDPC, the stabilizer generator weights of the code families with transversal T-gates scale roughly as the square root of their lengths.
Low-space-overhead fault-tolerant quantum computation requires not only high-rate quantum error-correcting codes but also space-efficient implementations of logical operations. Transversal and fold-transversal gates are promising since they limit error propagation and require no additional qubits. However, the logical operations they enable are typically restricted, and a central challenge is to construct codes that combine a complete set of logical Clifford gates with favorable code parameters. In this work, we introduce a family of quantum codes with an asymptotically constant encoding rate and sublogarithmically growing stabilizer weight, while supporting the entire logical Clifford group using only transversal and fold-transversal gates. Our construction is based on classical codes whose code spaces are absolutely irreducible Steinberg modules of their Tanner-graph automorphism groups. Taking hypergraph products of these classical codes yields quantum codes for which all logical Clifford operations can be synthesized from a fixed set of transversal and fold-transversal gates. Moreover, the slow growth of the stabilizer weight enables a high error-correcting performance in small instances. These results provide a path toward fault-tolerant quantum computation with low space overhead using transversal and fold-transversal gates.
Preparing arbitrary logical states is a central primitive for universal fault-tolerant quantum computation and the cost of encoded-state preparation contributes directly to the overall resource overhead. This makes the synthesis of efficient general-state encoding circuits an important problem, particularly with respect to two-qubit gate count and circuit depth. Yet the synthesis of such encoders has been studied less extensively than general Clifford circuit synthesis or the preparation of specific logical Pauli-eigenstates. In this work, we develop methods for synthesizing efficient encoders for arbitrary stabilizer codes. We formulate encoder synthesis as a search over stabilizer tableaus and introduce greedy and rollout-based algorithms that exploit the freedom among stabilizer-equivalent realizations of the same encoding isometry. For code families with a modular structure, such as generalized concatenated and holographic codes, we show how large encoders can be assembled from optimized local constituent encoders, and we use SMT-based exact synthesis to obtain optimal local circuits for small instances. We further evaluate the proposed methods on a broad set of stabilizer codes, including holographic and quantum low-density parity-check (qLDPC) codes, and compare them against recent encoder-synthesis methods and existing constructions from the literature, obtaining improvements of up to 43% in two-qubit gate count and up to 70% in depth. Our results support the optimization of encoded-state preparation in several fault-tolerant quantum-computing schemes, and all methods are openly available as part of the Munich Quantum Toolkit.