NBERWORKINGPAPERSERIES

DYNAMICPROGRAMMINGONAQUANTUMANNEALER:SOLVINGTHERBCMODEL

JesúsFernández-Villaverde

IsaiahJ.Hull

WorkingPaper31326

/papers/w31326

NATIONALBUREAUOFECONOMICRESEARCH

1050MassachusettsAvenue

Cambridge,MA02138

June2023

Duringpartoftheproject,IsaiahHullwasaffiliatedwithandhadafinancialinterestinCogniFrame,Inc.,whichisapartnerofD-WaveSystems,theproducerofthequantumannealersusedinthepaper.TheauthorsdidnotreceiveanysupportorcomputetimefromD-Wavethroughthispartnership.AllaccesstoD-Wave'squantumannealerswasprovidedthroughastandarddeveloperagreement.TheviewsexpressedhereinarethoseoftheauthorsanddonotnecessarilyreflecttheviewsoftheNationalBureauofEconomicResearch.

NBERworkingpapersarecirculatedfordiscussionandcommentpurposes.Theyhavenotbeenpeer-reviewedorbeensubjecttothereviewbytheNBERBoardofDirectorsthataccompaniesofficialNBERpublications.

?2023byJesúsFernández-VillaverdeandIsaiahJ.Hull.Allrightsreserved.Shortsectionsoftext,nottoexceedtwoparagraphs,maybequotedwithoutexplicitpermissionprovidedthatfullcredit,including?notice,isgiventothesource.

DynamicProgrammingonaQuantumAnnealer:SolvingtheRBCModel

JesúsFernández-VillaverdeandIsaiahJ.Hull

NBERWorkingPaperNo.31326

June2023

JELNo.C63,C78,E37

ABSTRACT

Weintroduceanovelapproachtosolvingdynamicprogrammingproblems,suchasthoseinmanyeconomicmodels,onaquantumannealer,aspecializeddevicethatperformscombinatorialoptimization.QuantumannealersattempttosolveanNP-hardproblembystartinginaquantumsuperpositionofallstatesandgeneratingcandidateglobalsolutionsinmilliseconds,irrespectiveofproblemsize.Usingexistingquantumhardware,weachieveanorder-of-magnitudespeed-upinsolvingtherealbusinesscyclemodeloverbenchmarksintheliterature.Wealsoprovideadetailedintroductiontoquantumannealinganddiscussitspotentialuseformorechallengingeconomicproblems.

JesúsFernández-Villaverde

DepartmentofEconomics

UniversityofPennsylvania

TheRonaldO.PerelmanCenter

forPoliticalScienceandEconomics

133South36thStreetSuite150

Philadelphia,PA19104

andCEPR

andalsoNBER

jesusfv@

IsaiahJ.Hull

DepartmentofFinance,

BINorwegianBusinessSchool

Nydalsveien37,0484Oslo,

Norway

hull.isaiah@

2

1Introduction

Weintroduceanewapproachtosolvingdynamicprogrammingproblems,suchasthosethatappearinmanyeconomicmodels,onaquantumannealer(QA).Thisspecializedquantumde-viceperformscombinatorialoptimizationusingaphysicalprocess.AQAembedstheproblem’sparametersintoaquantumsystemthatevolvesto?nditslowestenergycon?guration.Thisisequivalentto?ndingthevaluesofstatevariablesthatgloballyminimizealossfunction(

Farhi

etal.

,

2000).QAsattempttosolveaproblemthatisNP-hardforaclassicalcomputerbystart

-inginaquantumsuperpositionofallstatesandreturningcandidatesolutionsinmilliseconds,

irrespectiveoftheproblemsize(

Venegas-Andracaetal.,

2018)

.1

Ourpapermakesfourcontributions:

1.Thedevelopmentofanewsolutionmethodforsolvingdynamicprogrammingproblemsonquantumhardware.

