Random polylog-depth Clifford-circuit code [1]
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}
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].
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].
Member of code lists
Primary Hierarchy
References
- [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]
E. Anand, E. Gorokhovsky, J. Hritz, and J. Sun, “Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings”, (2026) arXiv:2608.18536
- [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]
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
- Victor V. Albert (2026-10-26) — most recent
- Victor V. Albert (2026-06-08)
- Victor V. Albert (2022-01-20)
- Srilekha Gandhari (2021-12-14)
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