The Complexity of Stoquastic Sparse Hamiltonians

Dit artikel stelt vast dat het probleem van stoquastische schaarse Hamiltonianen $\mathsf{StoqMA}$-compleet is en dat de separabele versie daarvan $\mathsf{StoqMA}(2)$-compleet is, waardoor het begrip van de kracht van de $\mathsf{StoqMA}$-complexiteitsklasse wordt bevorderd.

De kern

Het Grote Plaatje: De "Energie"-puzzel

Stel je een gigantische, complexe machine voor die bestaat uit duizenden kleine schakelaars (quantumbits, of qubits). Deze machine heeft een specifieke "grondtoestand", wat vergelijkbaar is met zijn rustpositie of zijn laagste energiestand.

In de wereld van de kwantumfysica is het ontzettend moeilijk om precies uit te rekenen wat die laagste energiestand is voor een complexe machine. Het is alsof je probeert het absolute laagste punt te vinden in een uitgestrekt, mistig berglandschap zonder kaart. Computerwetenschappers noemen dit het Lokale Hamiltoniaan-probleem.

Meestal is dit probleem zo moeilijk dat het behoort tot een klasse van problemen die QMA (Quantum Merlin-Arthur) wordt genoemd. Denk aan QMA als een spel waarbij een machtige tovenaar (Merlin) een sceptische rechter (Arthur) probeert te overtuigen dat hij het laagste punt heeft gevonden. De rechter kan het antwoord van de tovenaar controleren met een quantumcomputer.

Het Speciale Geval: "Stoquastische" Machines

Het artikel richt zich op een speciaal type machine dat een Stoquastische Hamiltoniaan wordt genoemd.

• De Analogie: Stel je een normale machine voor waarbij de schakelaars op verwarrende, negatieve manieren kunnen duwen of trekken (zoals een touwtrekken waarbij het touw door een muur loopt). Dit veroorzaakt een "tekenprobleem" dat ervoor zorgt dat klassieke computers (zoals je laptop) falen bij het simuleren ervan.
• Het Stoquastische Verschil: Een stoquastische machine is "vriendelijk". Al zijn schakelaars duwen of trekken op een manier die alles positief houdt. Er zijn geen verwarrende negatieve tekens. Hierdoor kunnen klassieke computers ze veel beter simuleren met methoden zoals Monte Carlo-simulaties (willekeurig gokken dat na verloop van tijd slimmer wordt).

Hoewel deze machines "vriendelijker" zijn, is het nog steeds moeilijk om hun laagste energie te bepalen. Het blijkt dat dit specifieke probleem behoort tot een klasse die StoqMA wordt genoemd. Dit is een middenklasse tussen standaard klassiek gokken (MA) en geavanceerder klassiek gokken (AM).

De Hoofdontdekking: Sparsiteit versus Localiteit

De auteurs wilden StoqMA beter begrijpen. Om dit te doen, keken ze naar een specifiek type machine: Spaarzame Hamiltonianen.

• Lokale Hamiltonianen: Stel je een machine voor waarbij elke schakelaar alleen met zijn directe buren praat (zoals mensen in een rij die alleen met de persoon naast hen praten).
• Spaarzame Hamiltonianen: Stel je een machine voor waarbij een schakelaar met iedereen in de kamer kan praten, maar elke schakelaar praat alleen met een zeer klein, vast aantal mensen (zeg maar 10 mensen uit een miljoen). Het is "spaars" omdat de meeste verbindingen leeg zijn.

De Bewering van het Artikel:
De auteurs bewezen dat het bepalen van de laagste energie van deze "Spaarzame" machines exact even moeilijk is als die van de "Lokale" machines.

• Het Resultaat: Het probleem van de "Stoquastische Spaarzame Hamiltoniaan" is StoqMA-compleet.
• Wat dit betekent: Als je de spaarzame versie efficiënt kunt oplossen, kun je ook de lokale versie oplossen, en andersom. Ze zijn even moeilijk. Dit is verrassend omdat spaarzame machines veel algemener en flexibeler zijn dan lokale, maar ze worden in deze specifieke quantumcontext niet "makkelijker" op te lossen.

Hoe Ze Het Dedden: De "Hadamard"-test

