The power of constant-depth quantum circuits of unbounded size

Technische Samenvatting: De Kracht van Quantumcircuits met Constante Diepte en Onbegrensde Omvang

Probleemstelling
Het artikel onderzoekt de computationele kracht van quantumcircuits wanneer beperkingen op de circuitgrootte en het aantal ancilla-qubits worden opgeheven. In de klassieke complexiteitstheorie kan de klasse $AC^0$ (circuits met constante diepte en onbeperkte fan-in AND/OR-poorten) geen pariteit berekenen. Echter, als de beperking op polynomiale grootte wordt opgeheven, kan elke Booleaanse functie in constante diepte worden berekend via Disjunctieve Normaalvorm (DNF) constructies. De auteurs vragen zich af of een vergelijkbaar fenomeen geldt voor quantumcircuits opgebouwd uit willekeurige single-qubit gates en gegeneraliseerde Toffoli-gates (onbegrensde omvang $QAC^0$). Specifiek: kan elke unitaire operatie exact worden geïmplementeerd in constante diepte als de circuitgrootte en het aantal ancilla-qubits onbeperkt zijn?

De auteurs kaderen deze vraagstelling via vier steeds algemenere taken:

1. Het berekenen van lidmaatschap in een willekeurige verzameling $L \subseteq \{0, 1\}^n$.
2. Het implementeren van elke permutatie van computationele basis toestanden.
3. Het voorbereiden van een willekeurige zuivere quantumtoestand.
4. Het implementeren van een willekeurige unitaire operatie op elke inputtoestand.

Methodologie
De auteurs maken gebruik van een combinatie van reversibele klassieke circuitconstructies, probabilistische klassieke technieken aangepast aan het quantumdomein, en quantumteleportatieprotocollen.

• Reversibele Klassieke Constructies: De auteurs stellen eerst vast dat willekeurige permutaties van bitstrings in constante diepte kunnen worden geïmplementeerd met behulp van Toffoli- en fanout-gates. Dit wordt bereikt via een "indicator-codering"-schema: de input wordt gemapt naar een $2^n$-dimensionale indicatorvector (waarbij precies één entry 1 is), gemanipuleerd, en vervolgens terug-gecodeerd naar de oorspronkelijke string. Dit maakt de parallelle evaluatie van alle mogelijke inputstrings mogelijk.
• Probabilistische naar Quantum Adaptatie: Om willekeurige kansverdelingen en zuivere quantumtoestanden voor te bereiden, passen de auteurs een klassieke probabilistische constructie aan. Dit houdt in dat bits onafhankelijk worden gesampled om een distributie te coderen op basis van de positie van de eerste '1'. In de quantumsetting wordt dit coherent gemaakt door inverse rotaties toe te passen op qubits volgend op de eerste '1' om ze terug te brengen naar $|0\rangle$ zonder de superpositie te vernietigen.
• Gate Set Extensies: Hoewel de primaire gate set single-qubit gates en gegeneraliseerde Toffoli-gates bevat, gebruiken de auteurs fanout-gates als een conceptueel instrument. Zij citeren resultaten van Grier, Morris en Wu [GMW26] en Rosenthal [Ros20] om aan te tonen dat fanout exact in constante diepte kan worden geïmplementeerd met enkel de primaire gate set, zij het met een potentiële toename van de circuitgrootte naar dubbel exponentiële grenzen.
• Reducties voor Unitaire Operaties: Voor de implementatie van willekeurige unitaire operaties bieden de auteurs geen directe constructie. In plaats daarvan bieden zij verschillende equivalente formuleringen en reducties aan. Deze omvatten het reduceren van unitaire implementatie naar:
  • Het klonen van vectoren van een gespecificeerde orthonormale basis.
  • Het permuteren van lijsten van basisvectoren.
  • Het decoderen van basislabels.
  • Het implementeren van unitaire operaties met eenheid rij- en kolomsommen (via de Idel-Wolf normale vorm).
  • Het implementeren van traceless unitaire involuties (met gebruik van één extra cleane qubit).
• Port-Based Teleportation (PBT): Om de implementatie van willekeurige unitaire operaties te benaderen zonder unitaire correcties die afhankelijk zijn van de specifieke gate, maken de auteurs gebruik van Port-Based Teleportation (PBT). Zij construeren een unitaire circuit dat PBT uitvoert met behulp van maximaal verstrengelde toestanden (of Choi-toestanden van de doel-unitaire operatie) en een gezamenlijke meting, gevolgd door poortselectie.

Belangrijkste Bijdragen en Resultaten

