Boosting integer factoring performance via quantum annealing offsets TECHNICAL REPORT EvgenyAndriyash,ZhengbingBian,FabianChudak,MarshallDrew-Brook,AndrewD.King,WilliamG.Macready,AidanRoy 2016-12-09 Overview CONTACT D-Wave quantum computing systems now allow a user to advance or CorporateHeadquarters 3033BetaAve delaytheannealingpathofindividualqubitsthroughtheannealoffsets Burnaby,BCV5G4M9 feature. Here we demonstrate the potential of this feature by using it Canada in an integer factoring circuit. Offsets allow the user to homogenize Tel.604-630-1428 dynamics of various computational elements in the circuit. This gives USOffice aremarkableimprovementoverbaselineperformance,insomecases 2650EBayshoreRd makingthecomputationmorethan1000timesfaster. PaloAlto,CA94303 Email: [email protected] www.dwavesys.com 14-1002A-B D-WaveTechnicalReportSeries Boostingintegerfactoringperformanceviaquantumannealingoffsets i Notice and Disclaimer D-WaveSystemsInc.(“D-Wave”)reservesitsintellectualpropertyrightsinandtothisdocument,any documentsreferencedherein,anditsproprietarytechnology,includingcopyright,trademarkrights, industrial design rights, and patent rights. D-Wave trademarks used herein include D-WAVE®, D-WAVE2X™, and the D-Wave logo (the “D-Wave Marks”). Other marks used in this document arethepropertyoftheirrespectiveowners.D-Wavedoesnotgrantanylicense,assignment,orother grantofinterestinortothecopyrightofthisdocumentoranyreferenceddocuments,theD-Wave Marks, any other marks used in this document, or any other intellectual property rights used or referredtoherein,exceptasD-Wavemayexpresslyprovideinawrittenagreement. Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets ii Summary Mapping a boolean circuit or optimization problem onto a D-Wave system typically re- quires the use of chains; that is, groups of qubits representing the same logical variable. Chainsofdifferentlengthproducedifferentquantumtunnelingdynamics,aslongerchains havealowereffectivetunnelingenergyandmayfreezeoutinafixedstateearlierinthean- neal. Tobalancethesedisparatetunnelingdynamics, wecanboosttherelativetunneling energyoflongerchainsbydelayingtheannealoftheirqubits. 2000-qubitD-Wavesystems allow the user to advance or delay the annealing path of individual qubits through the annealoffsetsfeature. Here we review a demonstration of this capability, as applied to the problem of integer factoring: given an input number p, find integers a and b such that a×b = p. The 1994 formulationofShor’salgorithm,alongwiththeubiquityoffactoringincryptographicsys- tems,makesthisaproblemofcentralinterestinthecontextofquantumcomputing. One way to factor an integer using quantum annealing is to run a multiplication circuit backwards. Webeginbysettingupaminimizationproblemrepresentingamultiplication circuit.Thiscircuithasinputsaandb,andoutputp,andcanachieveanoptimalstatewhen a×b = p. Ifwespecify aandbbutnot p,thenthesolutiontotheminimizationproblem tellsusthevalueof p. Ifinsteadwespecify pbutnot aorb,thesolutiongivesus aandb suchthata×b = p. Annealoffsetsgivearemarkableimprovementinperformancefortheseproblems,insome cases making the computation more than 1000 times faster. Figure 1 shows performance ofaD-Wavesystemonatestbedoffactoringproblems,runbothwithandwithoutanneal offsets. Unsolved Nooffsets y 6–bit Offsetstrategy g olved 1 strate 81–0b–bitit ss 0.8 et 1e0 m s e off robl 0.6 me, ofp 0.4 nti 1e-2 rtion 0.2 olutio o S p o 0 1e-4 Pr 6 8 10 1e-4 1e-2 1e0 Unsolved Problemsize(bitsinfactorednumber) Solutiontime,nooffsettuning (a) (b) Figure1: Performanceofa2000-qubitD-Wavesystemonintegerfactoringproblemsimprovesdra- maticallywhenannealoffsetsareused.(a)Percentageofinstancessolvedusing250,000samplesper instance,whenfactoring6-,8-,and10-bitsemiprimes. (b)Timerequiredtofindasolutionforeach instance. Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets iii Contents 1 Annealoffsets 1 1.1 Chaindynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Factoring 3 2.1 Multiplicationcircuitsasconstraintsatisfaction . . . . . . . . . . . . . . . . . . . 4 2.2 Constraintsasoptimizationobjectives . . . . . . . . . . . . . . . . . . . . . . . 4 3 Results 8 4 Discussion 9 A Derivationoftheannealdelayfunctionforchains 11 Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets 1 1 Anneal offsets IsingmodelquantumannealingcanbemodeledbytheHamiltonian H(s) = A(s)H +B(s)H , 0 P which evolves over time s from an initial Hamiltonian H = ∑ σ(i) at s = 0 to a final 0 i x Hamiltonian H = ∑ h σ(i)+∑ J σ(i)⊗σ(j) at s = 1. If the system evolves slowly P i i z i<j i,j z z enough,itremainsinitsgroundstatethroughout,andthegroundstateof H encodesthe P solution to the classical energy minimization problem of the Ising model [h,J]. A typical scheduleforthetunnelingenergy A(s) andproblemenergy B(s) isshowninFigure2(a). In the 2000-qubit D-Wave system, the default A(s) and B(s) is identical for every qubit. However, this schedule may be modified on a per-qubit basis, allowing for alternative schedulesthatbetteroptimizeperformance. Bydefault,theD-Wavescheduleiscontrolledbyaglobal,time-dependentsignalc(s)that simultaneouslydetermines A(s) and B(s). Theannealoffsetsfeatureperturbsthissignal ateachqubiti byanoffsetδc,sothattheschedulingsignalattimesonqubiti isc (s) = i i c(s)+δc. This offset has the effect of giving each qubit its own schedule [A (s),B(s)], i i i which may be advanced or delayed from the global schedule [A(s),B(s)], resulting in a modifiedHamiltonian (cid:113) H(s) = ∑A (s)σ(i)+∑B(s)h σ(i)+∑ B(s)B (s)J σ(i)⊗σ(j). (1) i x i i z i j i,j z z i i i<j Figure2(b)showstheeffectoftheseoffsets:ifδc >0,thescheduleisadvanced,soA (s) < i i A(s)andB(s) > B(s). i While modifying the annealing schedule on a per qubit basis allows a great deal of flex- ibility for optimization, the perturbation from B(s) to B(s) also introduces a new source i of error: the individual h and J terms of the Ising model in (1) are no longer amplified uniformlyduringtheanneal. Thismeansthatthebenefitsofindividualannealschedules mustbebalancedagainstlargerproblemmisspecification. 1.1 Chain dynamics Oneparticularlyvaluableapplicationoftheannealoffsetfeatureishomogenizingthedy- namicsofchains. Achainisacollectionofqubitsintendedtoactasasinglelogicalspin;to impose this behavior, we apply a strong ferromagnetic coupling (J = −1) between those qubits. Thelengthofthechainisthenumberofqubitsinit. If we impose a chain coupling J = −1 between qubits i and j, and express the problem ij Hamiltonian at a smaller energy scale, then the Ising model energy is minimized when i and j take the same spin; therefore we may treat i and j as a single logical qubit, call it q . However, at any point in the anneal, the effective tunneling energy of q is smaller ij ij thanthatofasinglequbit. Intuitively,twoqubitsarelesslikelytotunnelsimultaneously than just one in isolation. More precisely, at time s, if the tunneling energy and problem energy for a single qubit are A(s) and B(s), then the effective tunneling energy of q is ij Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets 2 12 12 A(s)baseline A(s) B(s)baseline 10 B(s) 10 A(s)/c =0:05 i i B(s)/c =0:05 i i 8 8 A(s)/c =!0:05 i i )z )z Bi(s)/ci=!0:05 H H G 6 G 6 ( ( y y g g r 4 r 4 e e n n E E 2 2 0 0 -2 -2 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 s(annealfraction) s(annealfraction) (a) (b) Figure2: Annealingschedules. (a)TypicalannealparametersA(s),B(s). Annealingbeginsats=0 with A(s) (cid:29) B(s) andendsat s = 1with A(s) (cid:28) B(s). (b)Annealparameterswithoffsets. The baselinecurve(δc =0)isshownalongwithA(s),B(s)foraqubitthatisadvanced(δc =0.05)or i i i i delayed(δc =−0.05). i proportionalto (cid:114) B(s)2 B(s) +A(s)2− . (2) 4 2 (See[1]fordetails.) Fork >2qubitsactingasasinglelogicalvariable,theeffectivetunnel- ingenergyisreducedevenfurther. Asaresultofreducedtunnelingenergy, chainssufferfromearlyfreeze-out: longerchains becomefixedtoaparticularspinvalueearlierintheannealthanshorterchains. Thiseffect usuallyhasanegativeimpactonperformance. However, annealoffsetscanmitigatethis effect: by delaying the anneal for longer chains, their tunneling energy is increased and broughtinlinewithothers. UsingperturbationtheoryandtheparticularscheduleoftheD-Wavesystem,wecancom- pute the anneal offsets required to synchronize the effective tunneling energy across all chain lengths at a fixed time s during an anneal (see Appendix A). The delay on an iso- lated chain of k qubits is reasonably well approximated by a function of the form f(k) = 1−k β k −1, where 0 < β < 1 depends on the time s at which the tunneling energies are synchronized(seeFigure3). Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets 3 0.4 0.35 0.3 ) s " (0.25 y a le 0.2 d la en0.15 n A 0.1 0.05 0 1 2 3 4 5 6 7 Chainlength 1−k Figure3:Annealoffsetdelay f(k)=β k −1asafunctionofchainlengthk.Shownisβ=log2. 2 Factoring As an application to measure the performance benefits of anneal offsets, we consider the problem of factoring integers. This is a problem whose presumed hardness is the basis formanycryptographicprotocols. Whileintegerscanbefactoredinpolynomialtimeona universalquantumcomputerusingShor’salgorithm[2],noefficientclassicalalgorithmis known.Ourapproach(introducedin[3],seealso[4,5])iscompletelydifferentfromShor’s algorithmandoffersnoguaranteeofasolutioninpolynomialtime. Itdoesdemonstratea waythatfactoringcanbeperformedonD-Wavesystemsandisusedtotestthebenefitof annealoffsets. Wewishtofactoraninteger pasaproductofapairofn-bitintegersaandb. Tosolvethis problem, werepresent a, b, and p inbinaryandconstructaBooleancircuitthatperforms n-bit by n-bit multiplication. We then encode the circuit as an optimization objective, so thatinput/outputbitstringsthatsatisfythecircuithaveaknownminimumenergy(and allotherbitstringshavehigherenergy). Finally, byfixingtheoutputofthecircuittothe binary representation of p and minimizing the resultant optimization objective, we can obtaintheinputsgivingthedesiredoutput,effectivelyrunningthecircuitinreverse. More generally, for any decision problem, we imagine encoding the Boolean circuit that verifies the answer as either true or false, clamping the output of the circuit to true, and minimizing. ForNPproblemsthiscircuitispolynomiallysized. (However,factoringa2n- bitintegerrequiresθ(n2)qubits: integersofcryptographicinterestarebeyondthescaleof 2000-qubitD-Wavesystems.) Clampingmaybeeffectedbyappropriatelocalfieldsacting ontheoutputbits,orbyeliminatingtheoutputbitsentirelyandaddingtheircontributions totheirneighbors. Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets 4 a a a a 3 2 1 0 b b b b 3 2 1 0 a b a b a b a b 3 0 2 0 1 0 0 0 a b a b a b a b 3 1 2 1 1 1 0 1 a b a b a b a b 3 2 2 2 1 2 0 2 a b a b a b a b 3 3 2 3 1 3 0 3 p p p p p p p p 7 6 5 4 3 2 1 0 Figure4:Multiplicationoftwo4-bitintegers(a ,a ,a ,a )and(b ,b ,b ,b )toformthe8-bitproduct 3 2 1 0 3 2 1 0 (p ,p ,p ,p ,p ,p ,p ,p ). 7 6 5 4 3 2 1 0 2.1 Multiplication circuits as constraint satisfaction Consider the multiplication of two 4-bit integers. Schematically, the product is formed fromthemultiplicationtablegiveninFigure4. Anyoutputbit p isformedasthesumof i appropriateproductsofthebitsofaandb. Forexample,thefirstoutputbitisgivenby p = a b . 0 0 0 Thisimposesaconstraintbetweeninputs a ,b andtheoutput p . Thisconstraint,which 0 0 0 wedenoteC∧(a0,b0,p0),istheANDgateofdigitallogic. To represent a sum of bits, we use digital adders. A half adder, denoted C (t,t(cid:48),p,c), 2A is a constraint with inputs t, t(cid:48) and outputs s, c (sum and carry), enforcing the constraint t+t(cid:48) = s+2c. Thefulladderconstraint,denotedC (t,t(cid:48),t(cid:48)(cid:48),p,c)enforcestheconstraint 3A t+t(cid:48) +t(cid:48)(cid:48) = p+2c (see Figure 5 for truth tables). Arranging half and full adders in a sequence,wecanenforcethesummationconstraintsontheoutputbits p imposedbythe columnsofthemultiplicationtableinFigure4. AnetworkofconstraintsrepresentingthefullmultiplicationcircuitisshowninFigure6, withoptimizationvariablesrepresentedasedges. Inadditiontothevariablesrepresenting inputs a and b andoutputs p, thereareanumberofintermediatevariables. The si and ci j j variables represent the sum and carry bits from adder constraints respectively, while the t variablesrepresenttheproductsa b . i,j i j 2.2 Constraints as optimization objectives Havingreducedintegerfactoringtoaconstraintsatisfactionproblem,wenextreducecon- straintsatisfactiontoIsingmodeloptimization. GivenaconstraintC(x)definedoverasetofBooleanvariables x ∈ {0,1}n,weidentify x with spin variables s = 2x−1 ∈ {−1,1}n, and represent C(x) by an Ising model whose ground states coincide with the feasible configurations of the constraint. Typically, this requirestheuseofancillaryvariables. Wewriteaspinconfigurationasz = (s,a),wheres andaaretheconstraintandancillaryvariablesrespectively,anddenoteenergyofanIsing model[h,J]atspinconfigurationzas E (z) = hTz+zTJz. [h,J] Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets 5 c t a b p a b t t(cid:48) s c t 0 0 0 0 p 0 0 0 0 0 1 0 s 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 (a) ANDgate(∧) (b) Halfadder(2A) t t(cid:48) t(cid:48)(cid:48) s c t00 t 0 0 0 0 0 c t0 1 0 0 1 1 0 s 0.5 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0.5 − 1 0 1 0 1 1 − 1 1 0 0 1 1 1 1 1 1 (d) Colorcode (c) Fulladder(3A) Figure 5: Truth tables and Ising penalty models for the (a) AND gate, (b) half adder, and (c) full adder.Colorsshownin(d)identifythedifferenthandJvaluesforeachIsingmodel. ToseparatefeasibleandinfeasiblesolutionsinC(x),werequirethatforsomeglobalmin- imae andpositiveenergygapg: 0 (cid:40) e ifC(x)issatisfied(wherex = s+1); minE (s,a) = 0 2 a [h,J] ≥ e +g ifC(x)isnotsatisfied. 0 The multiplication constraints C∧, C2A, and C3A can be realized as Ising penalty models P∧, P2A, P3A,asshowninFigure5. Thesemodels,foundusingthetechniquesin[6],were constructedtomatchthegraphstructureoftheD-Wavesystem. TheavailableIsingmodel interactions form a Chimera graph, consisting of a 2-dimensional grid of interconnected unitcells,whereeachunitcellisaK completebipartitegraph. 4,4 After penalty models are defined for all constraints in the circuit, the models are placed ontodisjointsubgraphsoftheChimeragraph.Variablesmayoccurinmultipleconstraints, but we connect the different instantiations of a variable together using chains. The con- straintsofthemultiplicationcircuitinFigure6haveanaturalgrid-likelayout;thisfitswell with the Chimera grid structure. Figure 7 shows a 3-bit multiplication circuit completely embeddedontoaChimeragraph. Copyright©D-WaveSystemsInc. Boostingintegerfactoringperformanceviaquantumannealingoffsets 6 b b b 0 0 0 P P P P ∧ ∧ ∧ ∧ a a a a 3 2 1 0 s1 s1 s1 3 2 1 b b b 1 1 1 P P˜ P˜ P˜ ∧ 2A 2A 2A a a a a 3 2 1 0 s2 s2 s2 4 c2 3 c2 2 c2 3 2 1 b b b 2 2 2 P P˜ P˜ P˜ ∧ 3A 3A 3A a a a a 3 2 1 0 s3 s3 s3 5 c34 4 c33 3 c32 p0 b b b 3 3 3 P P˜ P˜ P˜ ∧ 3A 3A 3A p1 c4 s4 s4 s4 3 6 c45 5 c44 4 p2 P P P 3A c5 3A c5 2A p3 p 5 4 7 p p p 6 5 4 (a) 4-bitby4-bitmultiplicationcircuit a a i s i s c b b j j P b P b ∧ j ∧ j t t i,j i,j a a i i P P 2A 3A c c ′ s ′ s ′ ′ (b) BoxP˜2A:halfadderdetail (c) BoxP˜3A:fulladderdetail Figure6: Theconstraintnetwork(a)representsthemultiplicationoftwo4-bitnumbers. Boxesla- beledP˜ andP˜ in(b)and(c)respectivelyrepresentpairsofconstraints(anANDgatewithahalf 2A 3A adderorfulladder). Copyright©D-WaveSystemsInc.