Constant overhead quantum fault-tolerance with quantum expander codes
arXiv:1808.03821 · doi:10.1109/FOCS.2018.00076
Abstract
We prove that quantum expander codes can be combined with quantum fault-tolerance techniques to achieve constant overhead: the ratio between the total number of physical qubits required for a quantum computation with faulty hardware and the number of logical qubits involved in the ideal computation is asymptotically constant, and can even be taken arbitrarily close to 1 in the limit of small physical error rate. This improves on the polylogarithmic overhead promised by the standard threshold theorem. To achieve this, we exploit a framework introduced by Gottesman together with a family of constant rate quantum codes, quantum expander codes. Our main technical contribution is to analyze an efficient decoding algorithm for these codes and prove that it remains robust in the presence of noisy syndrome measurements, a property which is crucial for fault-tolerant circuits. We also establish two additional features of the decoding algorithm that make it attractive for quantum computation: it can be parallelized to run in logarithmic depth, and is single-shot, meaning that it only requires a single round of noisy syndrome measurement.
32 pages
References in corpus (2)
Cited by in corpus (37)
- Quantum Low-Density Parity-Check Codes
- Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
- The XZZX Surface Code
- Quantum LDPC Codes with Almost Linear Minimum Distance
- Quantum advantage with noisy shallow circuits in 3D
- Balanced Product Quantum Codes
- Coherent spin qubit transport in silicon
- Constant overhead quantum fault-tolerance with quantum expander codes
- Low-overhead fault-tolerant quantum computing using long-range connectivity
- Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes
- Quantum Computing for Molecular Biology
- Parallel window decoding enables scalable fault tolerant quantum computation
- Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation
- Combining hard and soft decoders for hypergraph product codes
- Improved single-shot decoding of higher dimensional hypergraph product codes
- Quantifying nonlocality: how outperforming local quantum codes is expensive
- Finite Rate QLDPC-GKP Coding Scheme that Surpasses the CSS Hamming Bound
- Fault-tolerant gates on hypergraph product codes
- Connectivity constrains quantum codes
- Beyond single-shot fault-tolerant quantum error correction
- Morphing quantum codes
- Fold-Transversal Clifford Gates for Quantum Codes
- Numerical study of hypergraph product codes
- Fast erasure decoder for hypergraph product codes
- Fault-tolerant Coding for Quantum Communication
- Quantum XYZ Product Codes
- On maximum-likelihood decoding with circuit-level errors
- Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder
- Golden codes: quantum LDPC codes built from regular tessellations of hyperbolic 4-manifolds
- A lower bound on the space overhead of fault-tolerant quantum computation
- Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise
- Union-Find Decoders For Homological Product Codes
- A Converse for Fault-tolerant Quantum Computation
- Single-shot quantum error correction with the three-dimensional subsystem toric code
- Interactive quantum advantage with noisy, shallow Clifford circuits
- Limits of Fault-Tolerance on Resource-Constrained Quantum Circuits for Classical Problems
- Encoders and Decoders for Quantum Expander Codes Using Machine Learning