Om dit te bewijzen, moesten de auteurs een nieuwe manier bedenken voor de rechter (Arthur) om het antwoord van de tovenaar (Merlin) te controleren.

• Het Probleem: De gebruikelijke manier om energie te controleren, vereist complexe quantumwiskunde (Fasenschatting) die de "Stoquastische" rechter niet mag uitvoeren, omdat hun gereedschap te simpel is (ze kunnen geen "negatieve" wiskunde aan).
• De Oplossing: De auteurs bedachten een slimme truc. Ze splitsten de grote machine op in tiny, enkelvoudige verbindingsstukjes (1-spaarzame termen). Vervolgens creëerden ze een "Hadamard-achtige" test.
  • De Metafoor: Stel je voor dat de rechter de tovenaar vraagt een munt vast te houden. De rechter schakelt een schakelaar die de munt willekeurig verbindt met een specifieke buur. De rechter controleert vervolgens of de munt op een specifieke manier is geland. Door dit vele malen te doen met verschillende willekeurige verbindingen, kan de rechter de totale energie van de machine berekenen zonder een volledige quantum-supercomputer nodig te hebben.

De "Scheidbare" Twist: Twee Tovenaars, Geen Telepathie

Het artikel keek ook naar een variatie die de Scheidbare Stoquastische Spaarzame Hamiltoniaan wordt genoemd.

• Het Scenario: Stel je voor dat de machine in twee helften is verdeeld (Links en Rechts). De rechter wil de laagste energie weten, maar met een regel: De tovenaar moet twee aparte, niet-verstrengelde antwoorden geven (één voor de Linkerhelft, één voor de Rechterhelft). Ze kunnen geen "quantum-telepathie"-link (verstrengeling) tussen hen delen.
• Het Resultaat: De auteurs toonden aan dat dit specifieke probleem StoqMA(2)-compleet is.
  • StoqMA(2) is een klasse waarbij de rechter twee niet-verstrengelde tovenaars krijgt.
  • Dit is een grote zaak, omdat het laat zien dat zelfs als je de tovenaars dwingt apart te werken (geen quantum-samenwerking), het probleem even moeilijk blijft als het algemene geval.

De Regel "Twee Tovenaars zijn Genoeg"

Tot slot vroegen de auteurs zich af: "Wat als we drie tovenaars hebben, of tien tovenaars? Wordt het werk van de rechter dan makkelijker of moeilijker?"

• De Bevinding: Ze bewezen dat voor dit specifieke type quantumspel, twee tovenaars genoeg zijn.
• De Analogie: Zelfs als je een team van 100 tovenaars hebt die proberen de rechter te overtuigen, kan de rechter het hele team simuleren door gewoon twee van hen te vragen exact hetzelfde bericht te sturen en te controleren of ze de waarheid spreken. Je hebt niet meer dan twee nodig om de volledige kracht van het systeem te vangen.

Samenvatting

1. Stoquastische machines zijn een speciaal, "vriendelijker" type quantummachine dat het "tekenprobleem" vermijdt.
2. De auteurs bewezen dat het vinden van de laagste energie van Spaarzame stoquastische machines even moeilijk is als het vinden ervan voor Lokale machines. Beide zijn StoqMA-compleet.
3. Ze ontwikkelden een nieuwe testmethode die het een beperkte rechter mogelijk maakt om deze energieën te verifiëren zonder volledige quantumkracht nodig te hebben.
4. Ze toonden aan dat zelfs als je de machine in tweeën deelt en de tovenaars dwingt apart te werken, het probleem moeilijk blijft (StoqMA(2)-compleet).
5. Ze bewezen dat het hebben van meer dan twee niet-verstrengelde tovenaars je geen extra kracht geeft; twee zijn voldoende om elk aantal van hen te simuleren.

Dit werk helpt het landschap van quantumcomplexiteit in kaart te brengen, en laat precies zien waar de "moeilijke" problemen leven en hoe verschillende soorten quantummachines met elkaar samenhangen.

Technische samenvatting

Probleemstelling

Het artikel behandelt de computationele complexiteit van het Stoquastic Sparse Hamiltonian (StoqSH)-probleem. Hoewel de complexiteit van lokale stoquastische Hamiltonianen goed begrepen is (bekend als StoqMA-volledig), was de complexiteit van sparse stoquastische Hamiltonianen niet direct vastgesteld.