2.Theimplementationandexecutionofthesolutionmethodonexistingquantumhardware,ratherthanonaclassicalsimulator.

3.Thenoveluseofstate-of-the-artquantumannealingtechniques,includingreverseandinhomogeneousannealing.

4.ShowingthebroadapplicabilityofoursolutionmethodtoiterativeproblemsthatcouldnototherwisebesolvedonQAswithouthybridizingtheproblemintoclassicalandquan-tumcomponents.

Moreconcretely,wetacklethelimitationsofQAs,whicharenotdesignedtosolvethedynamicprogrammingproblemsatthecoreofmanyeconomicmodels.Inparticular,QAsdonotnaturallyallowforiterationovertimeoracrossmultipleobjectivefunctionsandsu?erfromthequantum-to-classicalbottleneck,whichseverelylimitshowmuchclassicalinformationcanbereadoutastheproblem’ssolution.Ourapproachovercomestheselimitationsandcanbeusedtorecoverpolicyandvaluefunctionsforproblemsinmacroeconomics,industrialorganization,gametheory,andlaboreconomics.

Toevaluateourapproach,wesolvetherealbusinesscycle(RBC)modelonaQAandcompareitsperformancetothebenchmarkresultsin

AruobaandFern′andez-Villaverde

(2015)

(hereafter,

AFV

).SolvingtheRBCmodelalsoallowsustodemonstratehowtoformulateawell-knowneconomicmodelinawaythatcanbesolvedonaQA.Evenwiththelimitationsofexistingquantumtechnology,wecansolvetheRBCmodelonaQAin3%ofthecomputationtimeoftheVFIsolutionusingC++asin

AFV

or0.66%ofthecomputationtimeofthecombinatorial

1Weusetheterm“classical”and“classically”toindicatethatsomethingisnotquantum.

3

algorithmthatweproposefortheQAbutrunonaclassicalcomputer.Thus,wedemonstratetheenormouspotentialofquantumhardwareforeconomists.

Ourapproachdi?ersfromtheexistingliteratureonquantumdynamicprogramminginthreekeyaspects.First,weuseaQAratherthanauniversalquantumcomputer(UQC).

2

WhileUQCsallowfortheproofofreductionsincomputationalcomplexity,theyarenotsu?cientlymaturetoimplementdynamicprogrammingalgorithmsthato?eraquantumspeed-upfornon-trivialproblems.PriorworkondynamicprogrammingonUQCshasfocused,instead,onthetheoreticaldemonstrationofquantumspeed-upsandonproof-of-principledemonstrationsfortrivialproblems.

3

Incontrast,ourfocusonQAsallowsustosolveastandardRBCmodelonthecurrentvintageofquantumhardwareratherthansimulatingnot-yet-developedquantumhardwareonaclassicalcomputer.

Second,wefocusonproblemsofinteresttoeconomistsandexplorewhatisachievablegivenalreadyexistingmachines.Workondynamicprogrammingusingquantumdeviceshascenteredalmostexclusivelyonproblemsinphysicsandcomputersciencethathavenaturallyparsimonioussolutions.Incontrast,economistsaretypicallyconcernedwithrecoveringpolicyorvaluefunctionsthatliveinhigh-dimensionalhypercubes.Thisisanon-trivialdi?erencesincethequantum-to-classicalbottleneckseverelylimitshowmuchdatacanbereadoutofaquantumdevice.Forinstance,aQAwithNqubitswillstartinanexponentiallylargequantumsuperpositionstateofdimension2N,butwilleventuallycollapseintoaclassicalstatethatcontainsonlyNclassicalbitsofinformation.Thus,?ndingawaytoencodethesolutioninNbitsisafundamentalchallengefordynamicprogrammingproblemsineconomics,whileitisusuallynotaprimaryconcerninphysicsandcomputerscience.Inpart,weovercomethisencodingproblembyusingtheparametricdynamicprogrammingmethodintroducedin

