Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Probleemstelling

Semidefinitie programmering (SDP) is een fundamenteel convex optimalisatieprobleem met toepassingen in de regeltechniek, statistiek, machine learning, financiën en kwantuminformatica. Het oplossen van grootschalige SDP-instanties blijft echter computationeel uitdagend voor klassieke algoritmen. De primaire knelpunten zijn de hoge kosten van het oplossen van lineaire stelsels en het uitvoeren van eigenwaardedecomposities (specifiek, projectie op de positief semidefinitie kegel) bij elke iteratie. Hoewel kwantumalgoritmen zoals Quantum Matrix Multiplicative Weights Updates (QMWU) en Quantum Interior Point Methods (QIPM) zijn voorgesteld om deze problemen aan te pakken, kampen zij vaak met afruilverschillen in dimensie-afhankelijkheid, sparsiteitsparameters of nauwkeurigheidseisen.

Methodologie

De auteurs stellen de Quantum Alternating Direction Method of Multipliers (QADMM) voor, een hybride kwantum-klassiek algoritme dat is ontworpen om SDP's op te lossen door gebruik te maken van kwantumversnellingen voor de meest kostbare subroutines, terwijl de robuustheid van klassieke eerste-orde methoden behouden blijft.

1. Inexact ADMM-framework:
De kern van de aanpak is een inexact ADMM-framework die specifiek is afgestemd op SDP's. In tegen naar de standaard ADMM, staat dit framework expliciet fouten toe die worden geïntroduceerd door kwantumsubroutines.

• Dual Variable Update: De update voor de duale variabele $y$ houdt het oplossen van een lineair stelsel $(AA^*)y = \dots$ in. In de kwantumsetting wordt dit opgelost met een Quantum Linear Solver (QLS).
• Primal Variable Updates: De updates voor de primaire variabelen $S$ en $X$ omvatten projectie op de positief semidefinitie (PSD) kegel. Klassiek vereist dit een eigenwaardedecompositie. QADMM vervangt dit door een polynomiale proximale operator.
• Fouttolerantie: Het framework introduceert fouttermen ($\Delta \tilde{y}, \Delta \tilde{S}, \Delta \tilde{X}$, etc.) om onnauwkeurigheden te compenseren die voortkomen uit block-encoding benaderingen, Quantum Singular Value Transformation (QSVT) en kwantumstate-tomografie. De auteurs bewijzen dat de gemiddelde iteraties van dit inexacte schema nog steeds convergeren naar een $\epsilon$-optimale oplossing.

2. Polynomial Proximal Operator en QSVT:
Om de kostbare eigenwaardedecompositie in de projectiestap te vermijden, ontwerpen de auteurs een polynomiale functie $g(x)$ die de projectie-operator $\text{Proj}_{S_+}(x) = \max(0, x)$ benadert.

• Met behulp van benaderingstheorie construeren zij een monotone stijgende polynoom $g$ van graad $d = O(1/\epsilon)$ die de ReLU-functie benadert binnen een fout $\epsilon$.
• Deze polynoom wordt op een kwantumcomputer geïmplementeerd met behulp van Quantum Singular Value Transformation (QSVT) onder het block-encoding model.
• Een "virtuele" barrièrefunctie $h(S)$ wordt geconstrueerd zodanig dat de proximale operator hiervan overeenkomt met deze polynomiale transformatie, wat de variationele structuur garandeert die vereist is voor de convergentieanalyse.

3. Algoritmische Flow:
Het algoritme verloopt iteratief:

1. $y$-update: Bereken de lineaire mapping klassiek, bereid een kwantumtoestand voor en los het lineaire stelsel op met behulp van QLS.
2. $V$-update: Bereken de tussenliggende variabele $V = C - A^*(y) - \gamma X$ met behulp van Linear Combination of Unitaries (LCU).
3. $S$-update: Pas de polynomiale spectrale transformatie (die de PSD-projectie benadert) toe op $V$ met behulp van QSVT, gevolgd door tomografie om de klassieke matrix te reconstrueren.
4. $X$-update: Vergelijkbaar met de $S$-update, waarbij een polynomiale transformatie wordt toegepast om de duale variabele $X$ bij te werken.
5. Klassieke Post-processing: Gereconstrueerde matrices worden geprojecteerd op begrensde verzamelingen (Frobenius-norm beperkingen) om haalbaarheid te garanderen.

Belangrijkste Bijdragen

