Sparse quantum state preparation with improved Toffoli cost

Technische Samenvatting: Spaarse Kwantumtoestandsvoorbereiding met Verbeterde Toffoli-kosten

Probleemstelling
De voorbereiding van kwantumtoestanden is een fundamentele primitief in quantum computing, essentieel voor toepassingen variërend van lineaire systeemoplossers en quantum machine learning tot quantumsimulatie. Terwijl generieke toestandsvoorbereiding uitgebreid is bestudeerd, vereisen sparse kwantumtoestanden—toestanden op $n$ qubits die slechts $s \ll 2^n$ niet-nul computationele basistoestanden bevatten—gespecialiseerde, efficiënte algoritmen.

In fouttolerante quantum computing is de primaire hulpbronmetriek vaak het aantal Toffoli-gates (en T-gates), aangezien deze niet-Clifford operaties aanzienlijk kostbaarder zijn om te implementeren dan Clifford-gates vanwege de overhead van magic-state distillatie. Bestaande benaderingen voor sparse toestandsvoorbereiding vallen over het algemeen uiteen in twee categorieën:

1. Iteratieve constructie: Het opbouwen van de toestands in $s$ stappen, waarbij telkens één basistoestand wordt voorbereid. Dit brengt doorgaans een Toffoli-kost met zich mee die groter is dan $s \lceil \log(s) \rceil$.
2. Twee-staps aanpak (Dense Voorbereiding + Isometrie): Eerst een dense toestandsvoorbereiding op een $\lceil \log(s) \rceil$-qubit sub-register, gevolgd door het mappen naar de doelgerichte sparse toestands via een isometrie. De methodiek van eerdere literatuur, zoals de methode van Malvetti et al., vereist een worst-case Toffoli-kost van $s(\lceil \log(s) \rceil - 1)$ voor de isometrie, wat de totale algoritmische kosten domineert.

Methodologie
De auteurs stellen een verfijnd twee-staps framework voor (geïllustreerd in Figuur 1) dat de isometrie-stap optimaliseert en integreert met dense toestandsvoorbereiding:

1. Gebatchte Isometrie Constructie:
   De kerninnovatie is een nieuw klassiek algoritme voor het construeren van de isometrie-circuit. In plaats van individuele multi-controlled-X gates toe te passen om niet-subspace qubits voor elke van de $s$ toestanden op nul te zetten (zoals gedaan door Malvetti et al.), groeperen de auteurs toestanden in batches van grootte $m$, waarbij $m$ de grootste macht van twee is die in het beschikbare niet-subspace register past ($m \le n - \lceil \log(s) \rceil$).

   • Voor elke batch transformeert het algoritme de toestanden naar een vorm waarin het niet-subspace register een enkele $|1\rangle$ op verschillende posities bevat (bijv. $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$).
   • Een Partial Unary Iteration (PUI) circuit wordt vervolgens toegepast om de niet-subspace registers voor de gehele batch gelijktijdig op nul te zetten.

2. Partial Unary Iteration (PUI) Circuits:
   De auteurs introduceren twee varianten van PUI-circuits, die itereren over een specifiek interval $[l, r]$ van een adresregister in plaats van de volledige ruimte:

   • Restricted PUI: Garandeert dat unitair-operaties alleen worden toegepast op toestanden binnen het doelinterval $[l, r]$.
   • Unrestricted PUI: Staat toe dat het circuit niet-triviale unitair-operaties toepast op toestanden met adreswaarden groter dan $r$. Deze versoepeling vermindert het aantal Toffoli-gates aanzienlijk. De "ongewenste" effecten op hogere adreswaarden worden klassiek bijgehouden en gecorrigeerd in opeenvolgende stappen of batches.

3. Gezamenlijke Optimalisatie met Dense Toestandsvoorbereiding:
   De auteurs analyseren de afruil tussen de isometrie-kosten en de dense toestandsvoorbereidingskosten. Ze stellen voor om bepaalde sub-taken van de dense voorbereiding naar de isometrie-circuit te "outsourcen":

   • Sign Fixes: In plaats van het hoekregister na de dense voorbereiding te de-computeren (wat extra Toffolis vereist voor tekencorrectie), wordt de tekeninformatie direct in de isometrie gecodeerd met behulp van restricted PUIs.
   • Real States: Voor doeltoestanden met zuiver reële coëfficiënten wordt de fase-codering stap van de dense voorbereiding volledig verwijderd en afgehandeld binnen de isometrie, wat potentieel de dense voorbereidings-Toffoli-kosten met een factor tot wel drie vermindert.

Belangrijkste Bijdragen

• Verbeterd Isometrie Algoritme: Een nieuw klassiek algoritme (Algoritme 1) dat isometrie-circuits construeert met een worst-case Toffoli-kost begrensd door:
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  waarbij $\tilde{s} = 2^{\lceil \log(s) \rceil}$. Dit vertegenwoordigt een verbetering van ongeveer $\log(s)/2$ ten opzichte van de state-of-the-art methode van Malvetti et al.
• PUI Varianten: De definitie en kostenanalyse van restricted en unrestricted partial unary iteration circuits. De unrestricted versie bereikt lagere Toffoli-aantallen door "lekken" van operaties naar hogere adreswaarden toe te staan, wat beheersbaar is in de context van de gebatchte isometrie-constructie.
• Resource Afruil Analyse: Een uitgebreide analyse (Tabel 1) van de gecombineerde Toffoli- en qubit-kosten voor sparse toestandsvoorbereiding, die aantoont hoe het optimaliseren van de isometrie een betere benutting van ancilla-qubits mogelijk maakt om de dense voorbereidingskosten te verlagen, met name voor reële toestanden.
• Implementatie: De circuits zijn geïmplementeerd in het Qualtran framework, waarbij het klassieke isometrie-zoekalgoritme is geoptimaliseerd met SIMD-versnelde Rust-code.

Resultaten

• Theoretische Grenzen: De worst-case Toffoli-kost voor de isometrie is gereduceerd van $O(s \log s)$ naar ongeveer $O(s)$ voor voldoende grote $n$. Specifiek nadert de kost $s$ in numerieke benchmarks op willekeurige toestanden, vergeleken met de vorige beste van ongeveer $s \log s$.
• Numerieke Benchmarks:
  • Voor willekeurige $s$-sparse toestanden nadert het aantal Toffolis per $s$ de waarde 1 naarmate $n$ toeneemt (Figuur 2, rechts).
  • Voor zuiver reële toestanden vermindert de gezamenlijke optimalisatie het totale Toffoli-aantal aanzienlijk vergeleken met generieke complexe toestanden (Figuur 9).
  • Het klassieke algoritme draait efficiënt en vindt isometrieën voor $s=10^7$ toestanden in ongeveer 10–20 minuten op standaard CPU-hardware.
• Vergelijking: De voorgestelde methode presteert beter dan bestaande literatuur (bijv. [4, 14, 20, 21]) wat betreft Toffoli-aantal, terwijl zij een vergelijkbaar of lager qubit-overhead behoudt.

Betekenis en Claims
Het artikel claimt de meest efficiënte sparse toestandsvoorbereidingscircuits in de literatuur te presenteren in termen van Toffoli- en qubit-aantallen. De significantie ligt in:

1. Verwijdering van de Bottleneck: Door de isometrie-kost te reduceren van de dominante factor naar een niveau dat vergelijkbaar is met de dense voorbereiding, wordt het totale algoritme efficiënter.
2. Schaalbaarheid: De aanpak schaalt gunstig met het aantal qubits $n$, waardoor het geschikt is voor grootschalige fouttolerante kwantumalgoritmen waar $s$ groot is maar $s \ll 2^n$.
3. Praktische Bruikbaarheid: De methode is compatibel met bestaande fouttolerante resource-estimatie frameworks (gericht op Toffoli-aantallen) en is geïmplementeerd in een modulair softwareframework (Qualtran).

De auteurs blijven bescheiden over toekomstige implicaties, waarbij zij opmerken dat hoewel het Toffoli-aantal de huidige standaardmetriek is, vooruitgang in magic-state generatie (cultivatie/distillatie) de focus in de toekomst naar runtime-metrieken kan verschuiven. Zij laten ook de vraag open of sub-lineaire Toffoli-kosten in $s$ haalbaar zijn met beperkte ancilla-resources.