Vi grupperar alla kända kvadratiseringar av kubik och kvartiska termer i binära optimeringsproblem i fem respektive sex unika grafer. Vi utför sedan en mindre inbäddning av dessa grafer på den välkända Chimera grafen, och den helt nya Pegasus grafen. Vi avslutar med rekommendationer för vilka prylar som är bäst att använda när man strävar efter att minska det totala antalet qubits som krävs för att bädda in ett problem. Diskreta optimeringsproblem är ofta naturligt formulerade när det gäller att minimera vissa polynom av grad > 2 [1], som sedan 'quadratized' [2] till en kvadratisk funktion som kan lösas med hjälp av standardalgoritmer för universella klassiska datorer [3], med hjälp av speciella klassiska annealer [4], eller med kvantannealer [5]. Med mer än 40 kvadreringsmetoder tillgängliga för binära optimeringsproblem [2], bör man välja den bästa kvadrering för ett givet problem, och för en given metod för att lösa det fyrdubblade problemet. Det finns sätt att fyrdubbla funktioner av diskreta variabler utan att lägga till några hjälpvariabler [2, 6-9], men när dessa metoder inte kan tillämpas introducerar vi hjälpvariabler. De resulterande quadratic funktioner (kallas "gadgets"), att med god noggrannhet (eller ibland exakt noggrannhet) simulera de ursprungliga höggradiga funktioner, kommer att ha viss anslutning mellan de binära variablerna (eller bitar, eller qubits, häri avses endast för bekvämlighet, som qubits) som kan representeras av en graf där hörn representerar qubits och kanter indikerar när två olika qubits visas tillsammans i en kvadratisk term. Eftersom denna graf inte innehåller någon information om linjära termer, konstant term, eller koefficienter för kvadratiska termer, många olika prylar har samma graf, därför i detta papper kommer vi att klassificera alla kända quadratization prylar i kategorier enligt deras motsvarande graf (här kallas deras "gadget graf"). Gadgetdiagram för alla kända enkla kubiktermer och för alla kända singelkvartiska termer ges i bild. 2............................................................... Gadget grafer berättar en hel del om hur dyrt quadratic optimering problem kommer att vara, och de med större anslutning tenderar att ge svårare funktioner att optimera. Dessutom fungerar vissa optimeringsmetoder endast om deras motsvarande graf har en viss konnektivitet, två exempel på sådana anslutningar är de i D-Waves välkända Chimera graf [10], och i deras alldeles nyligen Pegasus graf, båda visas i Fig. 1................................................................ Alla grafer, kan kartläggas på Chimera eller Pegasus grafer genom mindre-bäddning [24, 25], där Chimera grafen eller Pegasus grafen är en graf mindre av grafen som representerar problemet som behöver optimeras. Detta innebär ofta att en binär variabel i quadratic optimering problem måste representeras av två (eller fler) qubits (som kallas en "kedja") i stället för en, vilket gör antalet fysiska qubits som behövs för att lösa det ursprungliga problemet större än tidigare, och ibland omöjligt stor för att lösa. Till exempel om vi ville faktor det minsta RSA-nummer som ännu inte har faktoriserats på en klassisk dator (RSA-230) genom minimering av en motsvarande binär
På samma sätt diskuterade Dattani och Kansler vissa skillnader mellan de två senaste D-Wave kvantanglödande arkitekturer, nämligen Chimera och Pegasus grafer REF.
Embedding quadratization gadgets on Chimera and Pegasus graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}