Benitez-Silvaetal.

(2000)toreducethespacecomplexityofthesolution

.

Third,weshowhowtoconstructiterativealgorithmsthatcanbeimplementedonQAs,whichnootherworkhasaccomplishedtothebestofourknowledge.Afundamentalchallengeofdynamicprogrammingisthatsolutionmethodsoftenrequireiteration,sometimesoveralter-natingobjectivefunctions.QAsarenotprogrammableinthewaythatclassicalcomputersorUQCsareprogrammable.Thatis,theycanonlyembedaprobleminstanceandthenperformannealingwithalimitedsetofparameters.Ourapproachaddressestheproblemofhowtoimplementiterationsbymakinguseoftwostate-of-the-artfeaturesofQAs:reverseandinho-mogeneousannealing.Thesetwofeatureswidentheapplicabilityofourworktoanyiterative

2Section

2

willexplaininmoredetailthedi?erencebetweenQAsandUQCs.Su?ceittosayherethatUQCsaremorechallengingtoconstructthanQAs,whichiswhytheirdevelopmenthaslagged.

3EvenonUQCs,littletheoreticalprogresshadbeenmadebefore

Ambainisetal.

(2019),whousedthe

unstructuredquantumsearchalgorithmin

Grover

(1996),coupledwiththecomputationofapartialdynamic

programmingtable,toachieveaquadraticspeed-upforproblemsthatinvolvetheselectionofasubsetofelements.

4

algorithm,whetherornotitisrelatedtodynamicprogramming.

Therestofthepaperisstructuredasfollows.Section

2

givesanoverviewofquantumannealing.Section

3

introducesthebenchmarkRBCmodelweuseasatestbed.InSection

4

,weexplainhowtotranslatethemodelintoaformthatissolvableonaQA.Section

5

introduceshybridandquantumalgorithmsforsolvingthemodelandcomparestheresultstothebenchmarksin

AFV

.Section

6

concludeswithadiscussionoftheprospectsofquantumannealingineconomics.AnOnlineAppendixaddsfurtherdetails.

2QuantumAnnealing

Therearetwoprimarymodelsofquantumcomputing:universalquantumcomputingandquan-tumannealing.Universalquantumcomputers(UQCs)employthe“gate-and-circuit”model,inwhichquantumoperationscalledgatesareappliedtoquantumbits(qubits)toenablearbitrarycomputations.Thesegatesmustadheretotheprinciplesofquantumphysics,sincetheyareperforminganoperationonaquantumsystem.Quantumcircuitsconsistofgatesequencesthatimplementasubroutinewithinaquantumsystem.

UQCso?ertheoreticalreductionsintimeandspacecomplexityforvariousalgorithmsusedincomputationaleconomicsandeconometrics(

Hulletal.,

2020

).Forinstance,

Ambainisetal.

(2019)and

Glosetal.

(2021)provetheoreticalquantumspeed-upsforseveralclassesofdynamic

programmingproblem,includingthetravelingsalespersonandvertexorderingproblems.Ex-perimentalevidencealsodemonstratesthatUQCsarecapableofachievingaspeed-upoverclassicalcomputersforcertainproblemclasses(

Aruteetal.,

2019

)

.4

Unfortunately,UCQsaretechnicallydemandingtoconstruct,andtheirdevelopmenthaslaggedbehindspecializedquantumdevices,suchasQAs.

Incontrast,QAsdonoto?ertheoreticallyprovablereductionsincomputationalcomplexityandcannotbeprogrammedtoexecutearbitraryalgorithms.Instead,QAscanonlyperformcombinatorialoptimization.Thisseeminglyseverelimitationhas,however,enabledconsider-ablyfasterexperimentalprogress.Atpresent,QAshaveroughly50timesasmanyqubitsasUQCs

.5

Intheremainderofthissection,weintroducetheconceptofquantumannealing,discusstheproblemsitcansolve,explainitslimitations,andidentifyproblemsineconomicswhereit

