Sherrington-Kirkpatrick modellen med slumpmässiga ±1 kopplingar är programmerad på D-Wave Two annealer med 509 qubits interagerar på en Chimera-typ graf. Prestandan hos optimizern jämför och korrelerar till simulerad glödgning. När man överväger effekten av det statiska bruset, som försämrar prestandan hos annealern, kan man uppskatta en förbättring på den jämförande skalningen av de två metoderna till förmån för D-Wave maskinen. Det optimala valet av parametrar för inbäddning på Chimera grafen visas vara kopplat till uppkomsten av spin-glas kritiska temperaturen av det inbäddade problemet. NP-problem, såsom klassiska paradigmatiska datavetenskapliga problem [1] samt praktiska ingenjörsproblem [2] kan ofta formuleras effektivt som Quadratic Unconstrained Binary Optimizations (QUBO). Dessa beräkningsutmaningar kan ses som uppgiften att hitta marken tillstånd av en oordnad Ising spinnglas ofta definieras på en potentiellt starkt ansluten graf [3]. Ett lockande tillvägagångssätt för att lösa QUBOs i deras Ising formulering tillhandahålls av programmerbara kvant glödgning. Medan grundprinciperna för tekniken har undersökts numeriskt [4], analytiskt [5] och experimentellt [6] under det senaste årtiondet, gör den oordnade, interagerande, tidsberoende och öppna karaktären hos problemet med många kroppar det mycket svårt att dra universella slutsatser om teknikens kraft [7]. En mycket ny utveckling som stärkt vetenskaplig verksamhet inom detta område har varit kommersialiseringen av D-Wave Two optimizers, som implementerar glödgning tillvägagångssätt med hjälp av en solid stat arkitektur som består av hundratals sammanflätade supraledande flöde qubits [8]. Även om tillverkningsmetoderna och datortekniken är väldokumenterade är förståelsen av maskinens kraft en enorm utmaning av ovan nämnda skäl, med det ytterligare hindret att den tunga integrationen av kretsarna innebär förekomsten av statiska och dynamiska bullerkällor som delvis är okända. Av dessa skäl har grupper runt om i världen börjat att experimentellt jämföra maskinen [9-11], vårda en livlig diskussion om huruvida enheten gör funktionell användning av kvantmekanik för beräkning [12] och hur man korrekt mäta upphastigheter mellan olika beräkningsalgoritmer/experimental algoritmer [13, 14]. På en mer pragmatisk nivå testades chippet också för att utvärdera dess prestanda på leksaksproblem inom nätverksdiagnostik [15] [19]. En typisk förekomst i tillämpade problem är när QUBO som ska lösas är härledd från en linjär binär optimering problem med ett stort antal begränsningar såsom påtvingade equalities eller ojämlikheter mellan linjära relationer av variabler. I detta fall resulterar strafftermer i den objektiva funktionsformen skär kliquer vars minimering kan vara ett svårt beräkningsproblem för klassiska algoritmer såsom simulerad glödgning. Motiverad av det stora värdet av att kvantifiera effekten av kvantoptimering på värdefulla applikationer, i detta arbete rapporterar vi om de optimala programmeringsriktlinjer och prestandaförväntningar av D-Wave Two Vesuvius chip, tillämpas på problem som definieras på fullt anslutna grafer med slumpmässiga kopplingar i avsaknad av längsgående lokala fält. Denna Hamiltonian motsvarar Sherrington-Kirkpatrick Model (SKM) med kopplingar randomiserade från en bimodal fördelning av värden ±1 [20]. SKM är direkt relaterat till grafen partitionering problem [3] som är känd för att vara NP-hård, och stöder en spin-glas fas vid ändlig temperatur med tvärgående fält. Av dessa skäl utgör det en av de mest intressanta riktmärkena för att utvärdera optimizerns resultat när det gäller strukturerade problem. Dessutom har kodning av SKM på D-Wave hårdvara mycket intressanta symmetri egenskaper, vilket gör att vi elegant undersöka allmänna förfaranden som är gemensamma för alla strukturerade optimeringar på annealers, såsom parameter inställning av inbäddning och felkorrigering, som i det allmänna fallet kräver heuristiska numeriska förbehandling [21]. D-Wave Two "Vesuvius" chip värd på NASA Ames Research Center har 509 fungerande flödes-qubits ansluten av 1455 tonfiskble komposit qubits fungerar som Ising-interaktion kopplingar [22], arrangerade i en icke-planar lattice känd som en "Chimera graf" [23]. För att genomföra allmänna Hamiltonianer som definieras på godtyckliga grafer, är det brukligt att använda graf-minor inbäddning [24] teknik. Detta förfarande består av att hitta en uppsättning anslutna subgrafer (logiska bitar eller LB, motsvarande olika färger i Bild. 1 ) av den ursprungliga grafen sådan att varje LB kan associeras till en nod arXiv:1406.7553v1 [cond-mat.dis-nn]
Av särskild betydelse är arbetet med optimering av fullt anslutna grafer, såsom de som används för att kartlägga ML problem REF ; vars resultat visade att QA prestanda kan matcha den mest optimerade simulerade glödlampan körs på de senaste Intel processorer.
Quantum Optimization of Fully-Connected Spin Glasses
{'venue': 'Phys. Rev. X 5, 031040 (2015)', 'journal': None, 'mag_field_of_study': ['Physics']}