Automorphism-Assisted QAOA: A Classical-Estimator Speedup for QAOA Simulation on Graphs with Non-Trivial Symmetry

Technische Samenvatting: Automorphism-Assisted QAOA (AA-QAOA)

Probleemstelling
Het Quantum Approximate Optimization Algorithm (QAOA) is een vooraanstaande hybride kwantum-klassieke benadering voor het oplossen van NP-harde combinatorische optimalisatieproblemen, zoals het ongewogen MaxCut-probleem. Een significante bottleneck in QAOA-onderzoek, met name voor groepen die vertrouwen op klassieke statevector-simulatoren vanwege beperkte toegang tot Quantum Processing Units (QPU's), is de computationele kosten van de klassieke optimalisatielus. Specifiek moet bij elke iteratie van de klassieke optimizer de verwachtingswaarde van het probleem-Hamiltoniaan $H_C$ worden berekend. Voor een graaf met $|E|$ randen (edges) aggregeert de standaard statevector-estimator $|E|$ termen van de vorm $\langle Z_i Z_j \rangle$. Omdat elke term een $O(2^n)$ passage over de statevector-amplitudes vereist (waarbij $n$ het aantal qubits is), schalen de wall-time kosten per optimizer-iteratie als $O(|E| \cdot 2^n)$. Deze aggregatiekosten domineren vaak de totale simulatietijd, vooral voor grafen met veel randen, zelfs bij lage circuitdieptes ($p$).

Methodologie: Automorphism-Assisted QAOA (AA-QAOA)
Het artikel stelt AA-QAOA voor, een methode die de klassieke statevector-simulatie van QAOA versnelt door de symmetrieën van de onderliggende graaf te exploiteren. De kerninzicht is dat de QAOA-ansatz voor grafen met een niet-triviale automorphismengroep $\text{Aut}(G)$ een toestand $|\psi(\vec{\beta}, \vec{\gamma})\rangle$ voorbereidt die invariant is onder de werking van $\text{Aut}(G)$.

De methodologie verloopt als volgt:

1. Identificatie van Rand-Orbits: Met behulp van het Nauty-pakket berekent het algoritme de generatoren van de automorphismengroep van de graaf. Deze generatoren worden gebruikt om de verzameling randen $E$ te partitioneren in equivalentieklassen (orbits), aangeduid met $\tilde{S}_m$. Randen binnen dezelfde orbit zijn structureel identiek onder de symmetrieën van de graaf.
2. Observabele Substitutie: In plaats van de volledige kosten-Hamiltoniaan $H_C = \frac{1}{2} \sum_{(i,j) \in E} (1 - Z_i Z_j)$ te evalueren, vervangt de methode deze door een gereduceerde observabele $H_{\text{red}}$. Deze gereduceerde Hamiltoniaan behoudt slechts één representatieve ZZ-term per rand-orbit, gewogen door de grootte van die orbit:
   $$H_{\text{red}} = \frac{1}{2} \sum_{m=1}^{|O_E|} |\tilde{S}_m| (1 - Z_{i_m} Z_{j_m})$$
   waarbij $|O_E|$ het aantal rand-orbits is.
3. Exacte Equivalentie: De auteurs bewijzen dat voor de $\text{Aut}(G)$-invariante toestand die door de standaard QAOA-ansatz wordt voorbereid, de verwachtingswaarden identiek zijn: $\langle H_{\text{red}} \rangle = \langle H_C \rangle$. Bijgevolg blijven het optimalisatielandschap, de optimale variatiereparameters $(\vec{\beta}^*, \vec{\gamma}^*)$ en de uiteindelijke benaderingsratio onveranderd.
4. Pipeline Implementatie: De QAOA-ansatz circuit wordt geconstrueerd met de volledige Hamiltoniaan $H_C$ (om te garanderen dat de toestandvoorbereiding identiek is aan standaard QAOA). Echter, tijdens de klassieke optimalisatielus berekent de estimator de verwachtingswaarde met behulp van alleen de $|O_E|$ termen van $H_{\text{red}}$.

Belangrijkste Bijdragen

• Klassieke Aggregatie Versnelling: De primaire bijdrage is een reductie in de klassieke post-processing kosten van de statevector-estimator. De aggregatiekosten dalen van $O(|E| \cdot 2^n)$ naar $O(|O_E| \cdot 2^n)$ per iteratie. De versnellingsfactor wordt bepaat door de orbit-ratio $|E|/|O_E|$.
• Ontkoppeling van de Reverse Causal Cone (RCC): Het artikel onderscheidt de methode expliciet van eerder werk dat gebruikmaakt van de Reverse Causal Cone (RCC) om de circuitdiepte of qubit-spanne te reduceren. De auteurs demonstreren dat de AA-QAOA versnelling onafhankelijk is van de qubit-spanne van de representatieve RCC's. Zelfs als de RCC van een enkele representatieve rand alle qubits beslaat (zoals in complete grafen), blijft de versnelling bestaan omdat de besparing optreedt in de klassieke sommatie van termen, en niet in de kwantumcircuit-executie of toestandsevolutie.
• Exactheid: De methode biedt een exacte substitutie, geen benadering. Optimalisatie tegen $H_{\text{red}}$ convergeert naar exact dezelfde oplossing als optimalisatie tegen $H_C$.

Resultaten
De auteurs hebben AA-QAOA getest op diverse grafenfamilies met $p=1$ en $p=2$ lagen:

• Boomstructuur-Grafen: Op binaire en gebalanceerde bomen tot 34 vertices bereikte de methode significante reducties in wall-time. Voor een 34-vertex binaire boom daalde de optimizer-tijd van $>3600$ seconden (volledige Hamiltoniaan) naar $360,56$ seconden (gereduceerd), een reductie van meer dan 90%. Het piekgeheugengebruik nam ook aanzienlijk af.
• Diagnostische Controles: Om het mechanisme te isoleren, testten de auteurs:
  • Complete Grafen ($K_n$): Ondanks het hebben van een enkele rand-orbit ($|O_E|=1$) en een representatieve RCC die elke qubit beslaat, vertoonde $K_{16}$ een $\approx 8\times$ versnelling. Dit weerlegt de hypothese dat de versnelling afhankelijk is van het reduceren van de qubit-spanne van de RCC.
  • Ster-Grafen: Toonden versnellingen die consistent waren met de orbit-ratio zodra de overhead werd geminimaliseerd.
  • Willekeurige 3-Reguliere Grafen: Voor grafen met triviale automorphismengroepen ($|O_E| \approx |E|$), werd geen versnelling waargenomen, wat bevestigt dat het voordeel strikt gekoppeld is aan symmetrie.
• Architectuur Onafhankelijkheid: Tests op zowel CPU- als GPU-backends bevestigden dat de versnelling inherent is aan de klassieke aggregatiestap en geen artefact is van specifieke hardware-accelerators.
• Benaderingsratio's: Over alle geteste instanties waren de benaderingsratio's $R_{\text{red}}$ en $R_{\text{full}}$ identiek binnen de optimizer-variantie, wat de theoretische claim van exacte equivalentie valideert.

Betekenis en Reikwijdte
Het artikel positioneert AA-QAOA als een gespecialiseerde versneller voor klassieke statevector-simulatie pipelines, die de primaire tool zijn voor QAOA-onderzoeksgroepen zonder QPU-toegang.

• Beperkingen: De auteurs geven expliciet aan dat AA-QAOA geen versnelling biedt op een quantumprocessor (QPU). Op hardware wordt het volledige circuit uitgevoerd ongeacht de gemeten observabele, en de aggregatie van diagonale ZZ-termen is een triviale post-processing stap op klassieke bitstrings die niet de $O(|E| \cdot 2^n)$ kosten met zich meebrengt die bij statevector-simulatie voorkomen.
• Toepasbaarheid: De methode is het meest effectief voor gestructureerde grafen met een hoge symmetrie (bijv. bomen, cycli, complete grafen, hyperkubussen) waar de orbit-ratio $|E|/|O_E|$ groot is. Het is minder effectief voor generiek asymmetrische grafen (bijv. willekeurige 3-reguliere grafen) waar de automorphismengroep triviaal is.
• Overhead: Het pre-computeren van automorfismen (met behulp van Nauty) heeft een kostenpost die niet geamortiseerd is in de gerapporteerde per-iteratie tijden. Echter, voor typische QAOA-studies waarbij vele optimizer-iteraties of sweeps over parameters worden uitgevoerd, is deze pre-computatiekosten echter verwaarloosbaar vergeleken met de cumulatieve simulatiebesparingen.

Samenvattend biedt AA-QAOA een rigoureuze, exacte methode om de computationele bottleneck van klassieke QAOA-simulatie te reduceren door gebruik te maken van de symmetrieën van de graaf om het aantal termen in de kosten-verwachtingsaggregatie te verminderen, zonder de kwantumcircuit of de kwaliteit van de oplossing te wijzigen.