Counting with the quantum alternating operator ansatz

Dit artikel introduceert VQCount, een variatieel algoritme op basis van de Quantum Alternating Operator Ansatz dat het aantal benodigde steekproeven voor het benaderen van #P-moeilijke telproblemen exponentieel verlaagt en een empirisch efficiëntie-voordeel toont ten opzichte van bestaande methoden.

De kern

Het Grote Tellen met Quantum-magie: Een Reis met VQCount

Stel je voor dat je een enorme bibliotheek binnenloopt. Deze bibliotheek bevat niet gewoon boeken, maar miljoenen verschillende puzzels. Je taak is niet om één specifieke oplossing te vinden, maar om precies te tellen hoeveel oplossingen er voor elke puzzel mogelijk zijn.

In de wereld van computers is dit een nachtmerrie. Voor sommige puzzels (zoals het bepalen of een ingewikkelde zin waar of onwaar is) is het tellen van alle mogelijke oplossingen zo moeilijk, dat zelfs de snelste supercomputers van vandaag de dag er eeuwen voor nodig zouden hebben. Dit noemen wetenschappers een #P-hard probleem. Het is alsof je probeert elk mogelijk pad in een doolhof te vinden, terwijl het doolhof elke seconde groter wordt.

De auteurs van dit artikel, Julien, Shreya en Stefanos, hebben een nieuwe manier bedacht om dit probleem aan te pakken met behulp van kwantumcomputers. Ze noemen hun nieuwe methode VQCount.

1. Het Probleem: Het Doolhof van de Mogelijkheden

Stel je voor dat je een doolhof hebt met 100 ingangen. Je wilt weten hoeveel uitgangen er zijn.

• De oude manier (Klassieke computers): Je loopt elke weg één voor één af. Als je een doodlopende weg vindt, ga je terug. Als er miljarden wegen zijn, duurt dit te lang.
• De quantum-methode (VQCount): In plaats van één voor één te lopen, laat je een "quantum-spook" door alle wegen tegelijk lopen. Maar hier zit een addertje onder het gras: dit spook is niet perfect. Soms loopt het spook sneller door de goede wegen dan door de slechte, of soms verdwaalt het in de verkeerde gangen.

2. De Oplossing: Een Slimme Gids (JVV)

De auteurs gebruiken een slimme truc uit de wiskunde, bedacht door drie andere wetenschappers (Jerrum, Valiant en Vazirani, of kortweg JVV).

Stel je voor dat je niet het hele doolhof in één keer wilt tellen. In plaats daarvan bouw je het doolhof stap voor stap op:

1. Kijk eerst naar de eerste ingang: "Is er een oplossing als we linksaf slaan?"
2. Kijk daarna: "En als we rechtsaf slaan?"
3. Herhaal dit voor elke volgende afslag.

Als je kunt willekeurig een oplossing vinden in een klein stukje van het doolhof, kun je met wiskunde de totale hoeveelheid oplossingen voor het hele doolhof berekenen. Het geheim is: je hebt een eerlijke gids nodig die je met gelijke kans naar elke mogelijke oplossing stuurt.

3. De Quantum-motor: QAOA

Hier komt hun nieuwe motor, VQCount, om de hoek kijken. Ze gebruiken een quantum-algoritme genaamd QAOA als die gids.

Ze hebben twee soorten gidsen getest:

• De snelle, maar onvoorspelbare gids (Gewone QAOA): Deze gids is snel en vindt vaak een oplossing, maar hij is niet eerlijk. Hij houdt van bepaalde wegen en negeert andere. Hij is als een hond die graag naar de buren loopt, maar niet naar de achtertuin.
• De eerlijke, maar trage gids (GM-QAOA): Deze gids is geweldig eerlijk. Hij stuurt je met exact dezelfde kans naar elke mogelijke oplossing. Maar hij is traag en heeft veel energie nodig om zijn werk goed te doen.

4. De Grote Ontdekking: De Perfecte Balans

De auteurs ontdekten iets fascinerends: Je hoeft niet altijd de perfecte, eerlijke gids te hebben.

In hun experimenten zagen ze dat de "snelle, onvoorspelbare gids" (de gewone QAOA) vaak beter werkte dan de "eerlijke, trage gids", zelfs als hij niet helemaal eerlijk was.

• De Analogie: Stel je voor dat je een grote stapel kaarten moet tellen.
  • De eerlijke gids sorteert ze perfect, maar hij doet er een uur over om één stapel te maken.
  • De snelle gids gooit ze wat slordig op elkaar, maar hij is 10 keer sneller.
  • De auteurs ontdekten dat als je de snelle gids een paar keer laat werken en de resultaten slim combineert, je alsnog een heel nauwkeurig totaalbedrag krijgt, en dat veel sneller dan met de perfecte gids.

