The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
summary
Identifies that common control-flow constructs cause polynomial increases in T-complexity under surface-code error correction and gives a precise cost model that counts T gates from nested MCX controls. Implements program-level rewrites in Spire (Tower extension) — notably conditional flattening and conditional narrowing — and shows on 11 benchmarks that quadratic T-scaling drops to linear, with Spire producing asymptotically optimal circuits while using 54×–2400× less compile time than the best competing circuit optimizers.
AI-written summary · about
chapters (9)
- 0:00T-Complexity and error correction
- 2:27Quantum algorithms cost
- 4:53Quantum logic gates basics
- 8:02Error correction overhead
- 11:52T-Complexity cost model
- 13:37T-Complexity optimizations
- 15:24Evaluation vs optimizers
- 16:49Conclusion and future
- 17:32Question and Answer Session
related talks
33mOptimizing the Annoying Stuff: Reducing Costs Obscured by the Abstract Circuit Model
01h 37mFault-Tolerance Against Adversarial Errors & PCPs
32mOptimal Quantum Programs
29mEfficiently Verifying Quantum Programs with Few T Gates
39mBuilding a Compiler for Quantum Computers
51mOn constant T-depth circuits
19mAvenues for Quantum Error Correction and Mitigation
19mOptimizing Ancilla-Based Quantum Circuits with SPARE