Sparse Hamiltonianen vormen een bredere klasse dan lokale Hamiltonianen; een $k$-lokale Hamiltoniaan met $m$ termen is $2^{km}$-sparse. Het StoqSH-probleem vraagt, gegeven een $d$-sparse stoquastische Hamiltoniaan $H$ (waarbij niet-diagonale elementen niet-positief zijn) en parameters $\alpha, \beta$, of de grondtoestandsenergie $\lambda_{\min}(H) \le \alpha$ of $\lambda_{\min}(H) \ge \beta$, met de belofte dat één van deze gevallen geldt.

De centrale uitdaging is dat standaardtechnieken voor het bewijzen van opname in StoqMA voor lokale Hamiltonianen (die vertrouwen op het omzetten van lokale termen in specifieke projecties) niet uitbreiden naar de sparse setting. Bovendien zijn standaard quantumverificatiemethoden zoals Fase-schatting (gebruikt voor algemene sparse Hamiltonianen in QMA) inherent quantum en kunnen niet worden gesimuleerd door de beperkte stoquastische verifiers, die beperkt zijn tot klassieke reversible circuits en metingen in de Hadamard-basis.

Methodologie

De auteurs hanteren een verificatieprocedure die de kloof overbrugt tussen de structuur van sparse Hamiltonianen en de beperkingen van stoquastische verifiers. De methodologie bestaat uit drie hoofdbestanddelen:

1. Sparse Decompositie:
   De auteurs maken gebruik van een bekende decompositie (uit [BCC+14]) waarbij elke $d$-sparse Hamiltoniaan $H$ kan worden geschreven als een som van $d^2$ 1-sparse termen ($H = \sum H_j$). Cruciaal is dat, als $H$ stoquastisch is, elke term $H_j$ in deze decompositie ook stoquastisch is, en dat de niet-nul matrixelementen uniek worden toegewezen aan specifieke termen.

2. Gegeneneraliseerde StoqMA-verifiers (gStoqMA):
   Om de verificatie te hanteren, introduceren de auteurs een generalisatie van de StoqMA-verifier. Standaard StoqMA-verifiers meten een enkele qubit in de Hadamard-basis. De auteurs definiëren gStoqMA, waarbij de verifier een polynomiaal aantal qubits kan meten in de Hadamard-, $|0\rangle$- of $|1\rangle$-basissen.

   • Zij bewijzen dat deze generalisatie de computationele kracht van de klasse niet verhoogt; deze kan worden gesimuleerd door een standaard StoqMA-verifier met een lineair verlies in de gap tussen volledigheid en geluid (Stelling 1.2). Dit maakt het gebruik van multi-qubit-metingen (specifiek Swap-tests) binnen het stoquastische kader mogelijk.

3. Verificatieprocedure voor StoqSH:
   De kernbijdrage is een verificatieprotocol voor StoqSH dat een getuigestaat $|\psi\rangle$ accepteert met een waarschijnlijkheid die lineair gerelateerd is aan de energie-verwachting $\langle \psi | H | \psi \rangle$. De verifier kiest willekeurig tussen twee sub-procedures ($V_1$ en $V_2$):

   • Procedure $V_1$: Gebruikt de oracle voor de matrixelementen van de Hamiltoniaan om een staat te construeren die afhankelijk is van $|\psi\rangle$ en de 1-sparse term $H_j$. Het voert een "Hadamard-achtige" test uit die een gecontroleerde oracle-query en metingen in de $X$- en $Z$-basissen omvat. De acceptatiekans relateert zich aan de niet-diagonale elementen en de energie.
   • Procedure $V_2$: Een complementaire procedure die de laatste qubit meet in de $Z$-basis.
   • Gecombineerd Resultaat: Door de acceptatiekansen van $V_1$ en $V_2$ te middelen, wordt de totale acceptatiekans $1/2 - \frac{1}{4d^2}\langle \psi | H | \psi \rangle$. Deze lineaire relatie stelt de verifier in staat om te onderscheiden tussen lage-energie (JA) en hoge-energie (NEE) instanties.

