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

Titel

Wanneer T-Depth Misleidt: Het Voorspellen van Vertraging in Fouttolerante Quantum-uitvoering onder Beperkte Magic-State Levering

1. Het Probleem

In fouttolerante quantumcomputing (FTQC) zijn niet-Clifford-operaties (zoals T-gates) afhankelijk van "magic states" die via distillatie moeten worden geproduceerd. Traditionele compilatie- en optimalisatiestrategieën focussen zich op het minimaliseren van de T-depth (het aantal sequentiële lagen van T-gates), onder de aanname dat er een onbeperkte voorraad magic states beschikbaar is.

Het paper identificeert een fundamenteel probleem:

• Mismatch tussen statische diepte en uitvoeringstijd: Een circuit met een lage T-depth kan slechter presteren dan een circuit met een hogere T-depth als de levering van magic states beperkt is door de productiecapaciteit van de "magic-state factories".
• Vraag-Aanbod Disbalans: Een optimalisatie die de T-depth minimaliseert, kan leiden tot een concentratie van T-gate-vereisten in korte tijdsintervallen (bursts). Als deze vraag de leveringscapaciteit ($C$) en buffercapaciteit ($B$) overschrijdt, moet de uitvoering stilstaan (stall).
• Gevolgen: Deze stilstanden zijn niet alleen tijdsverlies; ze vereisen dat logische qubits langer actief foutgecorrigeerd blijven, wat de ruimte-tijd-volume vergroot en de betrouwbaarheid verlaagt.
• T-depth Inversie: Er kan een situatie ontstaan waarbij een schema met een kortere statische T-depth een langere werkelijke uitvoeringstijd ($T_{exe}$) heeft dan een schema met een langere statische diepte, puur vanwege leveringsbeperkingen.

2. Methodologie

De auteurs introduceren een uitvoeringsmodel dat de beperkte levering van magic states expliciet meeneemt.

• Het Model:

  • Het circuit wordt gemodelleerd als een Directed Acyclic Graph (DAG).
  • Vraag ($D_\sigma(t)$): Het aantal T-gates op tijdstap $t$.
  • Aanbod: Beperkt door een productiecapaciteit $C$ (T-states per stap) en een buffer $B$.
  • Cumulatieve Vraag vs. Aanbod: De uitvoering stopt als de cumulatieve vraag $A_\sigma(t)$ de cumulatieve beschikbare voorraad $Ct + B$ overschrijdt. Dit creëert een "backlog".

• Nieuwe Metrieken:

  1. Slack Ratio (Structureel): Een maat voor de flexibiliteit van het circuit. Het is het aandeel van T-gates dat een positieve "slack" heeft (het verschil tussen de vroegst mogelijke starttijd [ASAP] en de laatst mogelijke starttijd [ALAP]). Een hoge slack ratio betekent dat T-gates makkelijker over de tijd kunnen worden verspreid zonder de totale diepte te vergroten.
  2. $\Delta_{max}$ (Schema-niveau): De maximale cumulatieve vraag-supply gap onder een specifiek schema. Het meet de grootste verticale afstand tussen de cumulatieve vraag en de productiecapaciteitslijn.

• Ondersteboven Bound (Lower Bound):
  De auteurs leiden een wiskundige ondergrens af voor de uitvoeringstijd:
  $$T_{exe} \ge T_{static} + \lceil \frac{\max(0, \Delta_{max} - B)}{C} \rceil$$
  Dit betekent dat de extra vertraging direct gerelateerd is aan de backlog die niet door de buffer kan worden opgevangen.

• Experimenteel Opzet:

  • Datasets: Geconstrueerde DAG-families (hoge, gemiddelde en lage compressibiliteit) en echte quantum-circuits (Adder, Multiplier, Exacte QFT).
  • Scheduling Policy's: Vergelijking tussen een diepte-georiënteerde referentie ($\sigma_{static}$), een capaciteitsbewuste baseline ($\sigma_{ca}$), en een slack-gebaseerde herschikking ($\sigma_{smooth}$).
  • Validatie: Analyse van 4.904 eindige uitvoeringsinstanties.

3. Belangrijkste Bijdragen

