Fault-Tolerant Quantum Computation with Constant Overhead

Abstract

What is the minimum number of extra qubits needed to perform a large fault-tolerant quantum circuit? Working in a common model of fault-tolerance, I show that in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant. The construction makes use of quantum low-density parity check codes, and the asymptotic overhead of the protocol is equal to that of the family of quantum error-correcting codes underlying the fault-tolerant protocol.

32 pages. v2 has new title, discussion of hyperbolic codes, other minor edits. v3 has additional corrections and clarifications

References in corpus (6)

• Fault-tolerant quantum computation with high threshold in two dimensions
• Restrictions on Transversal Encoded Quantum Gate Sets
• Fault-Tolerant Quantum Computation For Local Non-Markovian Noise
• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Decoding in Hyperbolic Spaces: LDPC Codes With Linear Rate and Efficient Error Correction
• Scalable Quantum Computation in the Presence of Large Detected-Error Rates

Cited by in corpus (13)

• Quantum advantage with shallow circuits
• Quantum annealing correction for random Ising problems
• Quantum coding with low-depth random circuits
• Long-range big quantum-data transmission
• Reducing the overhead for quantum computation when noise is biased
• Understanding Quantum Control Processor Capabilities and Limitations through Circuit Characterization
• Universal Fault-Tolerant Quantum Computing with Stabiliser Codes
• Numerical and analytical bounds on threshold error rates for hypergraph-product codes
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes
• A lower bound on the space overhead of fault-tolerant quantum computation
• Lift-Connected Surface Codes
• Efficient decoding of random errors for quantum expander codes