The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation

Explore the impact of quantum error correction on control flow in quantum computation through this 19-minute conference talk from PLDI 2024. Delve into the concept of T-complexity and its role as a performance bottleneck in quantum programs. Discover how programming abstractions like quantum if-statements can lead to polynomial increases in T-complexity, potentially diminishing the computational advantage of quantum algorithms. Learn about a cost model for analyzing T-complexity under quantum error correction and a set of program-level optimizations to mitigate these costs. Examine the implementation of these optimizations in Spire, an extension of the Tower quantum compiler, and review empirical results from 11 benchmark programs. Compare the effectiveness of optimizing programs before compilation versus using quantum circuit optimizers, and understand the significant compile time savings achieved by Spire.

[PLDI24] The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation