A mixed-precision quantum-classical algorithm for solving linear systems

Probleemstelling

Het paper adresseert het fundamentele probleem van het oplossen van systemen van lineaire vergelijkingen ($Ax = b$) met behulp van kwantumcomputing. Hoewel algoritmen zoals de Quantum Singular Value Transformation (QSVT) het potentieel hebben om exponentiële snelheidswinst te bieden ten opzichte van klassieke methoden, stuiten ze op ernstige beperkingen:

• Hoge kwantumkosten: Om een acceptabele nauwkeurigheid (bijvoorbeeld beter dan $10^{-5}$) te bereiken, vereist de QSVT een zeer hoge graad van polynoombenadering. Dit leidt tot diepe kwantumcircuits en een enorm aantal benodigde qubits en poorten.
• Beperkte precisie: Directe implementatie van QSVT met hoge precisie is momenteel onhaalbaar vanwege de beperkte middelen van toekomstige Large Scale Quantum (LSQ) architecturen.
• Conditiegetal: De complexiteit van QSVT hangt sterk af van het conditiegetal ($\kappa$) van de matrix; een hoge $\kappa$ vereist nog meer resources.

Methodologie

De auteurs stellen een hybride kwantum-klassiek algoritme voor dat gebruikmaakt van gemengde precisie (mixed-precision) en iteratieve verfijning (iterative refinement). Het idee is om de kracht van kwantumcomputers te combineren met de stabiliteit en snelheid van klassieke processors.

Het algoritme werkt als volgt:

1. Initiële oplossing (Lage precisie): Een eerste oplossing $\tilde{x}_0$ wordt berekend met de QSVT-methode op een kwantumprocessor (QPU), maar met een lage precisie ($\epsilon_l$). Dit is goedkoper omdat de vereiste polynoomgraad lager is.
2. Iteratieve verfijning (Hoge precisie): De restvector $r_i = b - A\tilde{x}_i$ wordt berekend op een klassieke processor (CPU) met hoge precisie.
3. Correctie: Het correctievector-probleem $Ae_i = r_i$ wordt opnieuw opgelost met de QSVT op de QPU, maar nu met dezelfde lage precisie $\epsilon_l$.
4. Update: De oplossing wordt bijgewerkt: $\tilde{x}_{i+1} = \tilde{x}_i + e_i$ op de CPU in hoge precisie.
5. Herhaling: Dit proces wordt herhaald totdat de geschaalde rest $\omega = \|b - A\tilde{x}\| / \|b\|$ de gewenste tolerantie $\epsilon$ bereikt.

Belangrijke technische nuances:

• Normalisatie: Omdat kwantumalgoritmen genormaliseerde toestanden vereisen, moet de vector $b$ worden genormaliseerd. De schaal van de oplossing wordt later hersteld op de CPU via een minimaliseringsprobleem.
• Communicatie: De matrix $A$ (via blokkodering) wordt slechts één keer naar de QPU gestuurd. In elke iteratie worden alleen de restvectors (in de vorm van toestandvoorbereidingscircuits) overgedragen, wat de communicatie-overhead minimaliseert.
• Convergentie: De convergentie is gegarandeerd zolang $\epsilon_l \kappa < 1$. Het aantal benodigde iteraties wordt begrensd door $\lceil \log(\epsilon) / \log(\epsilon_l \kappa) \rceil$.

Belangrijkste Bijdragen

1. Hybride Architectuur: Het paper introduceert een specifiek ontwerp voor een CPU/QPU-systeem dat iteratieve verfijning toepast op QSVT. Dit benut de snelheid van lage precisie op de QPU en de nauwkeurigheid van hoge precisie op de CPU.
2. Complexiteitsanalyse: De auteurs leveren een gedetailleerde analyse van zowel de kwantum- als klassieke kosten.
   • Kwantumkosten: Het totale aantal calls naar de blokkodering (block-encoding) wordt drastisch gereduceerd omdat de polynoomgraad in elke iteratie lager kan blijven (gebaseerd op $\epsilon_l$ in plaats van de uiteindelijke $\epsilon$).
   • Klassieke kosten: De overhead voor het berekenen van resten en updates op de CPU is verwaarloosbaar vergeleken met de kosten van de QSVT.
3. Theoretische Bewijzen: Er wordt een stelling bewezen die de convergentie en de bovengrens van het aantal iteraties aangeeft, afhankelijk van het conditiegetal en de initiële precisie.
4. Implementatie: Het algoritme is geïmplementeerd en getest met de myQLM-simulator, inclusief toestandvoorbereiding, blokkodering en QSVT-circuits.

Resultaten

De auteurs hebben numerieke experimenten uitgevoerd met willekeurige matrices en tridiagonale matrices (afgeleid van de Poisson-vergelijking) met verschillende conditiegetallen ($\kappa$).

• Convergentie: De experimenten bevestigen dat de geschaalde rest exponentieel daalt met elke iteratie. De theoretisch afgeleide bovengrens voor het aantal iteraties bleek een scherpe schatting te zijn.
• Efficiëntie: Voor een gewenste hoge nauwkeurigheid ($\epsilon$) is het totale aantal calls naar de blokkodering aanzienlijk lager bij het gebruik van iteratieve verfijning dan bij het direct oplossen met hoge precisie.
  • Zonder verfijning: Complexiteit is $O(\frac{B \kappa}{\epsilon^2} \log(\kappa/\epsilon))$.
  • Met verfijning: Complexiteit is $O(\frac{B \kappa}{\epsilon_l^2} \log(\kappa/\epsilon_l) \cdot \text{iteraties})$. Omdat $\epsilon_l \gg \epsilon$, is de factor $\epsilon_l^2$ veel gunstiger.
• Voorbeeld: Bij een conditiegetal $\kappa=2$ en een zeer hoge eindschaarpte, toonde het algoritme met verfijning een duidelijk voordeel in complexiteit (aantal blokkodering-calls) ten opzichte van de directe methode.

Betekenis en Conclusie

Dit werk is significant omdat het een praktische route biedt naar het oplossen van lineaire systemen op toekomstige kwantumcomputers, zonder dat deze extreem grote resources nodig hebben voor hoge precisie.

• Haalbaarheid: Het maakt het mogelijk om "goedkope" kwantumoplossingen (lage precisie) te combineren met klassieke verfijning om industriële nauwkeurigheid te bereiken.
• Toekomstvisie: Het illustreert hoe hybride CPU/QPU-systemen in High-Performance Computing (HPC) kunnen functioneren, waarbij elke architectuur doet wat het het beste kan.
• Beperkingen: De huidige resultaten zijn gebaseerd op simulaties. De schaalbaarheid naar grotere problemen en het hanteren van slecht geconditioneerde matrices vereist nog verdere testen op echte, foutvrije kwantumhardware.

Samenvattend biedt dit paper een veelbelovende strategie om de huidige beperkingen van kwantumalgoritmen voor lineaire algebra te overwinnen door slimme integratie van klassieke numerieke methoden.