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 entries equal to 1 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) via the hypergraph product of their parity check matrices.

Protection

The code family has distance scaling as order \(\Omega(n^{1/2})\), and the small-set-flip decoder corrects a constant fraction of that many adversarial Pauli errors [1].

Rate

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

Encoding

Single-shot state preparation with constant space-time overhead [3].

Gates

Dimensional jump protocols between various quantum expander codes [3].

Decoding

Small set-flip linear-time decoder, which corrects order \(\Omega(n^{1/2})\) adversarial errors [1]. The decoder has been generalized to hypergraph products of 3 or more expander codes [3].Log-time decoder [4].Constant-time decoder [5].

Fault Tolerance

Fault-tolerance with constant overhead can be achieved [4].Corollary 1 of the first arXiv version of Ref. [6] asserts that 2D geometrically local syndrome extraction circuits on a patch of \(N\) physical qubits require depth of order \(\Omega(n/\sqrt{N})\) for QLDPC families with expanding generating sets. This corollary does not hold as stated, since recombining the weight-four checks of annular surface codes yields expanding bounded-weight generating sets measured in depth \(13\) [7; Cor. 5.3].

Threshold

Locally stochastic noise: \(2.7 \cdot 10^{-16}\) [8].Dimensional jump protocols between various quantum expander codes have a threshold under local stochastic noise [3].

Cousins

Expander code— Quantum expander codes are quantum analogues of expander codes.
Topological code— Quantum expander codes realize topological quantum spin glass order [9].
Higher-dimensional homological product code— Quantum expander codes have been generalized to hypergraph products of 3 or more expander codes [3].
Self-correcting quantum code— Constant-rate random (quantum) expander codes are self-correcting (quantum) memories, but have no thermodynamic phase transitions [10].

Member of code lists

Primary Hierarchy

Quantum Domain

Qubit Kingdom

Qubit codeQECC Quantum

Union stabilizer (USt) codeQECC Quantum

Qubit stabilizer codeQubit Stabilizer Hamiltonian-based QECC Quantum

Coherent-parity-check (CPC) code

Qubit CSS codeCSS Stabilizer Hamiltonian-based QECC Quantum

Generalized homological-product qubit CSS codeQLDPC Qubit CSS Generalized homological-product Stabilizer Hamiltonian-based QECC Quantum

Higher-dimensional homological product code

Homological product codeQLDPC Qubit CSS Generalized homological-product Stabilizer Hamiltonian-based QECC Quantum

Hypergraph product (HGP) codeGeneralized homological-product CSS Stabilizer Hamiltonian-based QECC Quantum

Parents

Hypergraph product (HGP) code

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

Quantum expander codes are the \(q=2\) specialization of Galois-qudit expander codes.

Single-shot codeQECC Quantum

Quantum expander codes are single-shot [4].