1. Exacte Constante-Diepte Constructies voor Specifieke Taken:

   • Permutaties: Willekeurige permutaties van computationele basis toestanden kunnen in constante diepte (diepte $\le 20$) worden geïmplementeerd met $O(n2^n)$ gates en ancilla-qubits.
   • Diagonale Unitaire Operaties: Willekeurige diagonale unitaire operaties kunnen in constante diepte (diepte 7) worden geïmplementeerd door indicatoren te berekenen, fasen parallel toe te passen en te uncomputen.
   • Toestandvoorbereiding: Willekeurige zuivere quantumtoestanden kunnen in constante diepte (diepte $\le 37$) worden voorbereid met $O(4^n)$ qubits en $O(n2^n)$ gates. Alle ancilla-qubits worden teruggebracht naar nul.
   • Fanout Implementatie: Fanout kan exact in constante diepte worden geïmplementeerd met enkel single-qubit en gegeneraliseerde Toffoli-gates, hoewel dit mogelijk dubbel exponentiële grootte vereist.

2. Reducties voor Willekeurige Unitaire Operaties:
   Het artikel toont aan dat het implementeren van willekeurige unitaire operaties in constante diepte equivalent is aan het implementeren van diverse specifieke operaties (bijv. het klonen van basisvectoren, het decoderen van labels, of het implementeren van traceless involuties). Dit herkadert het openstaande probleem van willekeurige unitaire implementatie tot een reeks equivalente structurele uitdagingen.

3. Adaptieve Metingen en Gate Teleportatie:
   De auteurs tonen aan dat indien adaptieve tussenliggende metingen zijn toegestaan, elke gate op niveau $\ell$ van de Clifford-hiërarchie kan worden geïmplementeerd met diepte $O(\ell)$. Bovendien reduceert de implementatie van willekeurige unitaire operaties tot het implementeren van traceless unitaire involuties in dit adaptieve model.

4. Port-Based Teleportation Approximatie:
   De auteurs construeren een unair circuit voor Port-Based Teleportation (PBT) voor een inputdimensie $d$ en $M \ge d^2 - 1$ poorten.

   • Diepte: Het circuit heeft een diepte van $O(\sqrt{d})$, wat onafhankelijk is van het aantal poorten $M$.
   • Fidelity: De entanglement fidelity is begrensd door $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • Nauwkeurigheid vs. Diepte: Voor een vaste inputdimensie $d$ kan de benadering willekeurig nauwkeurig worden gemaakt door $M$ te vergroten zonder de circuitdiepte te verhogen. De afhankelijkheid van de inputdimensie $d$ blijft echter bestaan; of een dieptegrens onafhankelijk van $d$ kan worden bereikt, blijft een open vraag.
   • Implementatie: Het circuit gebruikt enkel single-qubit en gegeneraliseerde Toffoli-gates en vereist geen tussenliggende metingen.

Betekenis en Claims
Dit artikel stelt vast dat het opheffen van restricties op grootte en ancilla-ruimte constante-diepte quantumcircuits in staat stelt om taken uit te voeren die over het algemeen onmogelijk zijn in polynomiale grootte constante-diepte modellen, zoals willekeurige toestandvoorbereiding en de permutatie van basis toestanden. Dit verbindt quantum toestandvoorbereiding direct met reversibele klassieke berekening en de voorbereiding van kansverdelingen.

Het artikel neemt echter een bescheiden standpunt in met betrekking tot de implementatie van willekeurige unitaire operaties. Hoewel het exacte constante-diepte constructies biedt voor permutaties, diagonale unitaire operaties en toestandvoorbereiding, blijft de implementatie van algemene unitaire operaties een open probleem. De auteurs bieden equivalente karakterisaties van dit probleem, maar lossen het niet op.

De primaire bijdrage met betrekking tot algemene unitaire operaties is de PBT-constructie. De auteurs demonstreren dat voor elke vaste inputdimensie, willekeurige unitaire operaties benaderd kunnen worden met willekeurige precisie zonder de circuitdiepte te verhogen door het aantal poorten te vergroten. Echter, de diepte van deze constructie schaalt als $O(\sqrt{d})$ met de inputdimensie $d$. De auteurs geven expliciet aan dat of deze afhankelijkheid van $d$ kan worden verwijderd (hetzij het bereiken van een dieptegrens onafhankelijk van $d$) een open vraag blijft. Het werk benadrukt dat de fundamentele moeilijkheid bij constante-diepte unitaire implementatie niet ligt in het produceren van een willekeurige output vanuit een vaste input, maar in het voorschrijven van de actie op elke inputtoestand tegelijkertijd, terwijl de unitariteit behouden blijft.