mightbeapplied.Westartwithabriefreviewofcombinatorialoptimization.

4Aruteetal.

(2019

)initiallyclaimedtoachieve“quantumsupremacy,”asde?nedin

Preskill

(2012),by

performingacomputationin200secondsthatwouldarguablytake10,000yearsontheworld’sfastestclassicalsupercomputer;however,thisclaimhassincebeendisputedandappearstohaveunderstatedtheperformanceofclassicalsupercomputers.

5ThelargestUQCsarecurrentlyproducedbyIBM.ItsEagler1quantumprocessorhas127qubits.IBMhasalsorecentlyintroducedanexploratoryOspreyr1processorwith433qubits.Incontrast,Advantage,theQAproducedbyD-WaveSystemsthatweuseforourcomputationsinthispaper,has5616qubits.

5

2.1CombinatorialOptimization

Quantumannealingisaheuristicmethodforsolvingcombinatorialoptimizationproblemsthatmayprovideasubstantialcomputationaladvantageoverclassicalsolutionmethodsforspeci?ccases(

Zintchenkoetal.,

2015

).Forourdiscussion,weadoptaslightlymodi?edversionofthede?nitionofacombinatorialoptimizationproblemgivenin

Venegas-Andracaetal.

(2018)

.

De?nition1(CombinatorialOptimizationProblem).LetEbea?nitesetwithcardinality|E|=n,PEthepowersetofE(hence|PE|=2n),andCalossfunctionwhereC:PE一R.Thegeneralsetupofacombinatorialoptimizationproblemisto?ndanelement此EPEsuchthatC(P)=minpiePE{C(此i)}.

Ingametheoryandmechanismdesign,problemsinvolvingtheallocationofdiscreteobjectsoftenhaveanaturalcombinatorialformthat?tsthede?nitionaboveandisconducivetousingaQA.Problemsthatinvolve?nancialnetworksalsoalignwiththisde?nitionandcanbesolvedonaQA,asshowninproof-of-principleexercisesby

Or′usetal.

(2019a

,b

).

Ourfocuswillbeonproblemsineconomicsthatdonotnaturally?tthisde?nitionbutarecommonlyreformulatedascombinatorialproblemstofacilitategridsearchorvaluefunctioniteration.Asthe?rstexample,considera?rmthatminimizesacostfunction,C,bychoosinginputs,LandK,giventechnologyyC=Y(L,K).Iftheproblemdoesnotpermitananalyticalsolution,acommonstrategyistosearchfortheminimumofCovertheCartesianproductof

discretegrids,whereKE{K0,K1,...,K*1}andLE{L0,L1,...,L*1}.Asolutiontothe

problemisapairoffunctions,KC(w,r,y)andLC(w,r,y),whichyieldoptimalKandLchoicesgivenfactorprices(w,r)andthetargetlevelofoutputy.

Asasecondexample,considertheproblemofanin?nitelylivedhouseholdthatmaximizesutilityfromconsumption,subjecttoabudgetconstraint.Thisproblemisoftenwrittenasadynamicprogramandsolvedusingvaluefunctioniteration.Thesolutionisadiscretelook-uptableapproximationoftheoptimalvaluefunctionorpolicyruleforcapitalandconsumption. Whilethesetwoexamplescan,inprinciple,besolvedonaQAoncewehavereformu-latedthemascombinatorialproblems,thelimitationsofquantumcomputerswillmakethisreformulationchallenging.Theprimarydi?culty,whichwediscussinSubsection

2.5

,isthequantum-to-classicalbottleneck,whichlimitstheamountofinformationthatcanbereadoutofaquantumcomputer,includingaQA.Thecomputationalcomplexityofsuchproblemsalsodi?ersfromthatofmorestandardcombinatorialoptimizationproblems,whichwediscussin

Subsection

