Fault-Tolerance Against Adversarial Errors & PCPs
summary
Constructs a compiler that turns any logical circuit into a fault‑tolerant physical circuit that tolerates an almost linear number of adversarial bit/qubit flips per time step (≈ N^{1−o(1)}), gives a classical PCP corollary with inverse‑polylog soundness, and a quantum analogue with subpolynomial depth, roughly n^5 space overhead and a requirement for free noiseless side classical computation. Key tools: high‑dimensional product of Reed‑Solomon codes (subsystem/gauge checks), transversal Toffoli via degree‑shifted encodings, code‑switching/degree reduction, and a circuit→Hamiltonian conjecture tying low‑energy states to low‑error executions.
AI-written summary · about
chapters (16)
- 0:00Fault-tolerance and PCPs intro
- 1:02Probabilistically checkable proofs
- 4:11Robust verification to computation
- 6:19Classical fault-tolerance
- 10:39Quantum fault-tolerance and QPCP
- 15:21Classical fault-tolerance to PCPs
- 23:31Quantum roadmap to quantum PCPs
- 29:13Circuit-to-Hamiltonian conjecture
- 31:01Quantum memory with Toffoli
- 50:07High-error fault-tolerance challenges
- 1:00:10Classical memory with multiplication
- 1:04:28Quantum memory with non-commuting checks
- 1:19:57Distance for quantum product codes
- 1:22:28Degree reduction and computation
- 1:26:29Summary of main results
- 1:31:06Conclusion and future
related talks
03mQuantum Algorithms, Complexity, and Fault Tolerance
59mDawn in the age of quantum fault tolerance
19mAvenues for Quantum Error Correction and Mitigation
36mCircuit-To-Hamiltonian From Tensor Networks and Fault Tolerance
47mHigh-Threshold and Low-Overhead Fault-Tolerant Quantum Memory
49mEvidence for the utility of quantum computing before fault tolerance
35mLow-Overhead Fault Tolerance in Two Dimensions
30mHow to fault-tolerantly realize any quantum circuit with local operations