1. Robuust Inexact ADMM-framework: Het artikel legt een theoretische brug tussen de klassieke ADMM-convergentietheorie en praktische kwantumcomputatie. Zij bewijzen dat de gemiddelde iteratie convergeert naar een $\epsilon$-optimale oplossing met een snelheid van $O(1/\epsilon)$, zelfs wanneer subprobleem-oplossingen en duale updates fouten bevatten die begrensd worden door kwantumruis en benaderingslimieten.
2. Polynomiale Proximale Mapping voor SDP: De auteurs introduceren een nieuwe methode om de eigenwaardedecompositie in ADMM te vervangen door een polynomiale eigenwaardetransformatie. Dit maakt het mogelijk om QSVT te gebruiken om de semidefinitie kegelrestricties efficiënt te behandelen, waardoor de $O(n^3)$ of $O(n^4)$ kosten van klassieke spectrale projecties worden vermeden.
3. Complexiteitsanalyse en Vergelijking: Het artikel biedt een rigoureuze complexiteitsanalyse die aantoont dat QADMM een gunstige schaling bereikt ten opzichte van de dimensie $n$ vergeleken met klassieke ADMM en bestaande kwantumsolvers (QMWU en QIPM).

Resultaten en Complexiteit

De auteurs leiden de totale computationele complexiteit af die vereist is om een absolute nauwkeurigheid $\epsilon_{abs}$ in de objectieve functie en de haalbaarheidsresidue te bereiken.

• Iteratiecomplexiteit: Het algoritme vereist $K = O\left(\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ iteraties, waarbij $R_X$ en $R_S$ bovengrenzen zijn op de Frobenius-normen van de optimale primaire en duale oplossingen.
• Totale Complexiteit:
  • Klassieke Operaties: $O\left((s_A + n^2)\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$, waarbij $s_A$ het aantal niet-nul elementen in de restrictiematrices is.
  • Kwantum Gate Complexiteit: $\tilde{O}\left( \left[ m\kappa_A^2(1+R_y)^2 + n^2(\kappa_A^2(1+R_y) + R_X) \right] \frac{(R_X + R_S)^3}{\epsilon_{abs}^3} \right)$.
  • Hierbij is $\kappa_A$ de conditiegetal van $AA^*$ en $R_y$ de bovengrens op de duale variabele norm.

Vergelijking:

• Vs. Klassieke ADMM: QADMM biedt een betere afhankelijkheid van de dimensie $n$ (het vermijden van de $O(n^6)$ of $O(n^4)$ factoren die geassocieerd worden met klassieke eigenwaardedecomposities en matrixvermenigvuldigingen in elke iteratie).
• Vs. QIPM: QADMM vermijdt de hoge afhankelijkheid van het conditiegetal van het Newton-stelsel ($\kappa_{newt}$) en biedt een andere afruil in nauwkeurigheid.
• Vs. QMWU: Hoewel QADMM een vergelijkbare dimensie-afhankelijkheid heeft als QMWU, bereikt het een lagere-orde afhankelijkheid van de nauwkeurigheidsparameter $\epsilon_{abs}$ (cubisch versus hogere machten in sommige regimes) en is het bijzonder voordelig wanneer de Frobenius-norm van de oplossing $\|X^*\|_F$ veel kleiner is dan zijn spoor $\text{Tr}(X^*)$ (bijv. in diagonale SDP-embeddings).

Betekenis en Claims

Het artikel claimt dat QADMM een gunstige schaling met betrekking tot de dimensie biedt voor het oplossen van grootschalige SDP's, wat het een veelbelovende kandidaat maakt voor problemen waar klassieke solvers moeite hebben met de kosten van eigenwaardedecomposities.

De auteurs benadrukken dat hun aanpak:

• Kwantumversnellingen Integreert: Het slaagt erin om QSVT en QLS te gebruiken om de meest rekenintensieve delen van het ADMM-algoritme te versnellen.
• Convergentiegaranties Handhaaft: Door een inexact framework te ontwikkelen, zorgen zij ervoor dat kwantumfouten de convergentie naar een optimale oplossing niet in de weg staan.
• Afhankelijk is van Specifieke Aannames: Het algoritme gaat uit van de beschikbaarheid van polynomiale-omvang QRAM voor datatoegang en block-encoding van de invoermatrices. De auteurs erkennen dat dit een sterke aanname is en merken op dat toekomstig werk zich zal richten op het versoepelen van deze vereiste.

Het artikel concludeert dat hoewel het algoritme wordt beperkt door de QRAM-aanname, het een belangrijke stap voorwaarts vertegenwoordigt in het toepassen van kwantumcomputing op grootschalige convexe optimalisatie, waarbij het specifiek een levensvatbaar alternatief biedt voor zowel klassieke eerste-orde methoden als andere kwantum SDP-solvers in specifieke regimes van dimensie en nauwkeurigheid.