2.4

.

6

2.2AdiabaticQuantumComputing

Quantumannealingcanbedescribedasaheuristicor?nitetemperatureimplementationofadiabaticquantumcomputing(

Venegas-Andracaetal.,

2018;

Shinetal.

,

2014),anditsvalue

asanoptimizationalgorithmisjusti?edthroughthequantumadiabatictheorem(

Messiah,

1958

;

AmbainisandRegev,

2004).Toexplaintheseideas,letusintroducetheidealizedconcept

ofadiabaticquantumcomputing,whichwewilltreatasthebest-casescenarioforquantumannealingthatisunlikelytobeachievedinpractice.

AmbainisandRegev

(2004)provideaninformalde?nitionofthequantumadiabatictheorem

.AHamiltonianexpressesthetotallevelofenergyinaquantumsystem:

...ifwetakeaquantumsystemwhoseHamiltonianslowlychangesfromN1toN2,then,undercertainconditionsonN1andN2,theground(lowestenergy)stateofN1getstransformedtothegroundstateofN2.

Farhietal.

(2000)showedthatthepreviousfactcanbeusedtoconstructanalternative

modelofquantumcomputingthatexploitsadiabaticevolutiontoidentifyglobalminima.

Moreconcretely,onebuildsaquantumstatethatinterpolatesbetweentwoHamiltonians:1)atrivialHamiltonian,N0;and2)theproblemHamiltonian,Np.ThesystemisinitializedasN0,buttransitionsovertimetoNp,followingtheadiabaticevolution:

N(t)=╱1-N0+Np.

TheinitialHamiltonian,N0,isspeci?edtobetrivial,suchthatwecanidentifythelowestlevelofenergy(thegroundstate)analytically.Incomparison,Npencodesaminimizationproblemofinterest,wheretheenergylevelinthesystemcorrespondstothelossassociatedwithastate.Thus,N0andNpcanbeinterpretedaslossfunctionswithgroundstatesthatcorrespondtoglobalminima.

Returningtothedescriptionofthequantumadiabatictheorem,evolvingfromN0toNpsu?cientlyslowlywillensurethatthequantumsystemremainsintheglobalminimum(groundstate)inallperiods.Thus,inprinciple,thequantumadiabatictheoremtellsushowto?ndtheglobalminimumofacombinatorialoptimizationproblem.

Adiabaticquantumcomputingalsoallowsustocomputea“speedlimit”forthetransitionbetweenN0andNptoensurethequantumsystemremainsinitsgroundstate.Unfortunately,formanyproblemtypesofsizeN,thespeedlimittakestheformT=p[exp(γNν)],whereγandνarepositiveparameters(

Bapstetal.,

2013

;

Lucas

,

2014)

.

Hence,adiabaticquantumcomputingmayrequireexponentialtimetotransitionbetweenN0andNpwhileremaininginthegroundstate.Consequently,itisunlikelythatQAswill

7

solvehardglobaloptimizationproblemsinpolynomialtime.However,γandνcouldbecon-siderablysmallerthantheircorrespondingvaluesfortheclassicalproblem,enablingustosolveexponentiallyhardproblemswithlargerinputsizes.WewillrevisitthisideainSubsection

2.4

.

2.3ProblemEncoding

QuantumannealinginvolvestheevolutionofatrivialHamiltonian,N0,con?guredinitsgroundstate,intoonethatencodestheproblemofinterest,Np.Ifthetransitionhappensadiabatically(veryslowly),Npwillalsobeinitsgroundstate.Wecanthenmeasurethequantumsystemandrecovertheglobalminimum.

QAsdonotrequireustospecifyN0,sinceanytrivialHamiltonianwithaknowngroundstate(globalminimum)willwork

.6

