Role of overparametrization in quantum approximate optimization

Technische Samenvatting: De rol van overparametrisatie in Quantum Approximate Optimization

Probleemstelling
Variational Quantum Algorithms (VQA's) zijn een leidende aanpak voor het oplossen van problemen op Noisy Intermediate-Scale Quantum (NISQ) apparaten, die beperkt worden door korte coherentietijden en gate-fouten. Een cruciale openstaande vraag in dit veld is het bepalen van de minimale kwantumbronnen (specifiek de circuitdiepte) die vereist zijn om praktische problemen efficiënt op te lossen. Hoewel overparametrisatie—het gebruik van een aantal parameters dat een bepaalde drempel overschrijdt—in klassieke machine learning en sommige kwantumcontexten heeft aangetoond de convergentie te verbeteren en barren plateaus te vermijden, vereist dit vaak circuitdieptes die de capaciteiten van NISQ-hardware overstijgen. Dit werk onderzoekt of overparametrisatie zowel voldoende als noodzakelijk is om oplossingen met een hoge waarschijnlijkheid te verkrijgen voor combinatorische optimalisatieproblemen met behulp van het Quantum Approximate Optimization Algorithm (QAOA).

Methodologie
De auteurs definiëren overparametrisatie met behulp van het concept Effective Quantum Dimension (EQD), wat de expressiviteit van een variationeel circuit kwantificeert op basis van de rang van de Quantum Fisher Information (QFI) matrix. Een circuit wordt als overgeparametriseerd beschouwd wanneer het verhogen van het aantal parameters (diepte) de EQD niet langer vergroot.

De studie richt zich op twee representatieve NP-harde combinatorische optimalisatieproblemen:

1. MAX-CUT: Onderzocht op 2-reguliere grafen (ringen van disagrees), $k$-reguliere grafen en willekeurige ongegewogen grafen.
2. MAX-2-SAT: Onderzocht op willekeurige instanties met variërende clausendichtheden.

Voor elk probleem vergelijken de auteurs de overparametrisatie-diepte ($p_c$, waar de EQD verzadigt) met de optimale diepte ($p^*$, de minimale diepte die nodig is om een oplossing te bereiken binnen een specifieke energie-fouttolerantie $\epsilon$). Ze maken gebruik van numerieke simulaties met laaggebonden heuristische strategieën en willekeurige parameter-initialisaties om energie-fouten en succeswaarschijnlijkheden over verschillende circuitdieptes te volgen.

Belangrijkste bijdragen en resultaten

• MAX-CUT op 2-reguliere grafen:

  • De auteurs leveren een analytisch bewijs dat voor een even aantal qubits $n$, de optimale QAOA-diepte schaalt als $p^* = \lfloor n/2 \rfloor$.
  • Numerieke resultaten bevestigen dat de overparametrisatie-diepte $p_c$ exact samenvalt met deze optimale diepte ($p_c = p^*$) voor systemen tot $n=20$.
  • Conclusie: Voor deze specifieke klasse problemen is overparametrisatie zowel voldoende als noodzakelijk om oplossingen met een hoge waarschijnlijkheid te vinden.

• MAX-CUT op algemene grafen (regulier en willekeurig):

  • Numerieke analyse laat zien dat voor de meeste instanties de optimale oplossing exact wordt gevonden bij of in de directe nabijheid van de overparametrisatie-diepte.
  • De succeswaarschijnlijkheid van het vinden van een oplossing vertoont een abrupte toename wanneer men overgaat van het ondergeparametriseerde naar het overgeparametriseerde regime.
  • Conclusie: Overparametrisatie is voldoende voor succes met een hoge waarschijnlijkheid. Hoewel het niet strikt noodzakelijk is voor elke individuele instantie, is het statistisch noodzakelijk voor het dominante deel van de instanties.

• MAX-2-SAT:

  • In scherp contrast met MAX-CUT worden de meerderheid van de MAX-2-SAT instanties opgelost ruim binnen het ondergeparametriseerde regime ($p/p_c \ll 1$).
  • Voor $n=7$ werden ongeveer 85% van de instanties opgelost met circuitdieptes die slechts de helft van de overparametrisatie-diepte bedroegen.
  • De optimale diepte schaalt als $p^* \sim \sqrt{2^n}$, terwijl de overparametrisatie-diepte $p_c \sim 2^n$ schaalt. Bijgevolg neemt de ratio $p^*/p_c$ exponentieel af met de probleemgrootte.
  • Conclusie: Overparametrisatie is niet noodzakelijk voor het oplossen van MAX-2-SAT instanties; hoge succeswaarschijnlijkheden worden bereikt met aanzienlijk vlakkere circuits.

Betekenis en claims
Het artikel claimt dat de relatie tussen overparametrisatie en de optimale circuitdiepte probleemafhankelijk is.

• Voor MAX-CUT fungeert overparametrisatie als een kritische drempel; de diepte die nodig is om de expressiviteit van het circuit (EQD) te verzadigen, komt overeen met de diepte die nodig is om het probleem op te lossen.
• Voor MAX-2-SAT benadrukken de resultaten het potentieel van QAOA in het ondergeparametriseerde regime. Omdat deze problemen kunnen worden opgelost met circuits die veel minder diep zijn dan de overparametrisatie-diepte, kan QAOA voor huidige NISQ-apparaten levensvatbaarder zijn dan eerder gesuggereerd door studies die zich uitsluitend richten op overgeparametriseerde regimes.

De auteurs benadrukken dat hoewel overparametrisatie convergentie garandeert in bepaalde theoretische kaders, het geen universele vereiste is voor alle combinatorische problemen. Deze bevinding suggereert dat voor specifieke probleemklassen zoals MAX-2-SAT, hulpbron-efficiënte oplossingen kunnen worden gevonden zonder de diepe circuits die typisch ruis en trainability-problemen (zoals barren plateaus) veroorzaken op nabije hardware. De auteurs merken echter ook op dat zelfs in het ondergeparametriseerde regime, beperkingen in de trainbaarheid zoals barren plateaus nog steeds kunnen voortbestaan voor grote probleemgroottes.