From barren plateaus through fertile valleys: Conic extensions of parameterised quantum circuits

Probleemstelling: Barren Plateaus in Variatiekwantumalgoritmen

Variatiekwantumalgoritmen (VQA's), zoals de Quantum Approximate Optimization Algorithm (QAOA), zijn momenteel de meest belovende aanpak voor optimalisatieproblemen op NISQ-achtige (Noisy Intermediate-Scale Quantum) apparaten. Een fundamentele beperking van deze methoden is het fenomeen van barren plateaus (vruchtbare plateaus).

• Het fenomeen: Bij diepe parameteriseerde kwantumcircuits (PQC) nemen de gradiënten van de kostenfunctie exponentieel af naarmate het aantal qubits toeneemt. Hierdoor wordt het voor klassieke optimalisatoren onmogelijk om een richting te vinden die de energie verlaagt.
• De oorzaak: De optimale richting om de energie te minimaliseren staat vaak loodrecht op de raakruimte van het variatie-manifold (de ruimte van alle bereikbare toestanden via unitaire operaties). Unitair PQC kan alleen langs het oppervlak van dit manifold bewegen, waardoor het vastloopt in lokale minima of plateaus.
• Huidige beperking: Zelfs met geavanceerde klassieke optimalisatiemethoden (zoals gradient descent) stagneert de prestatie van QAOA vaak snel, vooral bij grotere probleemgroottes, en bereikt zelden de kwaliteit van de beste klassieke solvers (zoals de Goemans-Williamson-bounds voor MAXCUT).

Methodologie: Kegeluitbreidingen en Lineaire Combinaties van Unitaires

De auteurs introduceren een nieuwe methode om uit barren plateaus te ontsnappen door het variatie-manifold te uitbreiden tot een variatiekegel (variational cone) via niet-unitaire operaties.

1. Concept van de Variatiekegel:
   In plaats van alleen unitaire operaties toe te passen, stellen de auteurs een niet-unitaire operator $M_\alpha$ voor die als een sprong door het binnenste van de Hilbert-ruimte fungeert. Dit wordt gedefinieerd als een lineaire combinatie van unitaire operatoren (LCU):
   $$M_\alpha = \sum_{i=1}^{\ell} \alpha_i U_i$$
   Waarbij $U_i$ vaste unitaire poorten zijn (uit het oorspronkelijke circuit) en $\alpha_i$ complexe parameters zijn. Door de identiteit op te nemen, kan de methode altijd terugvallen op de huidige staat, maar biedt ze ook nieuwe richtingen die niet op het unitaire manifold liggen.

2. Optimalisatie via Generalised Eigenvalue Problems (GEP):
   Het vinden van de optimale parameters $\alpha$ om de energie te minimaliseren onder normalisatie, wordt herschreven als een generaliseerd eigenwaardeprobleem (GEP) in een laag-dimensionale ruimte:
   $$H\alpha = \lambda E\alpha$$
   Hierbij zijn $H$ en $E$ momentenmatrices die de verwachtingswaarden van de Hamiltoniaan en de overlap tussen toestanden beschrijven. Deze matrices kunnen efficiënt geschat worden via klassieke meetprotocollen zoals de Hadamard-test.

3. Implementatie (LCU-kanaal):
   De niet-unitaire stap wordt fysiek geïmplementeerd met behulp van een Linear Combination of Unitaries (LCU) kanaal. Dit vereist:

   • Een kleine ancilla-register (extra qubits).
   • Het toepassen van gecontroleerde unitaire operaties.
   • Een projectieve meting op de ancilla.
   • Post-selectie: De methode is niet-deterministisch; het resultaat is alleen succesvol als de meting een specifieke uitkomst geeft. De succeskans wordt gegeven door $p_{succ} = \|\alpha\|_1^{-2}$.

4. Iteratief Schema:
   Het algoritme werkt als volgt:

   • Start met standaard QAOA (unitair).
   • Zodra de gradiënt verdwijnt (barren plateau), voer een LCU-stap uit om de staat te updaten.
   • Gebruik de nieuwe staat als startpunt voor een nieuwe QAOA-loop.
   • Herhaal dit proces totdat een satisfactorische oplossing is gevonden.

Belangrijkste Bijdragen

• Theoretisch kader: De introductie van "Quantum Conic Programming" (QCP), waarbij variatiekwantumalgoritmen worden uitgebreid met een kegel van niet-unitaire operaties om de beperkingen van unitaire manifolds te doorbreken.
• Efficiëntie: Het reduceren van het optimalisatieprobleem voor de sprongrichtingen tot een laag-dimensionaal GEP, dat klassiek snel opgelost kan worden, zelfs voor grote kwantumsystemen.
• Robuustheid: Het aantonen dat deze methode effectief is tegen barren plateaus en lokale minima, iets waar pure unitaire VQA's vaak tegenaan lopen.
• NISQ-compatibiliteit: De methode is ontworpen voor huidige hardware, gebruikmakend van mid-circuit metingen en kleine ancilla-systemen.

Resultaten

De auteurs hebben hun methode getest via uitgebreide simulaties op het MAXCUT-probleem (op 3-regulaire grafen) met variërende qantaantallen (van 4 tot 22 qubits).

• Prestatieverbetering:
  • Standaard QAOA (zonder LCU) stagneerde vaak na ~10 iteraties met een benaderingsratio van ongeveer 0,785, wat onder de klassieke Goemans-Williamson (GW) ondergrens van 0,878 ligt.
  • Met één LCU-stap steeg de ratio naar 0,842.
  • Met twee LCU-stappen werd de GW-bounds overschreden (0,885).
  • Met drie LCU-stappen werd een ratio van 0,904 bereikt, wat aanzienlijk beter is dan de beste klassieke solvers voor deze instanties.
• Kansverdeling:
  • Zonder LCU-stappen had de outputstaat minimale overlap met de hoogste kwaliteit oplossingen.
  • Na drie LCU-stappen was de waarschijnlijkheidsverdeling scherp gefocust op basisstaten met een hoge benaderingsratio (>0,9).
• Schaalbaarheid:
  • De prestatie (benaderingsratio) nam af bij toenemende probleemgrootte, maar de LCU-gemodificeerde QAOA bleef consistent beter presteren dan de standaard QAOA en behield ratios boven de GW-bounds, zelfs bij 22 qubits.
  • Opvallend genoeg bleven de succeskansen van de LCU-stappen stabiel of namen zelfs licht toe bij grotere instanties (in het geteste bereik), met kansen rond de 10-15% voor drie opeenvolgende stappen.

Betekenis en Conclusie

Dit werk biedt een veelbelovende oplossing voor een van de grootste obstakels in het NISQ-tijdperk: het vastlopen van variatiekwantumalgoritmen in barren plateaus.

• Paradigmaverschuiving: Het toont aan dat het introduceren van niet-unitaire operaties (via LCU en post-selectie) een krachtig mechanisme is om de zoekruimte te verbreden en optimale oplossingen te vinden die ontoegankelijk zijn voor puur unitaire circuits.
• Praktische toepasbaarheid: Hoewel de methode niet-deterministisch is (door post-selectie), is de succeskans hoog genoeg om nuttig te zijn, en de verbetering in de kwaliteit van de oplossing compenseert de extra meetkosten.
• Toekomstperspectief: De auteurs zien dit als het begin van een bredere raamwerk (QCP). Toekomstig werk richt zich op het verbeteren van de succeskans van de LCU-kanaal en het testen op echte, ruisgevoelige hardware.

Kortom, de paper demonstreert dat door "sprongen" te maken door de Hilbert-ruimte (via conische uitbreidingen) in plaats van alleen langs het oppervlak te glijden, kwantumalgoritmen significant effectiever kunnen worden voor complexe optimalisatieproblemen.