When T-Depth Misleads: Predicting Fault-Tolerant Quantum Execution Slowdown under Magic-State Delivery Constraints

Abstract

The efficient execution of fault-tolerant quantum algorithms is fundamentally limited by the production rate of magic states required for non-Clifford operations. While circuit optimization typically targets T-depth, static T-depth does not reliably predict executable performance under bounded T-state delivery. We introduce a model that captures demand-supply imbalance using two key quantities: slack ratio, a structural indicator of scheduling flexibility, and Delta_max, a measure of cumulative demand surplus. We show that Delta_max is a strong schedule-level indicator of execution slowdown and yields a provable lower bound on executable makespan for a fixed schedule. Empirical evaluation on constructed directed acyclic graph (DAG) families, with arithmetic circuits and exact quantum Fourier transform (QFT) traces providing additional grounding, shows that slack ratio is a stronger structural predictor than T-depth for stall and inversion risk, while Delta_max is the strongest predictor of slowdown. Across 4,904 instances, the lower bound shows zero violations, with 88.9% of cases within one cycle. These results highlight the importance of explicitly modeling delivery constraints in fault-tolerant quantum compilation.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.