Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

Dit artikel stelt een ancilla-vrij, op Fourier gebaseerd raamwerk voor Lineaire Combinatie van Unitaire Operatoren (LCU) voor dat complexe quantumcircuits voor optimalisatietaken efficiënt decomposeert door circuitcomplexiteit in te wisselen voor een polynomiale steekproefkosten, waardoor hardware-vriendelijke implementaties van algoritmen zoals QAOA op quantumapparatuur op korte termijn mogelijk worden gemaakt terwijl strikte prestatiegaranties worden behouden.

De kern

Stel je voor dat je probeert een enorm, ongelooflijk complex puzzel op te lossen. In de wereld van kwantumcomputing is deze puzzel vaak een optimalisatieprobleem: het vinden van de best mogelijke rangschikking van dingen (zoals de meest efficiënte bezorgroute of het beste beleggingsportefeuille).

Het artikel van Carrera Vazquez, Egger en Woerner introduceert een slimme nieuwe manier om deze puzzels aan te pakken met een kwantumcomputer, specifiek een die zich nog in de vroege, "ruisige" ontwikkelingsfase bevindt.

Hier is de uiteenzetting van hun idee met eenvoudige analogieën:

Het Probleem: De "Alle-handen-op-de-dek"-Schakeling

Traditioneel moet je, om deze puzzels op een kwantumcomputer op te lossen, een specifieke machine bouwen (een kwantumschakeling) waarbij elk enkel stukje van de puzzel tegelijkertijd met elk ander stukje praat.

• De Analogie: Stel je voor dat je een feestje organiseert waarbij 100 gasten allemaal tegelijkertijd met elke andere gast de hand moeten schudden. In een echte kamer is dit onmogelijk; mensen zouden tegen elkaar aanlopen, de kamer zou te vol zijn en het evenement zou mislukken.
• De Kwantumrealiteit: In kwantumspreuk vereist dit "all-to-all connectiviteit" en zeer diepe, complexe schakelingen. Huidige kwantumcomputers zijn als kleine kamers; ze kunnen niet zo veel gelijktijdige handdrukken aan zonder fouten (ruis) te maken.

De Oplossing: De "Receptenboek"-Aanpak (LCU)

De auteurs stellen een nieuwe strategie voor die Lineaire Combinatie van Unitaires (LCU) heet. In plaats van te proberen de onmogelijke "alle-handen"-machine te bouwen, breken ze de complexe taak op in een lijst met veel eenvoudigere, kleinere taken.

• De Analogie: In plaats van te proberen in één keer een gigantische, ingewikkelde bruiloftstaart te bakken (die zou kunnen instorten), bak je 100 simpele, kleine cupcakes.
  • Sommige cupcakes zijn vanille, sommige chocolade, sommige met hagelslag.
  • Je hebt geen gigantische oven nodig; je kunt ze één voor één of in kleine batches bakken.
  • Daarna meng je de resultaten samen op een bord. Als je ze in de juiste verhoudingen mengt, smaakt de "smaak" van het bord precies zoals de gigantische bruiloftstaart die je wilde.

In het artikel zijn deze "cupcakes" simpele kwantumschakelingen die alleen single-qubit-poorten vereisen (één persoon die de hand schudt met één andere persoon). Het "mengen" gebeurt klassiek (op een gewone computer) nadat het kwantumgedeelte is voltooid.

De Geheime Saus: De Fourier-transformatie

Hoe weten ze welke cupcakes ze moeten bakken en hoeveel ze van elk moeten mengen? Ze gebruiken een wiskundig hulpmiddel dat de Fourier-transformatie heet.

• De Analogie: Denk aan een complex lied. Een Fourier-transformatie breekt dat lied op in individuele noten (frequenties). De auteurs gebruiken dit om een complexe kwantum "lied" (de schakeling) op te breken in een reeks simpele, repetitieve noten (single-qubit rotaties).
• Het Resultaat: Ze kunnen een zeer moeilijke, complexe kwantumoperatie uitdrukken als een gewogen som van zeer eenvoudige operaties.

