[Jump to code hierarchy]

Random polylog-depth Clifford-circuit code [1]

Alternative Names: Brown-Fawzi code.

Description

An \([[n,k]]\) stabilizer code whose encoder is a random Clifford circuit of polylogarithmic depth, with two-qubit gates acting on randomly chosen pairs of qubits. The gates are applied either one at a time to random pairs [1] or in parallel layers on random perfect matchings [2].

An \(n\)-qubit encoding circuit with \(O(n \log^2 n)\) random two-qubit Clifford gates yields a code with distance at least \(d+1\) with probability \(1 - O(1/n^8)\) [1]. This holds provided that \begin{equation} \frac{k}{n} < 1 - \frac{d}{n}\log_2 3 - h\left(\frac{d}{n}\right)~,\tag*{$(1)$} \end{equation}where \(h\) is the entropy function. Since two gates acting on disjoint qubits can be executed simultaneously, the depth of a circuit of this size is typically of order \(O(\log^3 n)\).

In a random matching circuit, each layer pairs the qubits by a uniformly random perfect matching and applies an independent random two-qubit Clifford gate to each pair [2; Def. 2.2]. Depth \(O(\log n)\) attains the same tradeoff whenever the gate distribution assigns positive probability to an entangling gate and is invariant under inversion and under left and right single-qubit twirls [2; Thm. 2.3]. The twirling group is a single-qubit Clifford subgroup acting transitively on \(\{X,Y,Z\}\) up to sign [2; Def. 2.1]. CNOT gates twirled by independent single-qubit Cliffords drawn from \(\{I,HS,(HS)^2\}\) satisfy these conditions, for \(O(n\log n)\) CNOT gates in total [2; Cor. 1.3, Rem. 2.1]. Since circuits of one- and two-qubit gates need depth \(\Omega(\log n)\) for linear distance, this depth is optimal up to a constant factor [1,2].

Rate

Achieves the quantum GV bound [1,2].

Encoding

Random Clifford circuit of depth \(O(\log^3 n)\) [1] or random matching circuit of depth \(O(\log n)\) [2].

Cousin

  • Circuit-to-Hamiltonian approximate code— Circuit-to-Hamiltonian approximate codes are constructed by converting the encoding circuit of a random polylog-depth Clifford-circuit code into a Hamiltonian using the spacetime circuit-to-Hamiltonian construction [3,4].

References

  1. [1]

    W. Brown and O. Fawzi, “Short random circuits define good quantum error correcting codes”, 2013 IEEE International Symposium on Information Theory (2013) arXiv:1312.7646 DOI

  2. [2]

    E. Anand, E. Gorokhovsky, J. Hritz, and J. Sun, “Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings”, (2026) arXiv:2608.18536

  3. [3]

    A. Mizel, D. A. Lidar, and M. Mitchell, “Simple Proof of Equivalence between Adiabatic Quantum Computation and the Circuit Model”, Physical Review Letters 99, (2007) arXiv:quant-ph/0609067 DOI

  4. [4]

    N. P. Breuckmann and B. M. Terhal, “Space-time circuit-to-Hamiltonian construction and its applications”, Journal of Physics A: Mathematical and Theoretical 47, 195304 (2014) arXiv:1311.6101 DOI

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: nonlocal_lowdepth

Cite as:
“Random polylog-depth Clifford-circuit code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/nonlocal_lowdepth, arXiv:2606.11484
BibTeX:
@incollection{eczoo_nonlocal_lowdepth,
title={Random polylog-depth Clifford-circuit code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/nonlocal_lowdepth}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/nonlocal_lowdepth

Cite as:

“Random polylog-depth Clifford-circuit code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/nonlocal_lowdepth, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/dynamic/random/nonlocal_lowdepth.yml.