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
Small set-flip linear-time decoder, which corrects \(\Omega(n^{1/2})\) adversarial errors [1].Log-time decoder [2].Constant-time decoder [3].2D geometrically local syndrome extraction circuits acting on a patch of \(N\) physical qubits have to be of depth at least \(\Omega(n/\sqrt{N})\) [4].
Fault Tolerance
Fault-tolerance with constant overhead can be achieved [2].
Threshold
Locally stochastic noise: \(2.7 \cdot 10^{-16}\) [5].
Parent
Cousin
References
- [1]
- A. Leverrier, J.-P. Tillich, and G. Zemor, “Quantum Expander Codes”, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015) arXiv:1504.00822 DOI
- [2]
- 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) (2018) arXiv:1808.03821 DOI
- [3]
- A. Grospellier. Constant time decoding of quantum expander codes and application to fault-tolerant quantum computation. PhD thesis, Inria Paris (2019).
- [4]
- 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
- [5]
- 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 (2018) arXiv:1711.08351 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