De Ruil: Kwaliteit versus Hoeveelheid

Er is een addertje onder het gras. Omdat je niet direct de gigantische machine bouwt, moet je het "cupcake"-experiment veel vaker uitvoeren om een betrouwbare antwoord te krijgen.

• De Analogie: Als je de gemiddelde lengte van een menigte wilt weten, kun je iedereen één keer meten (moeilijk te doen als ze allemaal bewegen). Of je kunt 10 willekeurige mensen meten, dan 10 meer, dan 10 meer, en het gemiddelde nemen. Je krijgt hetzelfde resultaat, maar je moet meer metingen doen.
• De Bewering van het Artikel: De auteurs tonen aan dat hoewel je de simpele schakelingen vaker moet draaien (een "sampling overhead"), het aantal extra runs beheersbaar is (polynomiaal), niet onmogelijk. Deze ruil stelt hen in staat om problemen op huidige hardware uit te voeren die anders onmogelijk zouden zijn.

Toepassing in de Wereld: De "Dichtste Subgraaf"

Om te bewijzen dat dit werkt, hebben ze het getest op een specifiek probleem genaamd de "Densest k-Subgraaf" (het vinden van de hechtste groep vrienden in een enorm sociaal netwerk).

1. Kleine Schaal: Ze simuleerden het op een 12-knooppunten graaf (zoals een kleine wijk) om te laten zien dat de wiskunde perfect werkt.
2. Grote Schaal: Ze draaiden het op een echte IBM kwantumcomputer met 106 qubits (een grote wijk).
   • Ze vonden succesvol oplossingen van hoge kwaliteit.
   • Ze vergeleken twee methoden: één die een "straf" gebruikte (zoals een boete voor het overtreden van regels) en één die een speciale "mixer" gebruikte (een regelvoldoende dans).
   • De Bevinding: De "mixer"-aanpak, gecombineerd met hun nieuwe Fourier-methode, werkte uitzonderlijk goed en vond oplossingen die bijna net zo goed waren als het theoretische beste, zelfs op echte, ruisige hardware.

De "Geen-Hulp"-Truc

Normaal gesproken heb je, om deze "cupcakes" samen te mengen, een extra helper-qubit (een "ancilla") nodig om de wiskunde bij te houden.

• De Innovatie: De auteurs ontwikkelden een manier om dit zonder de helper te doen.
• De Analogie: In plaats van een scheidsrechter nodig te hebben om je te vertellen welk team scoorde, laat je gewoon de spelers willekeurig spelen en kijk je daarna naar het scorebord om de winnaar te achterhalen. Dit verwijdert een enorme hoeveelheid complexiteit uit de kwantumschakeling, waardoor het veel vriendelijker is voor de machines van vandaag.

Samenvatting

Dit artikel presenteert een nieuwe manier om complexe kwantumoptimalisatie-algoritmes uit te voeren op de imperfecte hardware van vandaag. In plaats van te proberen een massieve, fragiele machine te bouwen die alles met alles verbindt, breken ze het probleem op in vele kleine, simpele stukjes, draaien ze die stukjes en combineren ze de resultaten klassiek.

Ze bewezen dat dit werkt door een moeilijk graafprobleem op te lossen op een 106-qubit kwantumcomputer, en lieten zien dat we vandaag grotere, complexere problemen kunnen oplossen door "schakelcomplexiteit" (hoe moeilijk de machine is om te bouwen) te ruilen voor "sampling overhead" (hoe vaak we de test moeten uitvoeren).

Technische samenvatting

Technische Samenvatting: Efficiënte Fourier-gebaseerde Lineaire Combinatie van Unitaire Operatoren en Toepassingen in Quantum-optimalisatie