1. Demonstratie van T-depth Misleiding: Het paper bewijst empirisch dat T-depth alleen een onbetrouwbare voorspeller is voor de uitvoeringstijd onder beperkte levering. Het fenomeen van "T-depth inversie" (waarbij een schijnbaar sneller schema trager is) wordt kwantitatief aangetoond.
2. Introductie van Voorspellende Metrieken:
   • Slack Ratio: Blijkt statistisch een sterkere structurele voorspeller te zijn dan T-depth voor het risico op stilstand en inversie.
   • $\Delta_{max}$: Wordt geïdentificeerd als de sterkste voorspeller op schema-niveau voor uitvoeringsvertraging en stilstand.
3. Wiskundig Onderbouwd: De auteurs leveren een bewezen ondergrens voor de uitvoeringstijd die in geen van de 4.904 geteste gevallen is geschonden.
4. Openbare Framework: Het evaluatieframework, de gegenereerde datasets en analyse-scripts zijn openbaar gemaakt (GitHub: BARC).

4. Resultaten

• Voorspellende Kracht:
  • $\Delta_{max}$ is de dominante factor. Een lineair model dat alleen T-depth gebruikt verklaart slechts 12% van de variantie in vertraging ($R^2 = 0.12$). Door $\Delta_{max}$ toe te voegen, stijgt dit naar 86,5% ($R^2 = 0.865$).
  • De Slack Ratio is een betere indicator dan T-depth voor het voorspellen van stilstanden, vooral in circuits met hoge flexibiliteit (hoge compressibiliteit).
• Validatie van de Ondergrens:
  • Van de 4.904 geteste instanties schond geen enkele de berekende ondergrens.
  • 88,9% van de instanties lag binnen 1 cyclus van de ondergrens.
  • De ondergrens is het nauwkeurigst wanneer de backlog kort is; bij langdurige backlogs over meerdere stappen wordt de voorspelling iets ruimer, maar blijft geldig.
• Echte Workloads:
  • Rekenkundige circuits (Adder/Multiplier): Hebben een lage slack ratio en vertonen weinig vertraging, tenzij de levering extreem beperkt is.
  • QFT (Quantum Fourier Transform): Heeft een hoge slack ratio maar genereert enorme leveringsdruk ($\Delta_{max}$), wat leidt tot significante vertragingen.
  • Approximatie: Het gebruik van benaderde QFT-decompositie (zonder de diepte te veranderen) kon de leveringsdruk en de ernst van de vertraging aanzienlijk verminderen door piekvragen te verlagen.

5. Betekenis en Implicaties

• Voor Compiler Ontwerp: Compilers voor fouttolerante quantumcomputing mogen niet alleen T-depth minimaliseren. Ze moeten "leveringscapaciteit" als een expliciete beperking in het scheduling-proces opnemen. Het minimaliseren van piekvragen (demand shaping) is belangrijker dan het minimaliseren van de statische diepte.
• Architectuurplanning: De metriek $\Delta_{max}$ kan worden gebruikt om te bepalen hoeveel magic-state factories ($C$) en buffers ($B$) nodig zijn om een bepaald circuit zonder stilstand uit te voeren.
• Betrouwbaarheid: Stilstanden door leveringsproblemen verhogen de tijd dat qubits onder foutcorrectie staan, wat de kans op logische fouten vergroot. Het minimaliseren van $\Delta_{max}$ is dus ook een kwestie van betrouwbaarheid, niet alleen van snelheid.
• Toekomstige Richting: Het paper pleit voor het integreren van deze metrieken in bestaande compilatieflows (zoals Qiskit of tket) en voor het uitbreiden van het model naar stochastische leveringsmodellen en ruimtelijke beperkingen.

Conclusie:
Dit onderzoek verschuift de focus van statische circuit-metrieken naar dynamische vraag-aanbod-balans. Het toont aan dat zonder rekening te houden met de beperkte levering van magic states, schattingen van uitvoeringstijd en betrouwbaarheid fundamenteel onjuist kunnen zijn. De voorgestelde metrieken (Slack Ratio en $\Delta_{max}$) bieden een lichtgewicht, maar krachtig raamwerk voor het voorspellen en mitigeren van deze problemen.