Belangrijkste Bijdragen en Resultaten

1. StoqMA-volledigheid van StoqSH
Het primaire resultaat is Stelling 1.1, die stelt dat het Stoquastic Sparse Hamiltonian-probleem StoqMA-volledig is.

• Hardheid: Volgt onmiddellijk omdat lokale stoquastische Hamiltonianen een speciaal geval zijn van sparse stoquastische Hamiltonianen en al bekend zijn als StoqMA-hard.
• Opname: Vastgesteld via de hierboven beschreven verificatieprocedure, bewijzend dat StoqSH $\in$ StoqMA.

2. Separeerbare Stoquastische Sparse Hamiltonianen en StoqMA(2)
De auteurs breiden hun analyse uit naar het Separeerbare Stoquastische Sparse Hamiltonian (SepStoqSH)-probleem, waarbij de getuige beperkt is tot een productstaat $|\psi\rangle = |\chi_A\rangle \otimes |\chi_B\rangle$.

• Zij definiëren StoqMA(k), het stoquastische analogon van QMA(k), waarbij $k$ niet-verstrengelde bewerkers betrokken zijn.
• Stelling 1.4 (Vereenvoudigd): Zij tonen aan dat voor bepaalde volledigheids- en geluidsparameters, $k$ bewerkers kunnen worden gesimuleerd door 2 bewerkers ($StoqMA(k) \subseteq StoqMA(2)$). Het bewijs past het "Product Test"-protocol uit [HM13] aan op de stoquastische setting, gebruikmakend van het vermogen van stoquastische verifiers om multi-qubit-metingen uit te voeren (via de gStoqMA-generalisatie).
• Stelling 4.5: Het SepStoqSH-probleem is StoqMA(2)-volledig. Het bewijs van hardheid past de circuit-naar-Hamiltoniaan-constructie voor separeerbare sparse Hamiltonianen [CS12] aan op de stoquastische setting, gebruikmakend van perturbatietheorie om het gebrek aan foutversterking in StoqMA(2) op te vangen.

3. Generalisatie van StoqMA
Het artikel introduceert gStoqMA en bewijst dat het toestaan van metingen van polynomiale grootte de kracht van de klasse niet verhoogt buiten een parameterverplaatsing (Stelling 3.5). Deze eigenschap wordt geïdentificeerd als potentieel van onafhankelijk belang voor de studie van stoquastische bewijssystemen.

Betekenis en Beweringen

Het artikel claimt de kennis van de StoqMA-complexiteitsklasse te bevorderen, die ligt tussen de gerandomiseerde klassen MA en AM ($NP \subseteq MA \subseteq StoqMA \subseteq AM$).

• Volledigheid: Door StoqSH te identificeren als een volledig probleem voor StoqMA, bieden de auteurs een meer algemeen natuurlijk probleem voor deze klasse, verder gaand dan beperkte lokale modellen.
• Separeerbare Bewijzen: Het werk plaatst StoqMA(2) als een interessant intermediair model tussen single-prover stoquastische verificatie en algemene multi-prover quantumverificatie. Het biedt een natuurlijk volledig probleem (SepStoqSH) voor StoqMA(2), analoog aan de rol van separeerbare sparse Hamiltonianen voor QMA(2).
• Robuustheid: De resultaten suggereren dat de kracht van stoquastische verifiers robuust is, zelfs wanneer de getuige beperkt is tot sepereerbaar te zijn, mits de Hamiltoniaan sparse is.

De auteurs merken op dat hoewel zij tonen dat StoqMA(k) instort tot StoqMA(2) voor specifieke parameters, de robuustheid van deze instorting onder strakkere foutgrenzen een open vraag blijft. Bovendien blijft de complexiteit van het Separeerbare Stoquastische Lokale Hamiltonian-probleem open, aangezien huidige technieken voor lokale dichtheidsmatrixconsistentie niet direct van toepassing zijn op de stoquastische setting.

Samenvattend vestigt het artikel de computationele hardheid van sparse stoquastische Hamiltonianen, introduceert een nieuwe verificatietechniek die gebruik maakt van multi-qubit-metingen, en karakteriseert de kracht van stoquastische bewijssystemen met meerdere niet-verstrengelde bewerkers.