Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

• URL: http://arxiv.org/abs/2608.18536v1
• Date: Wed, 19 Aug 2026 04:39:23 GMT
• Title: Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings
• Abstract summary: We show that random circuits on two-qubit Clifford gates provide encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth.<n>We show that the same tradeoff is attained in optimal $O(log n)$ depth under a gate distribution with a more restricted support.<n>These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings.
• Score: 1.0171167503994478
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Link-middle-cut lower bounds for Clifford circuit synthesis [0.0]
  Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization.<n>We extend the link--middle-cut (LMC) framework for linear circuits to Clifford operators represented by binary symplectic tableaux.
  arXiv  Detail & Related papers  (2026-09-14T18:42:19Z)
• Optimal Approximation of Single Qubit Rotations within a Quantum Circuit [0.12599533416395764]
  Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T.<n>As a baseline, Diagonal approximation can be used for single-qubit Pauli rotations.<n>In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem.
  arXiv  Detail & Related papers  (2026-05-10T17:38:53Z)
• Clifford+V synthesis for multi-qubit unitary gates [0.0]
  We develop a general framework for synthesizing target gates by using a finite set of basic gates.<n>We introduce a suboptimal but short run-time algorithm for synthesizing multi-qubit controlled gates.
  arXiv  Detail & Related papers  (2025-10-09T14:57:55Z)
• Unitary designs in nearly optimal depth [40.28216388589026]
  We construct unitary designs on qubits in circuit depth $O(log k log log n k / varepsilon)$.<n>The depth is exponentially improved over all known results in all three parameters $n$, $k$, $varepsilon$.<n>We also develop a new analytical framework for bounding errors in quantum experiments involving many queries to random unitaries.
  arXiv  Detail & Related papers  (2025-07-08T17:48:33Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.<n>This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Fast estimation of outcome probabilities for quantum circuits [0.0]
  We present two classical algorithms for the simulation of universal quantum circuits on $n$ qubits. Our algorithms complement each other by performing best in different parameter regimes. We provide a C+Python implementation of our algorithms and benchmark them using random circuits.
  arXiv  Detail & Related papers  (2021-01-28T19:00:04Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Quantum coding with low-depth random circuits [2.4201087215689947]
  We use ensembles of low-depth random circuits with local connectivity to generate quantum error-correcting codes. For random stabilizer codes and the erasure channel, we find strong evidence that a depth $O(log N)$ random circuit is necessary. These results indicate that finite-rate quantum codes are practically relevant for near-term devices.
  arXiv  Detail & Related papers  (2020-10-19T18:25:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.