A 0.651-approximation to quantum Max Cut via Rydberg atoms

Technische Samenvatting: Een 0,651-benadering van Quantum Max Cut via Rydberg-atomen

Probleemdefinitie
Het artikel behandelt het Quantum Max Cut (QMC) probleem, dat equivalent is aan het vinden van de grondtoestandsenergie van de anti-ferromagnetische Heisenberg-Hamiltoniaan. Dit probleem is QMA-compleet, wat betekent dat het zelfs met een universele kwantumcomputer niet efficiënt opgelost kan worden. Het doel is om een benaderingsalgoritme te vinden dat een oplossing garandeert binnen een specifieke ratio ($\alpha$) van de optimale grondtoestandsenergie. De huidige state-of-the-art klassieke methoden, die uitsluitend vertrouwen op semidefiniete programmeringsrelaxaties (SDP), bereiken een benaderingsratio van $\alpha = 0,614$.

Methodologie: Een hybride kwantum-klassieke aanpak
De auteurs stellen een hybride algoritme voor dat de natuurlijke kwantumdynamica van Rydberg-atomsystemen integreert met klassieke optimalisatietechnieken (SDP en gerandomiseerde afronding). De methodologie verloopt in vier afzonderlijke stadia:

1. Codering en Annealing:
   Een QMC-instantie gedefinieerd op een graaf $G=(V, E, \omega)$ wordt gecodeerd in een Rydberg-atoomarray. Het statische deel van de Rydberg-Hamiltoniaan, $H_r$, wordt geconstrueerd om de $XX + YY$ interactietermen te bevatten die overeenkomen met de randen (edges) van de graaf:
   $$H_r = \sum_{(ij) \in E} \omega_{ij} (X_i X_j + Y_i Y_j)$$
   Het systeem ondergaat een annealing-procedure om een benaderende grondtoestand te bereiden, aangeduid als $\varrho_r$.

2. Meting en Constraatformulering:
   De verwachtingswaarden $\langle X_i X_j + Y_i Y_j \rangle$ worden gemeten voor alle randen in de geannealde toestand $\varrho_r$. Deze waarden dienen als empirische restricties voor een daaropvolgende klassieke optimalisatiestap.

3. Semidefiniete Programmering en Afronding:
   Een pseudo-momentmatrix $\Delta$ wordt geoptimaliseerd via SDP, onderworpen aan de restricties afgeleid van de Rydberg-metingen en de algebraïsche relaties van Pauli-operatoren. Deze matrix wordt vervolgens afgerond naar een producttoestand $\varrho_p$ met behulp van een gerandomiseerde projectietechniek (Cholesky-decompositie gevolgd door een willekeurige projectie van $\mathbb{R}^{4n}$ naar $\mathbb{R}^3$).

4. Selectie van de Eindtoestand:
   Het algoritme geeft de toestand met de lagere energie terug: ofwel de Rydberg-grondtoestand $\varrho_r$ of de klassiek afgeronde producttoestand $\varrho_p$.

Belangrijke Theoretische Bijdragen
Het artikel stelt een voorwaardelijke benaderingsratio vast van 0,651, waarmee de voorheen bekende beste ratio van 0,614 wordt overtroffen. De afleiding berust op twee belangrijke theoretische inzichten:

• Ondergrens via de Rydberg-grondtoestand: De auteurs bewijzen dat de grondtoestandsenergie van de volledige QMC-Hamiltoniaan ($H_{qmc}$) ondergebonden kan worden door de energie van de Rydberg-Hamiltoniaan ($H_r$). Door gebruik te maken van de $SU(2)$-invariantie van het Heisenberg-model, tonen zij aan dat de verwachtingswaarden van $XX$, $YY$ en $ZZ$ gelijk zijn in de optimale grondtoestand. Dit maakt de reconstructie van de volledige QMC-energie mogelijk op basis van de gedeeltelijke $XX+YY$-metingen verkregen uit het Rydberg-systeem.
• Bovengrens via Afronding: Het artikel analyseert de energie van de producttoestand $\varrho_p$ gegenereerd door de SDP-afronding. Er wordt een analytische expressie afgeleid voor de verwachte energie van deze toestand op basis van de gemeten correlaties.
• Optimalisatie van de Ratio: Door de ondergrens (afgeleid van de Rydberg-toestand) en de bovengrenzen (van zowel de Rydberg-toestand als de producttoestand) te combineren, formuleren de auteurs een minimalisatieprobleem over de correlatieparameter $t_{ij}$. Het oplossen hiervan levert de 0,651 ratio op.

Resultaten en Robuustheid

• Benaderingsratio: Het algoritme bereikt een voorwaardelijke benaderingsratio van $\kappa = 0,651$.
• Robuustheid tegen Ruis: Een belangrijke bevinding is de veerkracht van het algoritme tegen imperfecte grondtoestand-preparatie. De auteurs demonstreren dat het 0,651-voordeel standhoudt, zelfs als de Rydberg-annealingprocedure een toestand oplevert met slechts 89% van de ware Rydberg-grondtoestandsenergie ($\eta = 0,89$). Onder deze drempel neemt het voordeel ten opzichte van puur klassieke SDP-methoden af.
• Computationele Complexiteit: De hybride aanpak vermindert de dimensionaliteit van het klassieke optimalisatieprobleem. Terwijl klassieke schema's die zich richten op verstrengelde toestanden $O(n^4)$ reële variabelen vereisen, werkt deze hybride methode op $O(n^2)$ variabelen, waarbij gebruik wordt gemaakt van het kwantumsysteem om de complexiteit van de verstrengelingsstructuur te verwerken.

Betekenis
Het artikel beweert een nieuwe route te openen voor hybride kwantum-klassieke algoritmen. Het demonstreert dat het combineren van kwantumhardware (specifiek Rydberg-atoomarrays) met klassieke optimalisatie sterkere benaderingsgaranties kan opleveren dan klassieke methoden alleen, zelfs wanneer de kwantumhardware het onderliggende Hamiltoniaan-probleem niet perfect oplost. Het werk suggereert dat kwantumplatforms effectieve "proxies" kunnen dienen om hoogwaardige ondergrenzen en startpunten voor klassieke afrondingsprocedures te bieden, waardoor de computationele schaleringsbeperkingen van zuivere klassieke benaderingen effectief worden omzeild.