The power of constant-depth quantum circuits of unbounded size

Technische Zusammenfassung: Die Leistungsfähigkeit von Quantenschaltkreisen konstanter Tiefe mit unbeschränkter Größe

Problemstellung
Die vorliegende Arbeit untersucht die Rechenleistung von Quantenschaltkreisen, wenn die Beschränkungen bezüglich der Schaltkreisgröße und des Hilfsraums (ancillary space) aufgehoben werden. In der klassischen Komplexitätstheorie kann die Klasse $AC^0$ (Schaltkreise konstanter Tiefe mit unbeschränktem Fan-in von AND/OR-Gattern) die Parität nicht berechnen. Wenn jedoch die Beschränkung auf polynomielle Größe aufgehoben wird, kann jede boolesche Funktion in konstanter Tiefe mittels der Konstruktion der disjunktiven Normalform (DNF) berechnet werden. Die Autoren fragen, ob ein ähnliches Phänomen für Quantenschaltkreise gilt, die aus beliebigen Qubit-Einzelgattern und generalisierten Toffoli-Gattern aufgebaut sind ($QAC^0$). Konkret: Kann jede unitäre Operation exakt in konstanter Tiefe implementiert werden, wenn die Schaltkreisgröße und die Anzahl der Hilfsqubits unbeschränkt sind?

Die Autoren rahmen diese Untersuchung durch vier zunehmend allgemeinere Aufgaben ein:

1. Berechnung der Zugehörigkeit zu einer beliebigen Menge $L \subseteq \{0, 1\}^n$.
2. Implementierung jeder Permutation der Rechenbasis-Zustände.
3. Präparation eines beliebigen reinen Quantenzustands.
4. Implementierung einer beliebigen unitären Operation auf jedem Eingangszustand.

Methodik
Die Autoren verwenden eine Kombination aus reversiblen klassischen Schaltkreis-Konstruktionen, probabilistischen klassischen Techniken, die an den Quantenbereich angepasst wurden, und Quantenteleportations-Protokollen.

• Reversible klassische Konstruktionen: Die Autoren stellen zunächst fest, dass beliebige Permutationen von Bitstrings in konstanter Tiefe unter Verwendung von Toffoli- und Fanout-Gattern implementiert werden können. Dies wird durch ein „Indikator-Kodierungsschema“ erreicht: Der Input wird auf einen $2^n$-dimensionalen Indikatorvektor abgebildet (bei dem genau ein Eintrag 1 ist), manipuliert und dann zum ursprünglichen String dekodiert. Dies ermöglicht die parallele Auswertung aller möglichen Input-Strings.
• Probabilistische zu Quanten-Adaption: Um beliebige Wahrscheinlichkeitsverteilungen und reine Quantenzustände zu präparieren, passen die Autoren eine klassische probabilistische Konstruktion an. Dies beinhaltet das unabhängige Abtasten von Bits, um eine Verteilung basierend auf der Position der ersten „1“ zu kodieren. Im Quantenkontext wird dies kohärent gestaltet, indem inverse Rotationen auf Qubits angewendet werden, die auf der ersten „1“ folgen, um sie in den Zustand $|0\rangle$ zurückzuführen, ohne die Superposition zu zerstören.
• Erweiterung des Gatestatsets: Während das primäre Gaterset Einzel-Qubit-Gatter und generalisierte Toffoli-Gatter umfasst, nutzen die Autoren Fanout-Gatter als konzeptionelles Werkzeug. Sie zitieren Ergebnisse von Grier, Morris und Wu [GMW26] sowie Rosenthal [Ros20], um zu zeigen, dass Fanout exakt in konstanter Tiefe unter Verwendung des primären Gatysets implementiert werden kann, wenngleich dies zu einer potenziellen Erhöhung der Schaltkreisgröße auf doppelt exponentielle Grenzen führen kann.
• Reduktionen für Unitäre: Für die Implementierung beliebiger unitärer Operationen liefern die Autoren keine direkte Konstruktion. Stattdessen bieten sie mehrere äquivalente Formulierungen und Reduktionen an. Dazu gehört die Reduktion der Implementierung unitärer Operationen auf:
  • Das Klonen von Vektoren einer spezifizierten Orthonormalbasis.
  • Das Permutieren von Listen von Basisvektoren.
  • Das Dekodieren von Basis-Labels.
  • Die Implementierung von unitären Operationen mit Einser-Zeilen- und Spaltensummen (via der Idel-Wolf-Normalform).
  • Die Implementierung von spurlosen unitären Involutionen (unter Verwendung eines zusätzlichen sauberen Qubits).
• Port-Based Teleportation (PBT): Um der Implementierung beliebiger unitärer Operationen ohne von dem spezifischen Gatter abhängige unitäre Korrekturen nahezukommen, nutzen die Autoren Port-Based Teleportation. Sie konstruieren einen unitären Schaltkreis, der PBT unter Verwendung von maximal verschränkten Zuständen (oder Choi-Zuständen der Ziel-Unitären) und einer gemeinsamen Messung sowie Port-Selektion durchführt.

Wesentliche Beiträge und Ergebnisse

