Low-Overhead Fault Tolerance in Two Dimensions
summary
Constructs a 2D fault-tolerance scheme that uses only nearest-neighbor 2D gates to simulate long-range LDPC check circuits via graph edge coloring and permutation routing, pays a polylogarithmic depth and space overhead, and recovers an exponential logical error suppression with a threshold under locally decaying noise. Uses polylog-sized surface-code blocks to make per-cycle noise constant, routes with Knuth sorting and Abenstein‑Baumslag style product routing, and outlines bootstrapping to beat the polylogarithmic overhead.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 0:58LDPC Code
- 2:18Locality is a Curse
- 4:39Main Result
- 7:03Comparison
- 8:26Geometrical Locality
- 15:28Permutation Routing
- 19:06Surface Codes
- 27:41questions
related talks
01h 37mFault-Tolerance Against Adversarial Errors & PCPs
30mHow to fault-tolerantly realize any quantum circuit with local operations
59mDawn in the age of quantum fault tolerance
35mHalving the cost of surface codes by running error correction at the logical level
39mExpansion of Higher-Dimensional Cubical Complexes With Application To Good ...
51mPanel Discussion
45mOn the NLTS Conjecture
53mTalk by Chris Pattison (UC Berkeley)