Ze noemen dit een afweging (trade-off). Je ruilt een beetje "eerlijkheid" in voor veel "snelheid".

5. De Resultaten: Wat betekent dit voor de wereld?

Ze hebben hun methode getest op twee heel moeilijke puzzels (genaamd #NAE3SAT en #1-in-3SAT).

• Het goede nieuws: Hun methode, VQCount, is exponentieel beter dan eerdere quantum-methoden. Ze hebben minder "pogingen" nodig om een goed antwoord te krijgen.
• Het realistische nieuws: Hoewel het veel beter is dan voorheen, is het nog steeds niet sneller dan de allerbeste klassieke computers die we nu hebben voor deze specifieke puzzels. Het is alsof je een nieuwe, snellere fiets hebt gebouwd, maar de auto is nog steeds sneller.

Maar: De fiets wordt elke dag sneller naarmate de quantum-computers groter en krachtiger worden.

Conclusie: Waarom is dit belangrijk?

Dit artikel laat zien dat we quantum-computers niet alleen kunnen gebruiken om één antwoord te vinden (zoals in een spelletje), maar ook om statistieken en waarschijnlijkheden te berekenen.

Het is als het verschil tussen:

• "Is er een weg naar de schat?" (Ja/Nee-vraag)
• "Hoeveel wegen zijn er naar de schat?" (Telling-vraag)

De auteurs hebben bewezen dat quantum-computers potentieel hebben om dit tweede, veel moeilijkere probleem op te lossen. Ze hebben een brug gebouwd tussen de theorie en de praktijk. Hoewel de brug nog niet klaar is voor zware vrachtwagens (grote, echte problemen), is het een solide start voor de toekomst.

Kort samengevat: Ze hebben een slimme quantum-methode bedacht die een beetje "slordig" mag zijn, zolang hij maar snel genoeg is. Hierdoor kunnen we in de toekomst waarschijnlijk veel sneller complexe berekeningen maken over risico's, netwerken en kunstmatige intelligentie.

Technische samenvatting

Titel: Tellende met de Quantum Alternating Operator Ansatz (VQCount)

Auteurs: Julien Drapeau, Shreya Banerjee en Stefanos Kourtis (Universiteit van Sherbrooke).

---

1. Het Probleem: #P-Harde Telproblemen

Het artikel richt zich op telproblemen (counting problems), specifiek het tellen van het aantal oplossingen voor een gegeven instantie van een beslissingsprobleem. Deze problemen behoren tot de complexiteitsklasse #P, die hoger ligt dan de bekende NP-optimatieproblemen.

• Uitdaging: Voor #P-harde problemen (zoals het tellen van oplossingen voor SAT-formules) is het onwaarschijnlijk dat er exacte polynomiale algoritmen bestaan.
• Bestaande methoden:
  • Exacte telling: Gebruikt technieken zoals tensornetwerken en component-caching, maar is beperkt tot enkele honderden variabelen.
  • Benaderende telling: Bestaat uit hash-gebaseerde methoden (die een NP-orakel nodig hebben) en steekproefgebaseerde methoden (random sampling).
• De kloof: Variational Quantum Algorithms (VQA's), zoals QAOA, worden veel gebruikt voor optimalisatie, maar hun toepassing op tellen is lastig. Eerdere pogingen vereisten superpolynomiale aantallen metingen om een nauwkeurige schatting te krijgen, vooral omdat QAOA-circuits vaak niet-uniforme verdelingen van oplossingen genereren.

2. Methodologie: VQCount en de JVV-Link

De auteurs introduceren VQCount, een variational quantum algoritme voor benaderende telling. De kern van de methode is de koppeling tussen benaderende telling en uniforme steekproeven, gebaseerd op het beroemde Jerrum-Valiant-Vazirani (JVV) algoritme.

De werking van VQCount:

1. JVV-principe: Als oplossingen voor een "zelf-reduceerbaar" probleem (zoals SAT) voldoende uniform kunnen worden gestreamd, kan het totale aantal oplossingen benaderd worden door conditionele kansen te schatten langs een zelf-reductieboom (waarbij variabelen één voor één worden vastgezet).
2. QAOA als Sampler: In plaats van een klassieke sampler, gebruikt VQCount de output van een Quantum Alternating Operator Ansatz (QAOA) circuit als de generator voor oplossingen.
3. Varianten:
   • GM-QAOA (Grover-mixer): Garandeert dat alle oplossingen in de superpositie exact dezelfde amplitude hebben (perfecte uniformiteit, $\eta=0$). Dit voldoet strikt aan de JVV-theorie, maar vereist diepere circuits om een hoge succeskans te bereiken.
   • Standaard QAOA: Gebruikt een standaard mixer (bijv. $H_X$). Dit is efficiënter in diepte (on dieper circuits nodig) maar produceert een niet-uniforme verdeling van oplossingen.
4. Het Algoritme:
   • Het algoritme optimaliseert QAOA-parameters om de energie van het probleem-Hamiltoniaan te minimaliseren.
   • Het voert een zelf-reductie uit: het kiest een variabele, schat de kans dat deze 0 of 1 is (gebaseerd op gemeten oplossingen), en "fixeert" de variabele op de meest waarschijnlijke waarde.
   • Het circuit wordt aangepast voor de subproblemen (door Hadamard-gates te vervangen door vaste $X$-gates).
   • Het totale aantal oplossingen wordt geschat door de product van deze conditionele kansen.

3. Belangrijkste Bijdragen

• Exponentiële Verbetering in Steekproefcomplexiteit: De auteurs bewijzen dat VQCount, wanneer het werkt met een succeskans $r$, slechts $O(\frac{n^2 \log(1/\delta)}{r \epsilon^2})$ steekproeven nodig heeft voor een benadering binnen een multiplicative factor $\epsilon$. Dit is een exponentiële verbetering ten opzichte van eerdere VQA-werkzaamheden voor tellen (zoals die van Sundar et al.), die $O(\sqrt{N})$ steekproeven vereisten.
• Trade-off Analyse: Ze identificeren en kwantificeren een fundamentele afweging tussen steekproef-efficiëntie (succeskans) en steekproef-uniformiteit.
  • GM-QAOA is uniform maar heeft een lage succeskans (vereist diepere circuits).
  • Standaard QAOA heeft een hogere succeskans op ondiepe circuits maar is niet-uniform.
• Empirische Validatie: Ze tonen aan dat de niet-uniformiteit van standaard QAOA niet fataal is voor de nauwkeurigheid van de telling, mits de succeskans hoog genoeg is.

4. Resultaten en Simulaties

De auteurs gebruikten tensornetwerk-simulaties (met de bibliotheek quimb) om VQCount te testen op twee #P-harde problemen: positief #NAE3SAT en positief #1-in-3SAT.

• Prestaties op #NAE3SAT:
  • Bij een lage dichtheid van clausules ($\alpha=1$) presteren QAOA en GM-QAOA vergelijkbaar in termen van het totale aantal benodigde steekproeven.
  • Bij een hoge dichtheid ($\alpha=2$, dichter bij de moeilijkheidsdrempel) presteert standaard QAOA aanzienlijk beter dan GM-QAOA. Hoewel QAOA niet-uniform is, is de veel hogere succeskans (minder post-selectie nodig) doorslaggevend.
  • De benodigde steekproeven groeien exponentieel met het aantal variabelen, maar de exponent is gunstiger dan bij naïeve afwijzing (rejection sampling).
• Prestaties op #1-in-3SAT:
  • Voor dit probleem (een "locked" probleem) toont VQCount met ondiepe QAOA-circuits een schaling die beter is dan naïeve afwijzing en vergelijkbaar is met de BHMT (Brassard-Høyer-Mosca-Tapp) quantum counting algoritme.
  • De schaling is echter nog steeds slechter dan de beste klassieke exacte solvers (zoals tensornetwerk-contractie) voor de huidige probleemgroottes.
• Diepte vs. Uniformiteit:
  • Naarmate de circuitdiepte ($p$) toeneemt, stijgt de succeskans, maar neemt de uniformiteit van QAOA af (de verdeling wordt scheef).
  • GM-QAOA behoudt perfectie in uniformiteit, maar de succeskans daalt sneller bij toenemende probleemgrootte.

5. Betekenis en Conclusie

• Potentieel: VQCount demonstreert dat variational quantum algoritmen een veelbelovende route zijn voor benaderende telling van #P-harde problemen, met een theoretische en empirische winst in steekproefficiëntie ten opzichte van eerdere quantum-methoden.
• Praktische Toepassing: Het algoritme is geschikt voor "Noisy Intermediate-Scale Quantum" (NISQ) hardware omdat het werkt met ondiepe circuits.
• Beperkingen:
  • De huidige schaling is nog niet concurrerend met de state-of-the-art klassieke algoritmen voor exacte telling.
  • Er is een afweging nodig tussen circuitdiepte (voor succes) en uniformiteit (voor theoretische garanties).
• Toekomst: De auteurs suggereren dat verdere verbeteringen mogelijk zijn door "warm-start" strategieën, probleem-bewuste mixers, en geavanceerde post-processing om de kosten van post-selectie te verlagen.

Kortom, het artikel levert een solide framework voor het gebruik van quantum circuits als steekproefmachines voor tellen, waarbij het de theoretische garanties van het JVV-algoritme combineert met de praktische haalbaarheid van variational quantum circuits.