A lower bound on the space overhead of fault-tolerant quantum computation
summary
Shows that for any non‑unitary qubit noise channel N any fault‑tolerant encoding needs at least n' ≥ α_N log T physical qubits (α_N computable from N), and if the quantum capacity Q(N)=0 then space overhead must exceed 1/Q(N) (so fault tolerance fails). Proof uses Bloch‑sphere parametrization, chi‑squared divergence and trace‑norm contraction of tensor powers, separates unital vs non‑unital channels, and yields an exponential bound for amplitude‑damping noise.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:21Noisy quantum computation
- 1:19Fault-tolerant threshold theorem
- 3:08Fault-tolerant quantum computation
- 5:12Circuit model
- 6:21Noise model
- 7:21Main result
- 9:24Quantum fault tolerance model
- 11:48Technical Lemma
- 13:19Corollary
- 14:12Previous works & significance of our results
- 21:03Proof outline
- 30:00Summary and Outlook
related talks
03mQuantum Algorithms, Complexity, and Fault Tolerance
49mEvidence for the utility of quantum computing before fault tolerance
59mDawn in the age of quantum fault tolerance
53mFundamental limits to quantum computation
19mAvenues for Quantum Error Correction and Mitigation
30mHow to fault-tolerantly realize any quantum circuit with local operations
47mHigh-Threshold and Low-Overhead Fault-Tolerant Quantum Memory
28mThe Problem with Qubits