Sparse quantum state preparation with improved Toffoli cost

Technisches Resümee: Sparse Quantenzustandspräparation mit verbesserter Toffoli-Kosten

Problemstellung
Die Präparation von Quantenzuständen ist ein fundamentales Primitiv im Quantencomputing, das für Anwendungen reicht von linearen Systemlösern über Quanten-Maschinelles Lernen bis hin zur Quantensimulation. Während die generische Zustandspräparation intensiv untersucht wurde, erfordern sparse Quantenzustände (sparse quantum states)—Zustände auf $n$ Qubits, die nur $s \ll 2^n$ Nicht-Null-Basiszustände enthalten—spezialisierte, effiziente Algorithmen.

In der fehlertoleranten Quantenberechnung ist die primäre Ressourcenmetrik oft die Anzahl der Toffoli-Gatter (und T-Gatter), da diese nicht-Clifford-Operationen aufgrund des Overheads der Magic-State-Distillation deutlich kostspieliger in der Implementierung sind als Clifford-Gatter. Bestehende Ansätze zur Präparation von sparse Quantenzuständen fallen im Allgemeinen in zwei Kategorien:

1. Iterative Konstruktion: Aufbau des Zustands in $s$ Schritten, wobei jeweils ein einzelner Basiszustand präpariert wird. Dies verursacht typischerweise eine Toffoli-Kosten von über $s \lceil \log(s) \rceil$.
2. Zweistufiger Ansatz (Dense Präparation + Isometrie): Zuerst Präparation eines dichten Zustands auf einem $\lceil \log(s) \rceil$-Qubit-Subregister, dann Abbildung auf den Ziel-sparse-Zustand mittels einer Isometrie. Die Methode der vorangegangenen Arbeiten, wie etwa die von Malvetti et al., erfordert eine Worst-Case-Toffoli-Kosten von $s(\lceil \log(s) \rceil - 1)$ für die Isometrie, was die Gesamtkosten des Algorithmus dominiert.

Methodik
Die Autoren schlagen ein verfeinertes zweistufiges Framework vor (illustriert in Abbildung 1), das den Isometrie-Schritt optimiert und mit der dichten Zustandspräparation integriert:

1. Gebündelte Isometrie-Konstruktion (Batched Isometry Construction):
   Die zentrale Innovation ist ein neuer klassischer Algorithmus zur Konstruktion des Isometrie-Schaltkreises. Anstatt einzelne mehrfach-gesteuerte-X-Gatter anzuwenden, um die Nicht-Subraum-Qubits für jeden der $s$ Zustände zu nullen (wie bei Malvetti et al.), gruppieren die Autoren die Zustände in Batches der Größe $m$, wobei $m$ die größte Zweierpotenz ist, die in das verfügbare Nicht-Subraum-Register passt ($m \le n - \lceil \log(s) \rceil$).

   • Für jeden Batch transformiert der Algorithmus die Zustände in eine Form, in der das Nicht-Subraum-Register ein einzelnes $|1\rangle$ an distinkten Positionen enthält (z. B. $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$).
   • Ein Partial Unary Iteration (PUI) Schaltkreis wird dann angewendet, um die Nicht-Subraum-Register für den gesamten Batch simultan zu nullen.

2. Partial Unary Iteration (PUI) Schaltkreise:
   Die Autoren führen zwei Varianten von PUI-Schaltkreisen ein, die über ein spezifisches Intervall $[l, r]$ eines Adressregisters iterieren, anstatt über den vollen Raum:

   • Restricted PUI: Garantiert, dass Unitaris nur auf Zustände innerhalb des Zielintervalls $[l, r]$ angewendet werden.
   • Unrestricted PUI: Erlaubt es dem Schaltkreis, nicht-triviale Unitaris auf Zustände mit Adresswerten größer als $r$ anzuwenden. Diese Lockerung reduziert die Toffoli-Anzahl signifikant. Die „unerwünschten“ Effekte auf höhere Adresswerte werden klassisch nachverfolgt und in nachfolgenden Schritten oder Batches korrigiert.

3. Gemeinsame Optimierung mit dichter Zustandspräparation:
   Die Autoren analysieren den Trade-off zwischen den Isometrie-Kosten und den Kosten der dichten Zustandspräparation. Sie schlagen vor, bestimmte Teilaufgaben aus der dichten Präparation an den Isometrie-Schaltkreis auszulagern („outsourcing“):

   • Sign Fixes: Anstatt das Winkel-Register nach der dichten Präparation zu uncomputen (was zusätzliche Toffolis zur Sign-Korrektur erfordert), wird die Sign-Information direkt in die Isometrie mittels Restricted PUIs kodiert.
   • Reelle Zustände: Für Zielzustände mit rein reellen Koeffizienten wird der Phase-Encoding-Schritt der dichten Präparation vollständig entfernt und innerhalb der Isometrie gehandhabt, was die Toffoli-Kosten der dichten Präparation potenziell um den Faktor bis zu drei reduziert.