However,onemustspecifyNp,anon-trivialtaskevenforsimpleproblems.Thisprocessisreferredtoas“problemencoding,”sinceitencodestheinformationaboutaminimizationprobleminthestateofaquantumsystem.Next,wewilldiscusshowsuchencodingsareconstructed,startingwiththetypesofproblemswecanfeasiblyencode.

2.3.1Conversiontoabinaryquadraticmodel

Subsection

2.1

highlightedthatanoptimizationproblemmustbecombinatorialtobesolvableonaQA.ThisisbecauseQAsmustencodethestructureofaminimizationproblemasabinaryquadraticmodel(BQM).ThiscanbedoneusingtheIsingorthequadraticunconstrainedbinaryoptimization(QUBO)model.TheIsingmodelallowsustointroducethemainconceptstransparentlyandhasanintuitiveinterpretation.TheQUBOwillbemoreconvenientand,thus,ourpreferredchoicefortherestofthepaper.TheQUBOmodelalsoabstractsfromanyphysicalsystemand,thus,doesnotrequireknowledgeofphysics.

TheIsingmodel.TheIsingmodeldescribesasystemofatomicspins.Forourpurposes,itwillsu?cetounderstandthateachspinisaphysicalsystemthatcanbecon?guredinoneoftwostates,whichwewillrepresentas+1and-1.WecanthinkofaspinascorrespondingtoaterminalqubitstateinaQA.

WedenoteavectorofNspinsass=[s0,s1,...,sN*1}.Eachsihasabias,hi,andeachpairofspins,(si,sj),hasacoupling,Ji,j,wherehi,Ji,jBR.Thespinsandcouplingscanbeusedtode?neanIsingmodel:

N*1N*1N*1

N(s)=↓hisi+↓↓Ji,jsisj.

i=0i=0j=0

6Inpractice,anequalsuperpositionofallstatesistypicallyused.Additionally,“reverse”annealingallowsustospecifyaninitialclassicalstate,whichcanbeusedtore?nesolutionsbyperformingalocalsearch.

8

s2

RecallthatNencodesalossfunctionasthetotalenergylevelinaphysicalsystem.Thus,aterminalsvectorthatimpliesahigherNalsoimpliesahigherloss.Thebiasesandcouplingsarefeaturesofouroptimizationproblem,whichweencodeinthesystem.Theannealingprocessidenti?esanoptimalcon?gurationofspinstominimizetheenergylevel.

s0

s1

N(s)

1

-1

-1

-1.0

2

-1

1

0.0

3

1

-1

1.6

4

1

1

-0.6

Table1:Spincon?gurationsandenergylevels.

Forconcreteness,consideraproblemwhereN=2,h=[0.5,-0.3},andJ=[-0.8}.Table

1

enumeratesallpossibleterminalsvectorsandcomputesthetotalenergy(loss)inthesystem.Combination1,wheres=[-1,-1},isaglobalminimumforthisproblem,sinceN(-1,-1)islowerthanforanyothercombinationofspins.WhilethisistrivialtoprovefortheN=2case,theclassicaltimecomplexityofenumeratingallpossiblecombinationsforanarbitrarysoflengthNisp(2N).

s1

s0

s3

Figure1:AgraphicalrepresentationofabinaryquadraticmodelfortheN=4caseandwithcouplingsbetween

thepairs:[(s0,s1),(s0,s3),(s1,s2),(s1,s3)}.

BQMs,includingtheIsingmodel,haveanaturalgraphicalrepresentation.ConsiderthecaseforagraphofsizeN=4withnon-zerocouplingsbetweenthepairs(s0,s1),(s0,s3),(s1,s2),and(s1,s3).Abstractingfrombiasesandcouplingmagnitudes,wecanrepresentthismodelwithagraph,G,speci?edbyverticesandedges,(V,E).Figure

1

visualizesthegraph,whereV=[s0,s1,s2,s3}andE=[(s0,s1),(s0,s3),(s1,s2),(s1,s3)}.

AswediscussinSection

4

