Beyond single-shot fault-tolerant quantum error correction

Abstract

Extensive quantum error correction is necessary in order to perform a useful computation on a noisy quantum computer. Moreover, quantum error correction must be implemented based on imperfect parity check measurements that may return incorrect outcomes or inject additional faults into the qubits. To achieve fault-tolerant error correction, Shor proposed to repeat the sequence of parity check measurements until the same outcome is observed sufficiently many times. Then, one can use this information to perform error correction. A basic implementation of this fault tolerance strategy requires $\Omega (r{d}^2)$ parity check measurements for a distance-d code defined by r parity checks. For some specific highly structured quantum codes, Bombin has shown that single-shot fault-tolerant quantum error correction is possible using only r measurements. In this work, we demonstrate that fault-tolerant quantum error correction can be achieved using $O(d\log (d))$ measurements for any code with distance $d\ge \Omega (n^{\alpha })$ for some constant $\alpha >0$. Moreover, we prove the existence of a sub-single-shot fault-tolerant quantum error correction scheme using fewer than r measurements. In some cases, the number of parity check measurements required for fault-tolerant quantum error correction is exponentially smaller than the number of parity checks defining the code.

arXiv comment32 pages, 11 figures

References in corpus (22)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Surface codes: Towards practical large-scale quantum computation
• Good Quantum Error-Correcting Codes Exist
• Topological quantum memory
• Multiple Particle Interference and Quantum Error Correction
• Elucidating Reaction Mechanisms on Quantum Computers
• Sparse Graph Codes for Quantum Error-Correction
• Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
• Quantum error correction with only two extra qubits
• Efficient fault-tolerant quantum computing
• Single-shot fault-tolerant quantum error correction
• Flag fault-tolerant error correction with arbitrary distance codes
• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Constant overhead quantum fault-tolerance with quantum expander codes
• Fault-tolerant error correction with the gauge color code
• A theory of single-shot error correction for adversarial noise
• Quantum Expander Codes
• Cellular-automaton decoders with provable thresholds for topological codes
• Errors in Flash-Memory-Based Solid-State Drives: Analysis, Mitigation, and Recovery
• Ability of stabilizer quantum error correction to protect itself from its own imperfection
• Quantum convolutional data-syndrome codes
• On maximum-likelihood decoding with circuit-level errors

Cited by in corpus (8)

• Focus beyond quadratic speedups for error-corrected quantum advantage
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Pauli channels can be estimated from syndrome measurements in quantum error correction
• Learning logical Pauli noise in quantum error correction
• Optimal noise estimation from syndrome statistics of quantum codes
• Fault-tolerant syndrome extraction and cat state preparation with fewer qubits
• Distance-four quantum codes with combined postselection and error correction
• Single-shot quantum error correction with the three-dimensional subsystem toric code