# Quantum expander code[1]

## Description

CSS codes constructed from a hypergraph product of bipartite expander graphs 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 \(\Omega(n^{1/2})\).

## Rate

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

## Decoding

Ref. [1] details a linear time decoder, which corrects \(\Omega(n^{1/2})\) adversarial errors.

## Fault Tolerance

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

## Threshold

Current estimate of \(2.7 \cdot 10^{-16}\) in locally stochastic noise model [3].

## Parent

## Cousin

## Zoo code information

## References

- [1]
- A. Leverrier, J.-P. Tillich, and G. Zemor, “Quantum Expander Codes”, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015). DOI; 1504.00822
- [2]
- Omar Fawzi, Antoine Grospellier, and Anthony Leverrier, “Constant overhead quantum fault-tolerance with quantum expander codes”. 1808.03821
- [3]
- Omar Fawzi, Antoine Grospellier, and Anthony Leverrier, “Efficient decoding of random errors for quantum expander codes”. 1711.08351

## Cite as:

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