Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation
arXiv:2207.08826 · doi:10.1038/s41567-023-02325-8
Abstract
Scaling up quantum computers to attain substantial speedups over classical computing requires fault tolerance. Conventionally, protocols for fault-tolerant quantum computation demand excessive space overheads by using many physical qubits for each logical qubit. A more recent protocol using quantum analogues of low-density parity-check codes needs only a constant space overhead that does not grow with the number of logical qubits. However, the overhead in the processing time required to implement this protocol grows polynomially with the number of computational steps. To address these problems, here we introduce an alternative approach to constant-space-overhead fault-tolerant quantum computing using a concatenation of multiple small-size quantum codes rather than a single large-size quantum low-density parity-check code. We develop techniques for concatenating different quantum Hamming codes with growing sizes. As a result, we construct a low-overhead protocol to achieve constant space overhead and only quasi-polylogarithmic time overhead simultaneously. Our protocol is fault tolerant even if a decoder has a non-constant runtime, unlike the existing constant-space-overhead protocol. This code concatenation approach will make possible a large class of quantum speedups within feasibly bounded space overhead yet negligibly short time overhead.
57 pages, 16 figures
References in corpus (37)
- Quantum Computing in the NISQ era and beyond
- Quantum Teleportation is a Universal Computational Primitive
- Topological quantum memory
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Improved Simulation of Stabilizer Circuits
- Quantum Computing with Very Noisy Devices
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Surface code quantum computing by lattice surgery
- A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
- Methodology for quantum logic gate constructions
- Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
- Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
- The XZZX Surface Code
- Quantum error correction with only two extra qubits
- Ultrahigh Error Threshold for Surface Codes with Biased Noise
- Fault-Tolerant Quantum Computation For Local Non-Markovian Noise
- Flag fault-tolerant error correction with arbitrary distance codes
- Fault-tolerant thresholds for the surface code in excess of 5% under biased noise
- Local Fault-tolerant Quantum Computation
- Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
- Constant overhead quantum fault-tolerance with quantum expander codes
- Low-overhead fault-tolerant quantum computing using long-range connectivity
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Flag fault-tolerant error correction for any stabilizer code
- Quantum Expander Codes
- Constant-overhead quantum error correction with thin planar connectivity
- Fault-tolerant magic state preparation with flag qubits
- Parallel window decoding enables scalable fault tolerant quantum computation
- Proof of finite surface code threshold for matching
- Improved quantum hypergraph-product LDPC codes
- Fault-Tolerant Logical Gate Networks for CSS Codes
- Universal logical gates with constant overhead: instantaneous Dehn twists for hyperbolic quantum codes
- Techniques for combining fast local decoders with global decoders under circuit-level noise
- Fault-tolerant Preparation of Stabilizer States for Quantum CSS Codes by Classical Error-Correcting Codes
- Efficient Preparation of Large Block Code Ancilla States for Fault-tolerant Quantum Computation
- Constant depth fault-tolerant Clifford circuits for multi-qubit large block codes
- Modular decoding: parallelizable real-time decoding for quantum computers
Cited by in corpus (29)
- Entangling four logical qubits beyond break-even in a nonlocal code
- Scalable Networking of Neutral-Atom Qubits: Nanofiber-Based Approach for Multiprocessor Fault-Tolerant Quantum Computer
- Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation
- Energy-Consumption Advantage of Quantum Computation
- Fault-tolerant quantum algorithms for quantum molecular systems: A survey
- Constant-Overhead Fault-Tolerant Bell-Pair Distillation using High-Rate Codes
- Many-hypercube codes: High-rate quantum error-correcting codes for high-performance fault-tolerant quantum computing
- Hierarchical memories: Simulating quantum LDPC codes with local gates
- Long-Range Interaction via Resonator-Induced Phase in Superconducting Qubits
- Concatenate codes, save qubits
- Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder
- Efficient fault-tolerant code switching via one-way transversal CNOT gates
- Concatenated Steane code with single-flag syndrome checks
- Non-Clifford and parallelizable fault-tolerant logical gates on constant and almost-constant rate homological quantum LDPC codes via higher symmetries
- Logical entanglement distribution between distant 2D array qubits
- Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
- Far from Perfect: Quantum Error Correction with (Hyperinvariant) Evenbly Codes
- Fault-tolerant quantum computation with constant overhead for general noise
- Low-density parity-check representation of fault-tolerant quantum circuits
- Entanglement boosting: Low-volume logical Bell pair preparation for distributed fault-tolerant quantum computation
- Noise-Agnostic Unbiased Quantum Error Mitigation for Logical Qubits
- Towards self-correcting quantum codes for neutral atom arrays
- Quantum memory based on concatenating surface codes and quantum Hamming codes
- Time-frequency-correlated Native CCZ Gate in Superconducting Circuits
- Bounds on concatenated entanglement-assisted quantum error-correcting codes
- Efficient decoding of stabilizer code by single-qubit local operations and classical communication
- Subsystem many-hypercube codes: High-rate concatenated codes with low-weight syndrome measurements
- Accelerating Fault-Tolerant Quantum Computation with Good qLDPC Codes
- Color code with a logical control- gate using transversal rotations