1. Exakte Konstruktionen konstanter Tiefe für spezifische Aufgaben:

   • Permutationen: Beliebige Permutationen der Rechenbasis-Zustände können in konstanter Tiefe (Tiefe $\le 20$) unter Verwendung von $O(n2^n)$ Gattern und Hilfsqubits implementiert werden.
   • Diagonale Unitäre: Beliebige diagonale unitäre Operationen können in konstanter Tiefe (Tiefe 7) implementiert werden, indem Indikatoren berechnet, Phasen parallel angewendet und die Operation wieder rückgängig gemacht wird (uncomputing).
   • Zustandspräparation: Beliebige reine Quantenzustände können in konstanter Tiefe (Tiefe $\le 37$) unter Verwendung von $O(4^n)$ Qubits und $O(n2^n)$ Gattern präpariert werden. Alle Hilfsqubits werden in den Zustand Null zurückgeführt.
   • Fanout-Implementierung: Fanout kann exakt in konstanter Tiefe unter Verwendung von nur Einzel-Qubit- und generalisierten Toffoli-Gattern implementiert werden, was jedoch doppelt exponentielle Größen erfordern kann.

2. Reduktionen für beliebige Unitäre:
   Das Paper zeigt, dass die Implementierung beliebiger unitärer Operationen in konstanter Tiefe äquivalent zur Implementierung mehrerer spezifischer Operationen ist (z. B. Klonen von Basisvektoren, Dekodieren von Labels oder Implementierung von spurlosen Involutionen). Dies rahmt das offene Problem der Implementierung beliebiger Unitärer in eine Reihe äquivalenter struktureller Herausforderungen um.

3. Adaptive Messungen und Gate-Teleportation:
   Die Autoren zeigen, dass unter Zulassung adaptiver Zwischenmessungen jedes Gatter der Ebene $\ell$ der Clifford-Hierarchie mit einer Tiefe von $O(\ell)$ implementiert werden kann. Ferner reduziert sich die Implementierung beliebiger unitärer Operationen in diesem adaptiven Modell auf die Implementierung von spurlosen unitären Involutionen.

4. Port-Based Teleportation Approximation:
   Die Autoren konstruieren einen unitären Schaltkreis für Port-Based Teleportation (PBT) für eine Eingangsdimension $d$ und $M \ge d^2 - 1$ Ports.

   • Tiefe: Die Schaltungstiefe beträgt $O(\sqrt{d})$ und ist unabhängig von der Anzahl der Ports $M$.
   • Fidelität: Die Verschränkungsfidelität (entanglement fidelity) ist beschränkt durch $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • Genauigkeit vs. Tiefe: Für jede feste Eingangsdimension $d$ kann die Approximation durch Erhöhung von $M$ beliebig genau gemacht werden, ohne die Schaltungstiefe zu erhöhen. Die Abhängigkeit von der Eingangsdimension $d$ bleibt jedoch bestehen; ob eine Tiefe, die unabhängig von $d$ ist, erreicht werden kann, bleibt eine offene Frage.
   • Implementierung: Der Schaltkreis verwendet nur Einzel-Qubit- und generalisierte Toffoli-Gatter und erfordert keine Zwischenmessungen.

Bedeutung und Behauptungen
Das Paper stellt fest, dass das Aufheben von Größen- und Hilfsraumbeschränkungen es konstanter Tiefe Quantenschaltkreisen ermöglicht, Aufgaben auszuführen, die in polynomiellem Größenmaß in Modellen konstanter Tiefe im Allgemeinen unmöglich sind, wie etwa die beliebige Zustandspräparation oder die Permutation von Basis-Zuständen. Dies verbindet die Quantenzustandspräparation direkt mit der reversiblen klassischen Berechnung und der Präparation von Wahrscheinlichkeitsverteilungen.

Dennoch bewahren die Autoren eine bescheidene Haltung hinsichtlich der Implementierung beliebiger unitärer Operationen. Während sie exakte Konstruktionen konstanter Tiefe für Permutationen, diagonale Unitäre und Zustandspräparation liefern, bleibt die Implementierung allgemeiner Unitärer ein offenes Problem. Die Autoren bieten äquivalente Charakterisierungen dieses Problems an, lösen es jedoch nicht.

Der primäre Beitrag bezüglich allgemeiner Unitärer ist die PBT-Konstruktion. Die Autoren zeigen, dass für jede feste Eingangsdimension beliebige unitäre Operationen mit beliebiger Präzision approximiert werden können, ohne die Schaltungstiefe durch Erhöhung der Anzahl der Ports zu steigern. Dennoch skaliert die Tiefe dieser Konstruktion als $O(\sqrt{d})$ mit der Eingangsdimension $d$. Die Autoren geben explizit an, dass die Frage, ob diese Abhängigkeit von $d$ entfernt werden kann (d. h. das Erreichen einer Tiefenbindung, die unabhängig von $d$ ist), eine offene Frage bleibt. Die Arbeit verdeutlicht, dass die fundamentale Schwierigkeit bei der Implementierung von Unitären in konstanter Tiefe nicht darin liegt, eine beliebige Ausgabe aus einem festen Input zu erzeugen, sondern darin, die Wirkung auf jeden Eingangszustand gleichzeitig vorzuschreiben und dabei die Unitarität zu bewahren.