,theBQMimpliedbyourproblemmustbemappedtoagraphthatisembeddedinaQA.Whiletheembeddingistypicallyconstructedinaclassicalpre-processingstep–and,thus,isnotapartofthesolution–theproblem’sdi?cultyandtheembedding’s

9

qualitydependonthegraphourproblemimplies(

Lucas,

2014

).Section

4

explicitlyconsiderswhetheraBQM’sgraphissuitableforagivenQAtopology.

Earlier,wepresentedtheclassicalIsingmodeltoenhanceintuition.WedescribedtheHamiltonianasanoperatorthatexpressesthelevelofenergyinasystemasafunctionofitsstateandtheparametersofthesystem,whichcanbecon?guredtoencodeanoptimizationproblem.Inaddition,thereisaversionoftheIsingmodelthatallowsforquantumphenomenaandexpressesthelevelofenergyinthesystem.

Toseethis,westartwiththestandardinitialstateofaQAgivenbytheHamiltonian:

N*1

N0=-↓σ,

i=0

whereσ=I8...8σx8...8I,Iisa2x2identitymatrix,andσxisthePauliXmatrix:

σx=

0

1

1

0

,

wheretheiindicatesthatσXislocatedintheithpositioninthesequenceoftensorproducts:FortheN=2case,forexample,N0wouldbespeci?edas:

(0-1-10）

N0=-(σx8I+I8σx)=|--|.

（0-1-10ì

ThegroundstatecorrespondstotheeigenvectorassociatedwiththeminimumeigenvalueofN0.Inthiscase,thecharacteristicpolynomialoftheexpressionforN0isλ4-4λ=0,yieldingtheeigenvaluesλ=[-2,2,0,0}andeigenvectorsv:

(1）(1）(-1）(0）

v=（||||,,,1

|.

ì

The?rsteigenvector,v0=[1,1,1,1],isassociatedwiththeminimumeigenvalue(λ0=-2)and,thus,correspondstotheglobalsolution.Withasuitablenormalization,thisvectorrepresentsauniformsuperpositionoverallpossiblestates.Wehavetwoqubitsandtwostatesinthiscase,sotherearefourpossibleclassicalcon?gurations.AQAistypicallypreparedinthisposition(butforNqubits),sinceithasatriviallycomputablegroundstate.Performingmeasurement

10

immediatelywouldcollapsethesuperposition,yieldingoneofthefourpossiblestateswithequalprobability.

Duringtheannealingprocess,theHamiltoniancanbeexpressedas:

N=(1-hiσ+Ji,jσσ,(1)

wherethecoe?cientsontheinitialandproblemHamiltonianscorrespondtotheannealing

schedule.Again,weuseσasashorthandforσ=I8...8σz8...8I,whereσzisthePauli

Zmatrix:

σz=l01].

TheHamiltonian(

1

)containstransverse?elds,representedbytheσterms,whichpull

qubitstowardasuperpositionofthe+1and-1states.These?eldsareintensionwiththeσ

termsintheproblemHamiltonian,whichpullqubitstowardaclassicalcomputationalbasisstate

.7

TheQUBOmodel.TheQUBOmodelisstillaBQM,butituses0and1statesratherthanthe+1and-1statesoftheIsingmodel.AQUBOmodelallowsequalityandinequality

constraintsanddoesnotuseaquadraticapproximation

.8

ThestandardformofaQUBOproblemis:

N(x)=Qi,ixi+Qi,jxixj.

ThisHamiltonianformulationemphasizestherelationshipbetweentheIsingmodelandQUBOproblemsinthecontextofquantumannealing.

Noticethatx=[x0,x1,...,xN*1}isavectorofbinaryvariablesthatcantakeonvaluesof0and1.TheproblemstructureisembeddedinQ,anupper-triangularmatrix.WemayrewritetheproblemintermsofQasN(x)=xTQx.

Modelconversion.Convertingtheconstrainedopt