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

1. Problem Statement

In Fault-Tolerant Quantum Computing (FTQC), non-Clifford operations (specifically T gates) require "magic states" produced by resource-intensive distillation factories. Traditional circuit optimization focuses on minimizing T-depth (the number of sequential T-gate layers), assuming infinite or on-demand supply of magic states.

However, in realistic FTQC architectures, magic-state production is capacity-constrained. The paper identifies a critical mismatch:

• The Misleading Metric: A circuit with a lower static T-depth may execute slower than a circuit with a higher T-depth if the low-depth schedule concentrates T-gate demand into bursts that exceed the factory's delivery rate.
• The Consequence: This leads to execution stalls (waiting for magic states), increasing the total execution time (makespan) and the "protected idle time" where logical qubits must remain under active error correction, thereby increasing space-time volume and failure risk.
• The Gap: Existing metrics (T-count, T-depth) fail to predict this slowdown because they ignore the temporal distribution of demand relative to supply constraints.

2. Methodology

The authors propose a new execution model and predictive framework to quantify the impact of bounded magic-state delivery.

A. Execution Model

• Representation: Circuits are modeled as Directed Acyclic Graphs (DAGs).
• Parameters:
  • $C$: Delivery capacity (max T-states produced per time step).
  • $B$: Buffer capacity (max T-states stored in advance).
  • $D_\sigma(t)$: T-gate demand at time step $t$ for a schedule $\sigma$.
• Stall Mechanism: If cumulative demand $A_\sigma(t)$ exceeds cumulative supply $S(t) = Ct + B$, the execution stalls until the backlog is cleared.
• Atomic Step Assumption: T gates scheduled in a single logical step must be executed together; if demand $D_\sigma(t) > B + C$, the schedule is deemed infeasible.

B. Key Metrics Introduced

1. Slack Ratio (Structural Indicator):
   • Defined as the fraction of T gates with positive "slack" (the difference between the latest possible start time, ALAP, and earliest start time, ASAP).
   • Purpose: Measures the circuit's inherent structural flexibility to redistribute T-gate demand over time without violating dependencies.
2. $\Delta_{max}$ (Schedule-Level Indicator):
   • Defined as the maximum cumulative gap between demand and production capacity: $\Delta_{max} = \max_t (A_\sigma(t) - Ct)$.
   • Purpose: Quantifies the peak delivery pressure (backlog) induced by a specific schedule.
3. Provable Lower Bound:
   • The paper derives a theoretical lower bound for the executable makespan ($T_{exe}$):
     $$T_{exe} \ge T_{static} + \left\lceil \frac{\max(0, \Delta_{max} - B)}{C} \right\rceil$$
   • This bound represents the minimum additional time required to clear the backlog that cannot be absorbed by the buffer.

C. Experimental Setup

• Datasets:
  • Constructed DAGs: Three families (High, Medium, Low compressibility) with varying dependency densities to control structural flexibility.
  • Real Traces: Ripple-carry adders, integer multipliers, and exact Quantum Fourier Transform (QFT) circuits.
• Scheduling Policies:
  • $\sigma_{static}$: Greedy depth-minimization (ignores delivery).
  • $\sigma_{ca}$: Capacity-aware (respects per-layer quota $C$).
  • $\sigma_{smooth}$: Slack-based reshaping (spreads demand using structural slack).
• Evaluation: 4,904 finite executable instances analyzed for stall classification, slowdown regression, and T-depth inversion (where a shallower circuit runs slower).

3. Key Contributions

1. Demonstration of T-Depth Inversion: The paper provides empirical evidence that minimizing static T-depth can lead to worse execution performance under bounded supply. In high-compressibility circuits, 35.7% of configurations showed "T-depth inversion" (shallower static schedule $\to$ longer executable time).
2. Identification of Superior Predictors:
   • Slack Ratio is a statistically stronger structural predictor than T-depth for identifying stall risk and inversion potential.
   • $\Delta_{max}$ is the strongest schedule-level predictor for execution slowdown and stalls.
3. Provable Lower Bound: A mathematically derived lower bound on executable makespan that holds with zero violations across 4,904 tested instances.
4. Algorithmic Insight: The study shows that approximate QFT decomposition can reduce delivery pressure (lowering $\Delta_{max}$ and slowdown) even if it does not reduce the ideal circuit depth, by lowering peak concurrency.

4. Results

• Predictive Power:
  • For Stall Classification, Slack Ratio outperforms T-depth (AUC 0.975 vs. 0.967).
  • For Slowdown Regression, adding $\Delta_{max}$ to a model explains 86.5% of the variance ($R^2 = 0.865$), whereas T-depth alone explains only 12%.
  • Slack ratio adds marginal but significant structural insight over T-depth alone.
• Lower Bound Validation:
  • Across all 4,904 instances, the predicted lower bound was never violated.
  • 88.9% of instances fell within one cycle of the lower bound.
  • The bound is tightest when the backlog is cleared quickly; gaps increase when backlog persists across multiple steps.
• Real Workload Analysis:
  • Arithmetic Circuits (Adders/Multipliers): Exhibit low slack ratios (~0.35) and low delivery pressure. They are robust to supply constraints.
  • Exact QFT: Exhibits high slack ratio (~0.63) but massive delivery pressure ($\Delta_{max} \approx 43,000$), leading to significant slowdowns.
  • Approximation: Reducing QFT precision lowered $\Delta_{max}$ by ~45% and reduced slowdown severity, despite identical DAG depth.

5. Significance and Implications

• Compiler Design: Current compilers (e.g., Qiskit, tket) optimize for static depth. This paper argues that for FTQC, compilers must treat delivery capacity as an explicit scheduling constraint. Optimizing solely for T-depth is insufficient and potentially harmful.
• Two-Stage Optimization:
  • Use Slack Ratio as a pre-scheduling metric to identify circuits where delivery-aware optimization is critical.
  • Use $\Delta_{max}$ as a post-scheduling metric to evaluate and compare candidate schedules.
• Reliability: Execution stalls increase the time logical qubits spend in error correction, increasing the total space-time volume and the probability of logical failure. Minimizing $\Delta_{max}$ is thus a reliability imperative, not just a performance one.
• Future Directions: The framework suggests that future work should focus on "slack-based reshaping" heuristics and integrating these metrics into compiler passes to prevent T-depth inversion and minimize backlog-induced delays.

In summary, the paper establishes that temporal demand-supply imbalance is the primary driver of execution slowdown in FTQC, not static circuit depth. It provides the theoretical tools (Slack Ratio, $\Delta_{max}$, and a lower bound) to predict and mitigate this issue, fundamentally shifting the paradigm for fault-tolerant quantum compilation.