Quantum Expander Codes

Abstract

We present an efficient decoding algorithm for constant rate quantum hypergraph-product LDPC codes which provably corrects adversarial errors of weight $\Omega (\sqrt{n})$ for codes of length $n$. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.

References in corpus (2)

• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Local Hamiltonians with Approximation-Robust Entanglement

Cited by in corpus (40)

• Constant overhead quantum fault-tolerance with quantum expander codes
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• Constant-overhead quantum error correction with thin planar connectivity
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• Quantum coding with low-depth random circuits
• Trapping Sets of Quantum LDPC Codes
• Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Combining hard and soft decoders for hypergraph product codes
• Fault-tolerant gates on hypergraph product codes
• Universal logical gates with constant overhead: instantaneous Dehn twists for hyperbolic quantum codes
• Beyond single-shot fault-tolerant quantum error correction
• Scalable Networking of Neutral-Atom Qubits: Nanofiber-Based Approach for Multiprocessor Fault-Tolerant Quantum Computer
• Toward a 2D Local Implementation of Quantum LDPC Codes
• Generalized Belief Propagation Algorithms for Decoding of Surface Codes
• Numerical study of hypergraph product codes
• Many-hypercube codes: High-rate quantum error-correcting codes for high-performance fault-tolerant quantum computing
• Fault-tolerant gates via homological product codes
• Hierarchical memories: Simulating quantum LDPC codes with local gates
• Towards local testability for quantum coding
• Quantum Pin Codes
• Quantum memory at nonzero temperature in a thermodynamically trivial system
• Distance-preserving stabilizer measurements in hypergraph product codes
• Low-density parity-check codes as stable phases of quantum matter
• Quantum XYZ Product Codes
• Optimal quantum subsystem codes in 2-dimensions
• Fault-tolerant logical measurements via homological measurement
• Partial Syndrome Measurement for Hypergraph Product Codes
• A linear-time benchmarking tool for generalized surface codes
• Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes
• Layer Codes
• Software Tools for Decoding Quantum Low-Density Parity Check Codes
• Local Probabilistic Decoding of a Quantum Code
• Union-Find Decoders For Homological Product Codes
• Low-overhead fault-tolerant quantum computation by gauging logical operators
• Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically
• Generalized quantum data-syndrome codes and belief propagation decoding for phenomenological noise
• Single-shot preparation of hypergraph product codes via dimension jump
• Efficient decoding of random errors for quantum expander codes
• Encoders and Decoders for Quantum Expander Codes Using Machine Learning