Probleemstelling
Quantum-optimalisatiealgoritmes, met name het Quantum Approximate Optimization Algorithm (QAOA), staan voor aanzienlijke implementatiebarrières op hardware op korte termijn. De wiskundige structuur van optimalisatieproblemen, vooral die welke beperkingen omvatten (bijvoorbeeld kardinaliteitsbeperkingen), vereist vaak quantumcircuits met hoge connectiviteit (all-to-all interacties), grote circuitdieptes en talrijke twee-qubit-poorten. Deze vereisten overstijgen regelmatig de capaciteiten van huidige supergeleidende quantumprocessors. Hoewel strategieën zoals circuit-cutting of het benaderen van circuits bestaan, wisselen deze vaak oplossingskwaliteit in voor complexiteit of vereisen ze aanzienlijke sampling-overhead zonder strikte prestatiegaranties.

Methodologie
De auteurs stellen een Fourier-gebaseerde Lineaire Combinatie van Unitair Operatoren (LCU)-kader voor dat is ontworpen om complexe quantumcircuits te benaderen met behulp van ensemble's van eenvoudigere, hardware-vriendelijke circuits. De kernmethodologie omvat:

1. Ancilla-vrije LCU voor Sampling: In tegenstelling tot standaard LCU-implementaties die een ancilla-qubit gebruiken om een lineaire combinatie van unitaire operatoren coherent te implementeren (waarvoor gecontroleerde operaties nodig zijn), richt dit werk zich op sampling-gebaseerde toepassingen. Door de tekenfactoren die geassocieerd zijn met de quasi-kansdecompositie (QPD) te laten vallen en de ancilla te vervangen door klassieke willekeur, elimineert de methode de noodzaak van ancilla-qubits en gecontroleerde poorten. Dit transformeert de implementatie in een probabilistische mengeling van eenvoudigere circuits, waarbij de sampling-overhead wordt gekwantificeerd door een factor $\Gamma$.
2. Fourier-decompositie voor Diagonale Unitair Operatoren: Voor diagonale unitaire operatoren (vaak voorkomend in kostenfuncties en straftermen) maken de auteurs gebruik van de discrete Fourier-transformatie. Een doel-unitair $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ wordt ontleed in een lineaire combinatie van eenvoudigere unitaire operatoren $V(\theta_j)$, die vaak slechts lagen van enkel-qubit $R_Z$-poorten zijn. De coëfficiënten worden afgeleid uit de Fourier-transformatie van de functie die de unitaire operatie definieert. Deze benadering vervangt complexe multi-qubit-interacties (bijvoorbeeld kwadratische straffen die $O(n^2)$ poorten vereisen) door enkel-qubit-lagen, ten koste van een sampling-overhead $\Gamma \le m+1$.
3. Uitbreiding naar Niet-diagonale Permutatie-invariante Unitair Operatoren: Het kader wordt gegeneraliseerd naar niet-diagonale unitaire operatoren, zoals de volledig verbonden XY-mixer die wordt gebruikt om Hamming-gewichtbeperkingen te behouden. Door gebruik te maken van Schur-Weyl-dualiteit en de representatietheorie van $SU(2)$, drukken de auteurs permutatie-invariante unitaire operatoren uit als continue lineaire combinaties van collectieve enkel-qubit-rotaties $R(g)^{\otimes n}$. Dit maakt de implementatie van sterk niet-lokale mixers mogelijk met uitsluitend enkel-qubit-poorten, met een theoretische sampling-overhead die begrensd is door $O(n^3)$.
4. Verbinding met Lagrangiaanse Relaxatie: Het artikel vestigt een formele link tussen Fourier-gebaseerde quantumstraffen en klassieke Lagrangiaanse relaxatie. Het optimaliseren van één tak van de LCU-decompositie blijkt equivalent te zijn aan het optimaliseren van een Lagrangiaanse parameter, wat een verenigd perspectief biedt op het hanteren van beperkingen.

Belangrijkste Bijdragen

