Quantum expander code

Quantum expander code[1]

Alternative names: Quantum Sipser-Spielman code, Expander HGP code.

Description

CSS code constructed from a hypergraph product of bipartite expander graphs [2] with bounded left and right vertex degrees. For every bipartite graph there is an associated matrix (the parity check matrix) with columns indexed by the left vertices, rows indexed by the right vertices, and 1 entries whenever a left and right vertex are connected. This matrix can serve as the parity check matrix of a classical code. Two bipartite expander graphs can be used to construct a quantum CSS code (the quantum expander code) by using the parity check matrix of one as \(X\) checks, and the parity check matrix of the other as \(Z\) checks.

Protection

Pauli errors of weight \(\leq t\), distance scales as order \(\Omega(n^{1/2})\).

Rate

\([[n,k=\Theta(n),d=O(\sqrt{n})]]\) code with asymptotically constant rate.

Decoding

Small set-flip linear-time decoder, which corrects order \(\Omega(n^{1/2})\) adversarial errors [1].Log-time decoder [3].Constant-time decoder [4].2D geometrically local syndrome extraction circuits acting on a patch of \(N\) physical qubits have to be of depth of order \(\Omega(n/\sqrt{N})\) or deeper. More generally, there is a tradeoff between the depth \(D\) and width \(W\) of a syndrome extraction circuit, namely, \(D \geq n/\sqrt{W}\) [5].

Fault Tolerance

Fault-tolerance with constant overhead can be achieved [3].

Threshold

Locally stochastic noise: \(2.7 \cdot 10^{-16}\) [6].

Cousins

Expander code
Topological code— Quantum expander codes realize topological quantum spin glass order [7].
Self-correcting quantum code— Constant-rate random (quantum) expander codes are self-correcting (quantum) memories, but have no thermodynamic phase transitions [8].

Member of code lists

Primary Hierarchy

Quantum Domain

Qubit Kingdom

Qubit codeQECC Quantum

Union stabilizer (USt) codeQECC Quantum

Qubit stabilizer codeStabilizer Hamiltonian-based Qubit QECC Quantum

Coherent-parity-check (CPC) code

Qubit CSS codeCSS Stabilizer Hamiltonian-based QECC Quantum

Generalized homological-product qubit CSS codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum

Fiber-bundle codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum

Homological product code

Hypergraph product (HGP) codeCSS Generalized homological-product Lattice stabilizer QLDPC Stabilizer Hamiltonian-based Qubit QECC Quantum

Parents

Hypergraph product (HGP) code

Galois-qudit expander codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum

Single-shot codeQECC Quantum

Quantum expander codes are single-shot [3].

Quantum expander code

References

[1]: A. Leverrier, J.-P. Tillich, and G. Zemor, “Quantum Expander Codes”, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science 810 (2015) arXiv:1504.00822 DOI
[2]: S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
[3]: O. Fawzi, A. Grospellier, and A. Leverrier, “Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes”, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) 743 (2018) arXiv:1808.03821 DOI
[4]: A. Grospellier. Constant time decoding of quantum expander codes and application to fault-tolerant quantum computation. PhD thesis, Inria Paris (2019).
[5]: N. Delfosse, M. E. Beverland, and M. A. Tremblay, “Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes”, (2021) arXiv:2109.14599
[6]: O. Fawzi, A. Grospellier, and A. Leverrier, “Efficient decoding of random errors for quantum expander codes”, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing 521 (2018) arXiv:1711.08351 DOI
[7]: B. Placke, T. Rakovszky, N. P. Breuckmann, and V. Khemani, “Topological Quantum Spin Glass Order and its realization in qLDPC codes”, (2024) arXiv:2412.13248
[8]: Y. Hong, J. Guo, and A. Lucas, “Quantum memory at nonzero temperature in a thermodynamically trivial system”, Nature Communications 16, (2025) arXiv:2403.10599 DOI

Page edit log

Victor V. Albert (2022-09-23) — most recent
Victor V. Albert (2021-12-16)
Nolan Coble (2021-12-03)

Cite as:

“Quantum expander code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/quantum_expander

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/qldpc/homological/balanced_product/quantum_expander.yml.