Wesentliche Beiträge

• Verbesserter Isometrie-Algorithmus: Ein neuer klassischer Algorithmus (Algorithmus 1), der Isometrie-Schaltkreise mit einer Worst-Case-Toffoli-Kosten konstruiert, die durch Folgendes begrenzt sind:
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  wobei $\tilde{s} = 2^{\lceil \log(s) \rceil}$. Dies stellt eine Verbesserung um etwa $\log(s)/2$ gegenüber der State-of-the-Art-Methode von Malvivi et al. dar.
• PUI-Varianten: Die Definition und Kostenanalyse von restricted und unrestricted Partial Unary Iteration Schaltkreisen. Die Unrestricted-Version erreicht niedrigere Toffoli-Zahlen, indem sie „Leakage“ von Operationen zu höheren Adresswerten zulässt, was im Kontext der gebündelten Isometrie-Konstruktion handhabbar ist.
• Ressourcen-Trade-off-Analyse: Eine umfassende Analyse (Tabelle 1) der kombinierten Toffoli- und Qubit-Kosten für die sparse Zustandspräparation, die zeigt, wie die Optimierung der Isometrie eine bessere Nutzung von Ancilla-Qubits zur Reduktion der dichten Präparationskosten ermöglicht, insbesondere für reelle Zustände.
• Implementierung: Die Schaltkreise sind im Qualtran-Framework implementiert, wobei der klassische Isometrie-Findungsalgorithmus unter Verwendung von SIMD-beschleunigtem Rust-Code optimiert wurde.

Ergebnisse

• Theoretische Schranken: Die Worst-Case-Toffoli-Kosten für die Isometrie werden von $O(s \log s)$ auf etwa $O(s)$ für ausreichend große $n$ reduziert. Speziell nähern sich die Kosten in numerischen Benchmarks auf Zufallszuständen dem Wert $s$ an, verglichen mit dem bisherigen Bestwert von etwa $s \log s$.
• Numerische Benchmarks:
  • Für zufällige $s$-sparse Zustände nähert sich die Anzahl der Toffolis pro $s$ dem Wert 1 an, wenn $n$ steigt (Abbildung 2, rechts).
  • Für rein reelle Zustände reduziert die gemeinsame Optimierung die Gesamtzahl der Toffolis signifikant im Vergleich zu generischen komplexen Zuständen (Abbildung 9).
  • Der klassische Algorithmus läuft effizient und findet Isometrien für $s=10^7$ Zustände in etwa 10–20 Minuten auf Standard-CPU-Hardware.
• Vergleich: Die vorgeschlagene Methode übertrifft die bestehende Literatur (z. B. [4, 14, 20, 21]) hinsichtlich der Toffoli-Anzahl, während sie vergleichbare oder geringere Qubit-Overheads beibehält.

Bedeutung und Ansprüche
Das Paper beansprucht, die effizientesten Sparse-Zustandspräparations-Schaltkreise in der Literatur in Bezug auf Toffoli- und Qubit-Anzahlen zu präsentieren. Die Bedeutung liegt in:

1. Beseitigung des Flaschenhalses: Durch die Reduktion der Isometrie-Kosten von dem dominierenden Faktor auf ein Niveau, das mit der dichten Präparation vergleichbar ist, wird der Gesamtalgorithmus effizienter.
2. Skalierbarkeit: Der Ansatz skaliert günstig mit der Anzahl der Qubits $n$, was ihn für groß angelegte fehlertolerante Quantenalgorithmen geeignet macht, bei denen $s$ groß, aber $s \ll 2^n$ ist.
3. Praktikabilität: Die Methode ist kompatibel mit bestehenden Frameworks zur Ressourcenabschätzung für das fehlertolerante Computing (Fokus auf Toffoli-Zahlen) und ist modular in einem Software-Framework (Qualtran) implementiert.

Die Autoren bleiben bescheiden hinsichtlich zukünftiger Implikationen und merken an, dass, obwohl die Toffoli-Anzahl die aktuelle Standardmetrik ist, Fortschritte in der Magic-State-Generierung (Kultivierung/Distillation) den Fokus in Zukunft auf Laufzeitmetriken verschieben könnten. Sie lassen zudem die Frage offen, ob sublineare Toffoli-Kosten in $s$ mit begrenzten Ancilla-Ressourcen erreichbar sind.