• Ontwikkeling van een Kader: Introductie van een ancilla-vrij, Fourier-gebaseerd LCU-kader dat brede klassen van diagonale en niet-diagonale unitaire operatoren ontleedt in ensemble's van lagen met enkel-qubit-poorten.
• Hardware-efficiëntie: Aantonen dat complexe, all-to-all verbonden operatoren (zoals kardinaliteitsstraffen en XY-mixers) kunnen worden vervangen door aanzienlijk eenvoudigere circuits, waarbij circuitdiepte en connectiviteit worden ingewisseld voor een polynomiale sampling-overhead.
• Theoretische Garanties: Verschaffen van strikte prestatiegrenzen, waarbij wordt aangetoond dat de kans op het samplen van bitstrings van hoge kwaliteit in de LCU-benadering ondergrens is door de coherente kans geschaald met $1/\Gamma$. Het artikel verbindt Conditional Value at Risk (CVaR)-optimalisatie ook aan deze grenzen.
• Validatie van Schaalbaarheid: Succesvolle toepassing van het kader op het dichtste $k$-subgraafprobleem op instanties tot 106 qubits op echte IBM Quantum-hardware, een schaal die voorheen onbereikbaar was voor volledig coherente implementaties van dergelijke beperkingen.

Experimentele Resultaten
De auteurs hebben hun benadering gevalideerd via exacte statevector-simulaties op een instantie met 12 knopen en grootschalige experimenten op een apparaat met 106 qubits:

• Simulatie met 12 Knopen: Vergelijkingen tussen volledig coherente QAOA en de Fourier-gebaseerde LCU-benadering toonden aan dat, hoewel de ruwe verwachtingswaarden van de LCU-circuits lager waren (vanwege de sampling-overhead), het optimaliseren van één LCU-basis-circuit (een variational ansatz afgeleid van de LCU) de hoogste kans opleverde om optimale oplossingen te samplen, en in specifieke metrics de coherente baseline overtrof.
• Hardware-experiment met 106 Knopen: Op een heavy-hex-grafiek met 106 qubits (uitgebreid via SWAP-lagen) werden de op straffen gebaseerde en de op XY-mixer gebaseerde LCU-benaderingen uitgevoerd. De resultaten toonden aan dat de praktische sampling-overhead aanzienlijk lager was dan de theoretische grenzen in het slechtste geval ($\Gamma \approx 10^4$). De single-branch LCU-ansatz vond succesvol oplossingen van hoge kwaliteit (tot 81 randen in de dichtste subgraaf) met haalbare kansen variërend van 2,7% tot 4,8%, wat de levensvatbaarheid van de methode voor grootschalige problemen aangeeft.
• XY-Mixer versus Straf: De op XY-mixer gebaseerde LCU-benadering presteerde over het algemeen beter dan de op straffen gebaseerde benadering, met name bij gebruik van één geoptimaliseerd basis-circuit, wat suggereert dat beperkingenbehoudende mixers effectiever zijn wanneer ze worden gecombineerd met deze decompositie.

Betekenis en Beweringen
Het artikel beweert dat het Fourier-gebaseerde LCU-kader een systematische route biedt om het praktische bereik van quantum-optimalisatie op korte termijn uit te breiden. Door complexe coherente operaties te vervangen door gewogen combinaties van eenvoudigere circuits, verbreedt de methode het scala aan probleeminstanties (met name die met globale beperkingen) dat op huidige hardware kan worden uitgevoerd. De auteurs benadrukken dat deze benadering geen exacte reproductie van de doelverdeling vereist, maar zich richt op het samplen van oplossingen van hoge kwaliteit, een doel dat goed past bij optimalisatietaken. Het werk suggereert dat de afweging tussen circuitcomplexiteit en sampling-overhead gunstig is, omdat theoretische grenzen in de praktijk vaak los zijn, en de methode het bestuderen van algoritmen en probleeminstanties mogelijk maakt die anders buiten de capaciteiten van de hardware zouden vallen. Het artikel concludeert dat dit een flexibel ontwerpprincipe biedt voor meer hardware-compatibele quantumalgoritmes, met name voor het hanteren van beperkingen in QAOA.