Vi introducerar en algoritm för att generera (inte lösa) spin-glas instanser med planterade lösningar av godtycklig storlek och struktur. Först löses en uppsättning små problemlappar med öppna gränser antingen exakt eller med en heuristisk, och sedan sys de enskilda fläckarna ihop för att skapa ett stort problem med en känd planterad lösning. Eftersom i dessa problem frustration är typiskt mindre än i slumpmässiga problem, vi först bedöma den typiska beräkning komplexiteten hos de enskilda patchar med hjälp av befolkning glödgning Monte Carlo, och införa en metod som gör det möjligt att finjustera den typiska beräknings komplexiteten i det lappplanterade systemet. Skalan av den typiska beräknings komplexiteten hos dessa planterade fall med olika antal patchar och patchstorlekar undersöks och jämförs med slumpmässiga fall. PACS nummer: 75.50.Lk, 75.40.Mg, 05.50.+q, Många optimeringsproblem tillhör NP-hård komplexitet klass, som man tror att inga algoritmer finns för att lösa dem i polynom tid. Spin-glas problem utan förutfattade meningar och på icke-planar topologier, såsom EdwardAnderson (EA) modell [1], representerar en underklass av NPhard klassen. Eftersom spinnglasögon är de enklaste modellerna med både oordning och frustration som faller in i NP-hårda klassen, representerar de de idealiska modellsystemen för att jämföra algoritmer, samt nya datorarkitekturer. Ett antal heuristiker, såväl som uttömmande sökmetoder, har utformats och utvecklats för att minimera spin-glass Hamiltonianer så effektivt som möjligt. Denna metod omfattar också simulerad glödgning [2], parallell härdning Monte Carlo [3] [4] [5] [6] [6], population glödgning Monte Carlo [7] [8] [9] [10], och genetiska algoritmer [11, 12], liksom gren-och-klippta [13] algoritmer, för att nämna några. Många av dessa optimeringsalgoritmer använder endast lokala uppdateringar under minimeringsprocessen. I många fall kan dock användningen av klusteralgoritmer med icke-lokala uppdateringar avsevärt förbättra sökprocessen när energilandskapet har många metastabila tillstånd med liten överlappning [14] [15] [16]. Under de senaste två decennierna har kvantheuristik föreslagits som ett alternativ till klassisk heuristik, på grund av deras potential att utnyttja kvantöverläge och kvanttunneleffekter. Bland kvantmetoder används ofta adiabisk kvantoptimering (AQO) [17] [18] [19] [20] [20] [21] [23] [24] [25] [26] [27] [28] [29] [30]] och troligen den metod som är mest mottaglig för maskinvaruimplementeringar [31]. Nuvarande state-of-the-art AQO hårdvara tillverkas av D-Wave System Inc., vars senaste chip möjliggör kvantoptimering av problem på ungefär upp till 2000 variabler. Huruvida AQO kan vara effektivare än klassiska algoritmer för vissa problem är dock fortfarande kontroversiellt [32] [33] [34]. Med tanke på vikten av att jämföra optimeringsmetoder mellan olika discipliner, är det nödvändigt att ha referensproblem som är (1) representativa för hårdheten hos ett typiskt NP-hårda problem, (2) skalbara för stora system, och för vilka (3) marktillståndet är känt a priori. Även om det är lätt att uppfylla kriterierna (1) och (2) är det utmanande att ha stora FIG. 1: Schematisk diagram över patch planteringsmetod för en tvådimensionell lattice. För det första beräknas marktillståndet för varje (lätt solvable) patch (A-D) med hjälp av fria gränsförhållanden. Därefter väljs en marktillståndskonfiguration för varje plåster. Kanten snurrar mellan patchar representeras av tomma och fullständiga cirklar. Kopplingar mellan kanten snurrar mellan angränsande patchar läggs till under förutsättning att alla interaktioner är nöjda, dvs. om två spins har samma värde (dvs. både fulla eller båda tomma cirklar), ett ferromagnetiskt koppel (straight blå linje) läggs till. Om dock två intilliggande spins är olika, då ett antiferromagnetiskt koppel (röd wiggly linje) läggs till. Den direkta produkten av marken tillstånd av patchar A-D är sedan marken tillstånd av det stora planterade systemet. problem med kända lösningar. Det har funnits tidigare tillvägagångssätt för anläggningslösningar för benchmarking. Till exempel Ref. [35] använde sig av en metod baserad på problem med begränsad tillfredsställelse. Även om dessa problem är svåråtkomliga i hårdhet, finns det föga kontroll när man väljer parvärden mellan de enskilda variablerna. För analoga maskiner med ändlig precision, såsom D-Wave kvantannealers, kan detta vara en onödig begränsning. Andra tillvägagångssätt [36] börjar från ett slumpmässigt koppel arXiv:1706.02825v2 [cond-mat.dis-nn]
Ett nytt dokument REF introducerade metoden för patch plantering, där subgrafer med känd lösning är kopplade till varandra, tillfredsställer alla interaktioner och därmed plantera en övergripande mark tillstånd.
Patch-planting spin-glass solution for benchmarking
{'venue': 'Phys. Rev. E 96, 023312 (2017)', 'journal': None, 'mag_field_of_study': ['Physics', 'Medicine']}