Non-StoquasticInteractionsinQuantumAnnealingviatheAharonov-AnandanPhase Walter Vinci1,2,3 and Daniel A. Lidar1,2,3,4 1DepartmentofElectricalEngineering,UniversityofSouthernCalifornia,LosAngeles,California90089,USA 2DepartmentofPhysicsandAstronomy,UniversityofSouthernCalifornia,LosAngeles,California90089,USA 3Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA 4DepartmentofChemistry, UniversityofSouthernCalifornia, LosAngeles, California90089, USA We argue that a complete description of quantum annealing (QA) implemented with continuous variables must take into account the non-adiabatic Aharonov-Anandan geometric phase that arises when the system Hamiltonian changes during the anneal. We show that this geometric effect leads to the appearance of non- stoquastictermsintheeffectivequantumIsingHamiltoniansthataretypicallyusedtodescribeQAwithflux- qubits.WeexplicitlydemonstratetheeffectofthesegeometricinteractionswhenQAisperformedwithasystem ofoneandtwocoupledflux-qubits. Therealizationofnon-stoquasticHamiltonianshasimportantimplications 7 fromacomputationalcomplexityperspective,sinceitisbelievedthatinmanycasesQAwithstoquasticHamil- 1 0 tonianscanbeefficientlysimulatedviaclassicalalgorithmssuchasQuantumMonteCarlo. Itiswell-known 2 thatthedirectimplementationofnon-stoquasticinteractionswithflux-qubitsisparticularlychallenging. Our resultssuggestanalternativepathfortheimplementationofnon-stoquasticinteractionsviageometricphases n thatcanbeexploitedforcomputationalpurposes. a J 5 Introduction.—It is well known that the solution of com- secondorderone[27]. 2 putational problems can be encoded into the ground state of Introducingnon-stoquasticinteractionsisespeciallyimpor- ] a time-dependent quantum Hamiltonian. This approach is tantinthephysicalimplementationofQAdevices,inorderto h known as adiabatic quantum computation (AQC) [1–3], and allowthemtoescapethetrapofefficientclassicalsimulability. p isuniversalforquantumcomputing[4](forareviewofAQC Asacaseinpoint,andsettingasideheavilydebatedconcerns t- seeRef.[5]).Quantumannealing(QA)isaframeworkthatin- aboutwhethersuchdevicesaresufficientlyquantum[28–33], n corporatesalgorithms[6–8]andhardware[9–13]designedto despite intense efforts [32, 34–40] there is currently no evi- a u solvecomputationalproblemsviaquantumevolutiontowards dence of an example where stoquastic QA hardware such as q the ground states of final Hamiltonians that encode classical theD-Wavedevices[10–12]deliversaquantumspeedupover [ optimization problems, without necessarily insisting on uni- all possible classical algorithms. This is true even though versalityoradiabaticity. in this setting QA is not limited to ground state evolution. 1 QA thus inhabits a regime that is intermediate between However, the implementation of non-stoquastic interactions v 4 the idealized assumptions of universal AQC and unavoid- is technologically challenging, at least with superconducting 9 able experimental compromises. Perhaps the most signifi- flux-qubits. The D-Wave devices, for example, have a scal- 4 cant of these compromises has been the design of stoquas- able design that can only implement the Hamiltonian of the 7 tic quantum annealers. A Hamiltonian H is stoquastic with quantumtransversefieldIsingmodel,whichisstoquastic. To 0 respect to a given basis if H has only real nonpositive off- remedy this would require additional couplings between the . 1 diagonal matrix elements in that basis, which means that its flux qubits, to realize, e.g., σx σx interactions, in addition 0 ground state can be expressed as a classical probability dis- totheexistingσz σz interacti⊗ons. Thisgreatlycomplicates 7 tribution [14, 15]. Typically, one chooses the computational the design of the⊗current generation of superconducting cir- 1 basis, i.e., the basis in which the final Hamiltonian is diag- cuits. : v onal. The computational power of stoquastic Hamiltonians Ratherthanattempttointroducenon-stoquasticityvianew Xi hasbeencarefullyscrutinized, andissuspectedtobelimited components, here we revisit the assumptions that lead to the in the ground-state AQC setting [5]. E.g., it is unlikely that derivation of the Hamiltonian generating the effective time r a ground-statestoquasticAQCisuniversal[16]. Moreover,un- evolution of a continuous-variable system, such as induc- dervariousassumptionsground-statestoquasticAQCcanbe tivelycoupledfluxqubits. Weshowthatnon-stoquasticterms efficientlysimulatedbyclassicalalgorithmssuchasquantum arise naturally as a non-adiabatic geometric phase, due to Monte Carlo [14, 15, 17, 18], though certain exceptions are the Aharonov-Anandan effect [41, 42]. In other words, non- known[19,20]. stoquastictermsareinfactpresentallalongwhenQAisper- Oneisthusnaturallymotivatedtoconsideradeparturefrom formedinsystemsofinductivelycoupledfluxqubits.Westudy the stoquastic setting. Indeed, this is the setting of proofs of these geometric terms in detail, and show that the geometric theuniversalityofAQCandofvariousspecificresultsthatuse effectisamplifiedinproportiontotheinversegapoftheflux non-stoquasticity to improve upon the performance of a sto- Hamiltonian,appearingandthendisappearingduringthean- quastic Hamiltonian [21–26]. For example, it is known that neal. The geometric effect can thus be considered as a type non-stoquasticinteractionsthatareturnedontemporarilydur- of non-stoquastic catalyst [5], with the potential to lead to ing QA can modify the annealing path so that it encounters quantumspeedups[21–27]. Thepresenceofgeometricterms a polynomially small gap rather than an exponentially small alsohasclearexperimentalconsequences. Geometriceffects one, by replacing a first order quantum phase transition by a should be taken into account in the validation of current and 2 future QA devices. Conversely, the same devices could be where τ t/t , and t denotes the final time. Then it f f ≡ usedtoperformexperimentalmeasurementsofnon-trivialge- follows directly from Eq. (5b) that G(t)dt = G(s)ds (see ometricphases. the SM, section B), which shows that G(s) is a geomet- Generalformalismandthegeometricterm.—Forconcrete- ric term, i.e., it depends only on the schedule s (and not ness, we assume that QA is performed by implementing a on its parametrization) [44, 45]. Consequently, W(t ) = f (cid:104) (cid:105) time-dependentHamiltonianthatcanbegenericallyexpressed exp i(cid:82)1Heff(s)ds with the dimensionless effective asfollows: T − 0 Hamiltonian n 1 (cid:88) H(φ,t)=−2EC ∂φ2i +P(φ,t). (1) Heff(s)=tfκ˙(s)H˜(s)−G(s), (6) i=1 wherefromhereonadotdenotesd/ds,andwesets τ for SuchHamiltonianscanberealizedwithsuperconductingflux- ≡ simplicity. Notethatthegeometrictermisnegligibleonlyin qubits [43], in which case the continuous variables φ = the adiabatic limit t . As we shall see, is responsible {anφdi}Eni=1raerperethseenmtsaagncehtaicrgflinugxeesnterragpyp.edThbeyttehremnPfl(uφx-,qtu)biistsa, fortheappearanceoffn→on-∞stoquastictermswhentf isfinite. C Application to QA with superconducting flux qubits.—Let time-dependentpotentialthatcontrolsboththeannealandthe a(s) denote the N lowest energy instantaneous eigen- interactions between qubits. We assume that the lowest 2n {| (cid:105)} states of the original Hamiltonian (1), i.e., H(s)a(s) = energy levels of the Hamiltonian (1) are separated from the E (s)a(s) . We identify the earlier ψ(cid:48)(s) w|ith t(cid:105)hese rest of the spectrum by an energy gap. At sufficiently low a | (cid:105) {| a (cid:105)} eigenstates,sothatW(s)describestheunitaryevolutioninthe temperatures and for a slowly variable potential P(φ,t), the subspacerotatingwiththeinstantaneouseigenbasisofH(s). system of Eq. (1) is then effectively confined to an N = 2n Inthisbasis,theQAprocessisdescribedbythedimensionless dimensionalHilbertspace (t). HN effectiveHamiltonian(6)with: To proceed, we follow the approach introduced by Anan- dan in the discussion of non-adiabatic non-Abelian geomet- H˜ (s) E (s)δ , G (s) a(s)i∂ b(s) . (7) ab a ab ab s ric phases [42]. We first consider the time-evolved N- ≡ ≡(cid:104) | | (cid:105) dimensionalsubspace N(t),whichisdefinedbythemap InQAapplications,theHamiltonian(1)isdesignedsuchthat H its N = 2n lowest energy levels can be put into 1-to-1 cor- U(t): (0) (t)=U(t) (0), (2) HN (cid:55)→HN HN respondencewiththeenergylevelsofatransversefieldIsing where U(t) = exp(cid:16) i(cid:82)tH(t(cid:48))dt(cid:48)(cid:17) is the unitary time- model with n qubits. Thus, there exists a unitary V(s) such T − 0 that,uptoatermproportionaltotheidentitymatrix[32]: evolutionoperator( denotestimeordering),andH(t)isthe Hamiltonian (1). LTet ψ (0) N denote an orthonormal V(s)H˜(s)V†(s)=A(s)H˜X +B(s)H˜Z, (8) {| a (cid:105)}a=1 basisfor (0).Thus, (t)hasabasiswhoseorthonormal N N H H wheretheprofilefunctionsA(s)andB(s)areparticulartothe elementsobeytheSchro¨dingerequation: qubitHamiltonian(seeSM,sectionC),H˜X = (cid:80)n σx is i∂t ψa(t) =H(t)ψa(t) . (3) theusualtransverse-fielddriver,and − i=1 i | (cid:105) | (cid:105) We now define another (arbitrary) orthonormal basis ψ(cid:48)(t) n n forHN(t),suchthat|ψa(0)(cid:105)=|ψa(cid:48)(0)(cid:105). Thenthereex|isatsan(cid:105) H˜Z =(cid:88)hiσiz+(cid:88)Jijσizσjz (9) N N unitary transformation W(t) between the two bases i=1 i>j suc×hthat ψ (t) = (cid:80)N W (t)ψ(cid:48)(t) . Anarbitrarystate |(cid:80)b (cid:105) a=1 ab | a (cid:105) is the problem Hamiltonian whose ground state encodes the ω(0) = ω (0)ψ (0) (0)thusevolvesaccording t|o: ω(cid:105)(t) =a (cid:80)a ω| (a0)ψ(cid:105)(∈t)HN= (cid:80) ω (t)ψ(cid:48)(t) , where answer to the optimization problem of interest. The unitary | (cid:80)(cid:105) a a | a (cid:105) a a | a (cid:105) V(s)isthetransformationbetweentheenergyeigenbasisand ω (t) W (t)ω (0).TheunitaryW(t)canthusbecon- siadered≡asdbescraibbingtbheeffectiveevolutionofthestate ω(t) the computational basis |ψaC(s)(cid:105). Note that the geometric | (cid:105) termtransformsasageometricconnection[42](seeSM,sec- insidethesubspace (t)intheframerotatingwiththebasis ψ(cid:48)(t) (we derive tHheNevolution equation of this basis in the tionD): | a (cid:105) SM,sectionA).Bysubstitutingthebasistransformationinto GC(s)=V(s)G(s)V†(s)+iV(s)V˙†(s). (10) Eq.(3)oneeasilyfinds: Quantumannealingofasystemofnflux-qubitscontrolledby i∂ W(t)=Heff(t)W(t), Heff(t) H˜(t) G(t), (4) t theHamiltonian(1)isthendescribedbythefollowingeffec- ≡ − tiveHamiltonianinthecomputationalbasis: whereH˜(t)andG(t)aretheN N matricesdefinedbythe × followingmatrixelements,respectively: (cid:16) (cid:17) Heff,C(s)=t A(s)H˜X +B(s)H˜Z GC(s). (11) f H˜ (t) ψ(cid:48)(t)H(t)ψ(cid:48)(t) , (5a) − ab ≡(cid:104) a | | b (cid:105) G (t) ψ(cid:48)(t)i∂ ψ(cid:48)(t) . (5b) The first term, proportional to tf, is the usual Hamiltonian ab ≡(cid:104) a | t| b (cid:105) discussedinliteratureinthecontextofQA.Thesecondterm Let us now assume that H(t) depends on t only via the in- hasageometricoriginandisnon-vanishingforfiniteanneal- vertibleanddifferentiable“annealingschedule”s κ−1(τ), ing times t . The geometric term is non-stoquastic. To see f ≡ 3 8 1 0.9 6 0.8 4 0.7 0.6 2 0.5 0.4 0 0.3 -2 0.2 0.1 -4 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 (a) (b) FIG.1.Onequbit.(a)AnnealingschedulesA(s)(red)andB(s)(blue),gap∆(s)(black)andthegeometrictermgy(s)(yellow)ofEq.(15). ThefunctionsA(s)andB(s)areobtainedaccordingtotheproceduredescribedintheSM,sectionC.(b)Populationsofthestatesthatare connectedtothefinalgroundstate(solid)andfinalexcitedstate(dashed),fort = 5(ns/2π). Blueandredlinesrepresentsthepopulations f of the two states in the instantaneous energy eigenbasis [Eq. (14)] and the computational basis [Eq. (15)], respectively. Because the two Hamiltoniansareequivalentuptoatime-dependentbasischange,andthefinalbasisisthecomputationalbasisinbothcases,thepopulations at the end of the evolution (s = 1) coincide. Yellow lines represent the populations during the anneal if the geometric term of Eq. (15) isdropped. Theblacklineisthefidelity|(cid:104)ψC (s)|ψC (s)(cid:105)|2 betweenthetime-evolvedstateswith(‘G’subscript)andwithout(‘no-G’ 1,G 1,no-G subscript)geometricinteractions.Resultsshownareforφx (s)=2.9(1−s)+2.2sandparametervaluesfortheflux-qubitHamiltonianthat CJJ matchthoseofthehighlycoherentflux-qubitsstudiedinRef.[46]:E /2π(cid:126)=3.03GHz,E/2π(cid:126)=86.2GHz[thecontrolfluxesφx (s)and S J CJJ φx(s)areshownintheSM,Fig.5(a)]. this, note that the original Hamiltonian (1) is real, and thus We next construct the effective Hamiltonian of Eq. (11). there is a basis choice in which the energy eigenbasis states Westartbynumericallycomputingthegroundstate 0(s) and | (cid:105) a(s) haveonlyrealamplitudes. Consequently, thegeomet- firstexcitedstate 1(s) oftheflux-qubitHamiltonianEq.(13) | (cid:105) | (cid:105) rictermG(s)inEq.(7)isthenapurelyimaginaryHermitian [examples are given in the SM, Figs. 5(b)-5(d)], from which matrix. The transformed geometric term GC(s) [Eq. (10)] is we numerically obtain the effective Hamiltonian [Eq. (6)] in also purely imaginary in the computational basis, since the theinstantaneousenergyeigenbasis: basis change of Eq. (8) can be performed with a real unitary ∆(s) (i.e., orthogonal) matrix V(s). Therefore, including only in- Heff(s)=t σz g(s)σy, (14) teractions up to two-body terms, the geometric term can be 1 f 2 − writteninthemostgeneralformasfollows: (we have ignored a term proportional to the identity ma- (cid:88) (cid:88) trix) where ∆(s) E (s) E (s) is the gap [plotted GC(s)= gy(s)σy+ gxy(s)σxσy+gzy(s)σzσy. ≡ 1 − 0 i i ij i j ij i j in Fig. 1(a)] and g(s) 1(s)∂ 0(s) . We now trans- s i i(cid:54)=j form to the computation≡al b(cid:104)asis|usi|ng th(cid:105)e unitary V(s) = (12) (cid:104) (cid:16) (cid:17) (cid:105) Quantum annealing with geometric terms: one qubit.— exp i arctan A(s) σy , after which the Hamiltonian of 2 B(s) We now apply the results obtained so far to QA with one Eq.(14)becomes qubit. For concreteness we focus on the C-shunt flux-qubit with three Josephson junctions. This qubit can be described H1eff,C(s)=tf[A(s)σx+B(s)σz]−gy(s)σy. (15) bythefollowingHamiltonian[46–48](seeSM,sectionE): This has the form of the most general single-qubit Hamilto- 1 nian: Heff,C(s) = (cid:80) c (s)σα. Itcanbecheckedeas- H (φ,s)= E ∂2+P(φ,s) (13a) 1 α∈x,y,z α 1 −8 S φ ilythat(seeSM,sectionF): (cid:18) (cid:19) 1 P(φ,s)=−2EJ cos[2φxCJJ(s)]cos[φx(s)+2φ]+cosφ , ∆(s)=2(cid:112)A2(s)+B2(s), (16a) (13b) gy(s)=g(s)+ 2 (cid:104)A˙(s)B(s) A(s)B˙(s)(cid:105) . (16b) ∆2(s) − where φ is the flux (in units of Φ /2π) trapped in the super- 0 conducting ring, E is the charging energy of the shunting Bydefiningthecomputationalbasisasthebasisofstateswith S capacitor, and φx (s) and φx(s) are external fluxes used to well-defined persistent current, the annealing schedule func- CJJ controltheanneal. tions A(s) and B(s) [shown in Fig. 1(a)] can be determined 4 1 0.4 0.8 0.3 10 0.6 0.2 0.4 0.1 5 0.2 0 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 0 0.3 0.3 0.2 0.2 -5 0.1 0.1 -10 0 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 (a) (b) FIG.2.Twointeractingqubits.(a)Gaps∆ (s)(black)andthegeometrictermsgy(s),gxy(s),gzy(s)computednumericallyusingEq.(17) k,0 i ij ij forh =1,h =0.4,J =−0.7. (b)Populationsofthestatesoftheinstantaneousbasisthatareconnectedtothefinaleigenstates,forthe 1 2 12 samevalueofthecouplingsasin(a)andt =5(ns/2π).TheblackdottedlineshowninthetopleftpanelisthefidelityasexplainedinFig.1. f ResultsshownareforE /2π(cid:126) = 3.44GHz,E/2π(cid:126) = 684GHz,E /2π = 570GHzandE /2π(cid:126) = 3.98GHz,valuesthataretypicalfor C J L M theD-Wavedevices[10–12][thecontrolfluxesareshownintheSM,Fig.4(a)]. ForconsistencywiththeoneC-shuntfluxqubitcaseweset φx (s)=2.6(1−s)+1.9s,whileintheactualDWdevicesthescheduleischosensuchthatthefieldφx(s)isalinearfunctionofs[wehave CJJ thesamecharacteristicparametricrelationshipφx(φx )]. CJJ in terms of the external fluxes φx and φx of Eq. (13b) (see instantaneous energy eigenbasis [Eq. (6)]. Once again, the CJJ theSM,sectionC).Thus,Eq.(16b)showsthatthesefluxpa- effective Hamiltonian can be expressed in the computational rameters in turn control the properties of the geometric term basisby(numerically)findingaunitaryV suchthatthefinal gy. The profile function gy(s) for the geometric term, also Hamiltonianreads: showninFig.1(a),isnon-vanishingtowardsthemiddleofthe adiabatic evolution, when the gap closes. The effects of the H2eff,C(s,h1,h2,J12)=tfA(s)(σ1x+σ2x)+ (19) geometric term are shown in Fig. 1(b), obtained by numeri- +t B(s)(h σz+h σz+J σzσz) GC(s,h ,h ,J ). f 1 1 2 2 12 1 2 − 1 2 12 callysolvingforthecorrespondingunitaryevolution. Theef- fectsbecomesignificantwhenthegapissmall. Thereisalso This is the usual transverse field Ising model, plus an ad- asignificanteffectonthefinalgroundstatepopulation. ditional geometric term, whose general form is given in Quantum annealing with geometric terms: two qubits.— Eq.(12). Figure2(a)showsthegaps∆k,0 =Ek E0,where − To study the interacting case, we consider two inductively- E 3 aretheorderedeigenvaluesofHeff,C,andthecom- coupled compound Josephson junction flux qubits [46] (see {ponke}nkt=s0ofthegeometrictermGC(s,h ,h2,J )inthecom- 1 2 12 SM,sectionE): putational basis as defined in Eq. (12). Fig. 2(a) shows that, in general, the geometric functions gy(s),gxy(s),gzy(s) are H (φ ,φ ,s,h ,h ,J )=H (φ ,s,h )+ i ij ij 2 1 2 1 2 12 1 1 1 all non-vanishing, and their magnitude grows as the ground +H1(φ2,s,h2)+Pint(φ1,φ2,s,J12), (17) state gap shrinks. In particular, as in the single-qubit case, geometric effects introduce a non-stoquastic contribution to wheretheflux-qubitHamiltonianisgivenby thedrivertermwhichisnon-vanishingtowardsthemiddleof 1 theanneal. Fig.2(b)showstheeffectofthegeometricinter- H1(φ,s,hi)=−4EC∂φ2+P(φ,s,hi) (18a) actions in the annealing of the system of two coupled qubits (cid:20)φx (s)(cid:21) [φ h φx(s)]2 under consideration. As in the single qubit case, we see that P(φ,s,h )=2E cos(φ)cos CJJ +E − i ignoring the geometric terms results in consistently different i J L 2 2 finalpopulationsinthecomputationalbasis. (18b) Dependence on the annealing time.—The contribution of thegeometrictermsisinherentlyanon-adiabaticeffect,aris- andtheinteractionpotentialisexplicitlywrittenas: ing when diabatic transitions populate the excited states. In Pint(φ1,φ2,s,J12)=−J12EM[φ1−φx(s)][φ2−φx(s)]. Fthieg.ti3mew-eevsohlvoewdsthtaetefisdweliitthya|n(cid:104)dψw1C,iGt(hso)u|tψg1Ce,noom-Ge(tsr)ic(cid:105)|t2erbmetsw,aesena Proceeding as in the single qubit case, we start from the functionofthetotalannealingtime.Asexpected,theeffectof Hamiltonian (17) to numerically compute H˜ and G appear- thegeometrictermsincreaseswithdecreasingannealingtime inginEq.(7), andconstructtheeffectiveHamiltonianinthe and it is reflected in the decreasing fidelity. Figure 3 shows 5 1 INSPIRE-1551064. 0.8 AppendixA:Evolutionequationofthe{|ψ(cid:48)(t)(cid:105)}basis a 0.6 Recall that the ψ (t) basis was chosen to satisfy a {| (cid:105)} the Schro¨dinger equation with the given Hamiltonian H(t) 0.4 [Eq. (3)]: ψ˙ (t) = iH(t)ψ (t) , where in this section a a | (cid:105) − | (cid:105) dot denotes ∂ . Here we derive the evolution equation satis- t 0.2 fiedbythe ψ(cid:48)(t) basis,whichisrelatedtothe ψ (t) {| a (cid:105)} {| a (cid:105)} basisviatheunitaryW(t): 0 2 4 6 8 10 12 14 16 18 20 ψ(cid:48)(t) =(cid:88)[W†(t)] ψ (t) . (A1) | b (cid:105) ab| a (cid:105) a FIG.3.Fidelityattheendoftheannealasafunctionoftheannealing Differentiationyields: timeforsinglequbit(blue)andtwoqubits(red). (cid:88) ψ˙(cid:48)(t) = [W˙ †] ψ (t) +[W†(t)] ψ˙ | b (cid:105) ab| a (cid:105) ab| a(cid:105) a that the total annealing time over which this contribution is (cid:88)(cid:16) (cid:17) = [W˙ †] i[W†(t)] H(t) ψ (t) significantisontheorderofafewnanoseconds,forparame- ab ab a − | (cid:105) tersrelevantforcurrentQAdevices.Whilethisissignificantly a (cid:88)(cid:16) (cid:17) shorterthanthetypicalmicrosecondtimescaleofcurrentQA = [W˙ †] i[W†(t)] H(t) W (t)ψ(cid:48)(t) experimentsusingtheD-Wavedevices,thisisthecaseforthe ab− ab ca | c (cid:105) ac oneandtwo-qubitcaseswhichwehaveanalyzedhere. Since, =(cid:88)[WW˙ †] ψ(cid:48)(t) iH(t)ψ(cid:48)(t) . (A2) as is clear from Eq. (16b) and from Fig. 2, the magnitude of cb| c (cid:105)− | b (cid:105) c thegeometrictermgrowsininverseproportiontothegap,we expectittobecomemoresignificantformulti-qubitproblems Thus, the evolution equation satisfied by the basis element whosegapdependencecanbeinversepolynomialorevenex- ψ(cid:48)(t) is ponential.ThiseffectisalreadyvisibleinFig.3,whichshows | a (cid:105) that the fidelity for the two-qubit system tends to be smaller (cid:88) ψ˙(cid:48)(t) = i[H˜eff(t)] ψ(cid:48)(t) iH(t)ψ(cid:48)(t) , (A3) thantheone-qubitsystemforlargerannealingtimes. | a (cid:105) ba| b (cid:105)− | a (cid:105) Conclusions.—We have shown that even the simplest im- b plementationofQAwithflux-qubitsinduceseffectiveHamil- tonians with non-stoquastic interactions arising from a geo- where we used W˙ = iHeff(t)W(t) and unitarity, and de- − metric phase. The appearance of such interactions is ubiqui- finedH˜eff(t) W†(t)Heff(t)W(t). ≡ tous when the Hamiltonian of a continuous-variable system ischangedovertime,andtheevolutionisnon-adiabatic,due to the appearance of the Aharanov-Anandan effect. Since AppendixB:ProofthatGisageometricterm arbitrarily small gaps are inevitable in QA for hard opti- mizationproblems,non-adiabaticevolutionsareultimatelyin- escapable. Wethusarguethat,similarly,thegeometriceffects LetusshowexplicitlythatGisageometricterm,i.e.,that studied here are unavoidable and relevant in practical appli- G(t)dt = G(s)ds where s = κ−1(t/tf). Note that since cations of QA. Moreover, since these geometric effects give we assumed that κ is invertible and differentiable, we can risetonon-stoquastictermsintheeffectiveHamiltonian,they write t = tfκ(s), so that dt = tfdκd(ss)ds and ∂t = ddst∂s = provideanaturalanddesirablemechanismforavoidingclas- 1 (cid:104)dκ(s)(cid:105)−1∂ . Thus sicallyefficientsimulationofQA.Thismaypointtothepossi- tf ds s bilityof“quantumsupremacy”experimentswithQAdevices featuringfewerthan100physicalqubits [49–52]. Gab(t)dt=(cid:104)ψa(cid:48)(t)|i∂t|ψb(cid:48)(t)(cid:105)dt (B1a) (cid:34) (cid:18) (cid:19)−1 (cid:35) 1 dκ(s) dκ(s) = ψ(cid:48)(s)i ∂ ψ(cid:48)(s) t ds (cid:104) a | t ds s | b (cid:105) f ds ACKNOWLEDGMENTS f =G(s)ds, (B1b) We are grateful to Dr. Andrew Kerman for useful dis- cussions. This work was supported under ARO grant num- where in the second line we used the assumption that H(t) berW911NF-12-1-0523, AROMURIGrantNos. W911NF- depends on t only via s, which means, by Eq. (5a), that the 11-1-0268 and W911NF-15-1-0582, and NSF grant number samemustbetrueofψ(cid:48)(t). a 6 AppendixC:PerturbativeDerivationofProfileFunctionsA(s) thenextsection. Figure6showstheratiosbetweentheexact andB(s) gapscomputedbynumericaldiagonalizationofEqs.(13)and (17),andthegapscomputedbydiagonalizingtheHamiltoni- a. CJJFlux-Qubit ans Eqs. (15) and (19) (without geometric terms), when the profilefunctionsA(s)andB(s)arecomputedasdescribedin this section. Due to the perturbative expansion, the method In this section we closely follow Ref. [32] to briefly de- describedinthissectiononlyapproximatelyrecoverstheex- scribehowtheannealingprofilefunctionsA(s)andB(s)can becalculated.Themainobservationisthatthecontrolfluxφx, actgaps. Therelativeerrorislargest(upto2%)inthemiddle oftheanneal,whenthegapsclose. i.e., the bias between the two potential wells, is a small per- turbationforthepotentialofH inEq.(18). Theeigenstates 1 0(s) and 1(s) oftheunperturbedHamiltonianwithφx =0 | (cid:105) | (cid:105) areusedtodefinethestatesofthecomputationalbasis: b. C-shuntFlux-Qubit 1 |↑(s)(cid:105)≡ √2(|1(s)(cid:105)+|0(s)(cid:105))|φx=0 AsintheCJJcase,wewilltreatφxasasmallperturbation. ExpandingtheHamiltonian(13)tofirstorderinφxgives: 1 (s) (1(s) 0(s) ) φx=0. (C1) |↓ (cid:105)≡ √2 | (cid:105)−| (cid:105) | H (φx)=H (φx =0)+2E φxcos(φx /2)sin(2φ). (C6) 1 1 J CJJ Thesesymmetricandantisymmetriccombinationshaveoppo- site and well-defined circulating persistent current along the TheHamiltonianabovehasthefollowingrepresentation: whole anneal, with the persistent current operator defined as Ip =ELφ. Thisjustifiestheuseof (s) and (s) asstates H =A(s)σx+B(s)σz, (C7) |↑ (cid:105) |↓ (cid:105) 1 ofthecomputationalbasis. We can now expand the flux qubit Hamiltonian H in 1 with Eq.(18)tofirstorderinφxtoget: H1(s,φx)=H1(s,φx =0)+φx(s)Ip+ [(φx)2]. (C2) A(s)=((cid:104)↑(s)|H(s,φx =0)|↓(s)(cid:105) O B(s)=2E φxcos[φx (s)/2] (s) sin(2φ ) (s) J CJJ (cid:104)↑ | m |↑ (cid:105)≡ EvaluatingtheHamiltonianaboveinthebasis( (s) , (s) ) φx (s). (C8) |↑ (cid:105) |↓ (cid:105) p thengives(uptoatermproportionaltoidentity)theHamilto- ≡ I nian: ForconsistencywiththeCJJexample,wehavetakenφx(s) H1 =A(s)σx+B(s)σz, (C3) EMEL−2Ip(s)2/Ip(s) with EM−1EL2 = 104GHz, such th≡at B(s)isproportionaltothesquareofthepersistentcurrent. where A(s) (s)H (s,φx =0) (s) ≡(cid:104)↑ | 1 |↓ (cid:105) AppendixD:ProofthatGtransformsasageometricconnection B(s) (s)φx(s)I (s) φx(s)I (s). (C4) p p ≡(cid:104)↑ | |↑ (cid:105)≡ Theprofilefunctionsabovearecompletelycontrolledviathe Let us show that G transforms as in Eq. (10), i.e., that externalfluxesφ (s)andφx(s). GC(s)=V(s)G(s)V†(s)+iV(s)V˙†(s). CJJ Thescheduleofthefluxφx(s)andthusoftheprofilefunc- Recall that we transform from the basis a(s) (e.g., tion B(s) is further constrained in the case of multi-qubit the energy eigenbasis) to the new basis ψ|C(s)(cid:105) (e.g., | a (cid:105) interactions. The interaction potential is given by Eq. (19), the computational basis) using the unitary V(s). Thus, wbyh:ose expectation value in the computational basis is given |pali(csi)t(cid:105)s=-de(cid:80)pebnVdeban(cse)|fψobCr(ssi)m(cid:105).plFicriotym. noBwy odnefiwneitidorno,pGthCe ex=- ab ψC GC ψC = i ψC ψ˙C . Using these two expressions, we (cid:104)↑1(s)↑2(s)|Pint|↑1(s)↑2(s)(cid:105)(cid:39)−J12EMEL−2Ip(s)2, (C5) h(cid:104)avae|: | b(cid:105) (cid:104) a| b(cid:105) fromwhichitfollowsthattheinteractiontermintheeffective G = aGb =i ab˙ = (D1a) HamiltonianisgivenbyHint =−J12EMEL−2Ip(s)2σ1zσ2z. To ab (cid:104)(cid:88)| | (cid:105) (cid:104) | (cid:105)(cid:104) (cid:105) ensurethesameannealingscheduleforthelocalandinterac- =i ψC(s)V† V˙ ψC(s) +V ψ˙C(s) (D1b) tion terms, the control field φx is then chosen to be propor- (cid:104) c | ac bd| b (cid:105) bd| b (cid:105) cd tional to the persistent current φx(s) = E E−2I (s). This (cid:88) (cid:88) M L p =i V†V˙ + V†GCV (D1c) impliesthatB(s)=E E−2I (s)2. ab bd ac cb bd M L p d cd Wehaveconsideredanannealingschedulelinearinthecon- trolfieldφCJJ(s)[seeFig.4(a)]. Thecorrespondingvaluesfor =i(V†V˙)ab+(V†GCV)ab, (D1d) the control flux φx(s) and profile functions A(s) and B(s) are shown in Fig. 4(b) and are computed using the prescrip- i.e.,GC =VGV† iV˙V†,whichgivesthedesiredresultafter tiondescribedinthissection,usingthenumericalmethodsof usingunitaritytow−riteV˙V† = VV˙†. − 7 10-3 10 2.6 15 9 2.5 8 2.4 7 10 2.3 6 2.2 5 2.1 5 4 2 3 2 1.9 0 1 1.8 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 (a) (b) 90 1.2 140 1.6 80 1 1.4 120 0.8 70 1.2 0.6 100 60 1 0.4 50 80 0.8 0.2 40 60 0.6 0 30 0.4 -0.2 40 20 0.2 -0.4 20 10 -0.6 0 0 -0.8 0 -0.2 -1.5 -1 -0.5 0 0.5 1 1.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 (c) (d) FIG.4.CJJflux-qubitEq.18.(a)Thesdependenceofthefluxφx (s)(rightaxis)controlstheannealingschedule.Thefluxφx(s)iscomputed CJJ accordingly.(b)GapandprofilefunctionsA(s)andB(s).(d)ThepotentialP(φ,s)(blacksolidlines),andthecorrespondingwavefunctions of|0(s)(cid:105)(dottedlines)and|1(s)(cid:105)(dashedlines)fordifferentvaluesoftheannealingparameters:(c)s=0.5,and(d)s=1. AppendixE:Flux-QubitHamiltonians tors: p i∂ . ThecorrespondingHamiltonianis: c (cid:55)→− φc TheLangrangianofasuperconductingcircuitwithJoseph- H =−(cid:88)E2C,c∂φ2c−(cid:88)EJ,jcosφj+(cid:88)E2L,l(φl−φxl)2. sonjunctionsisgenericallywrittenasfollows[43]: c j l 1(cid:88) (cid:88) (cid:88)1 = E−1φ˙2+ E cosφ E (φ φx)2, L 2 C,c c J,j j− 2 L,l l− l c. CompoundJosephsonJunction(CJJ)Flux-Qubit c j l (E1) wherethefirsttermisthekineticterm,thesecondisthejunc- The basic design of a CJJ flux-qubit [46] is shown in tion energy, and the third is the induction energy. The φ Fig.7(a). Weassumethesamechargingandjunctionenergies c are the phase differences at each capacitance. The charging for the two Josephson junctions and a negligible inductance energy is E (2e)2/C , where C is the c-th capaci- ofthesmallloop. TheHamiltonianforthisdevicecanthenbe C,c c c ≡ tance and e the electron charge. The junction energies are writtenas: given by E I (Φ /2π), where I is the critical cur- J,j c,j 0 c,j ≡ rEeLn,tlo≡fth(eΦj0-/t2hπju)2n/cLtiol,nw. ThehreeinLdluicstitohneeinnedrugciteisonaroefgtihveenl-btyh HCJJ =−21EC(cid:0)∂φ2L +∂φ2R(cid:1)−EJ(cosφL+cosφR)+ lTohoep.ciTrchueitciosnqjuuganatteizmedobmyenptraomaroetipncg=the∂mLo/m∂φe˙cnt=atoEoC−p,1ceφr˙ac-. + 1EL[(φL φR)/2 φx]2, (E2) 2 − − 8 0.05 2.9 350 1.5 0.045 2.8 300 1 0.04 2.7 250 0.5 0.035 2.6 200 0 0.03 2.5 150 -0.5 0.025 2.4 100 -1 0.02 2.3 50 0.015 2.2 0 -1.5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 -3 -2 -1 0 1 2 3 (a) (b) 350 1.5 400 1.6 300 350 1.4 1 1.2 300 250 1 250 0.5 200 0.8 200 150 0.6 0 150 0.4 100 100 0.2 -0.5 50 50 0 0 -1 0 -0.2 -3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3 (c) (d) FIG.5. C-shuntflux-qubitEq.13. (a)Thesdependenceofthefluxφx (s)(rightaxis)controlstheannealingschedule. Thefluxφx(s) CJJ iscomputedaccordingly. (b)-(d)ThepotentialP(φ,s)(blacksolidlines),andthecorrespondingwavefunctionsof|0(s)(cid:105)(dottedlines)and |1(s)(cid:105)(dashedlines)fordifferentvaluesoftheannealingparameters:(b)s=0,(c)s=0.5,and(d)s=1. i.e.,thesumofthecharging,junctionandinductionenergies isshowninFig.7(b). Westartbywritingthekineticterm: of the circuit. By defining φ (φ φ )/2 and φ = L R CJJ ≡ − 1 (cid:16) (cid:17) 1 (cid:16) (cid:17)2 oφbRta+in:φL we have ∂φL,R = ∂φCJJ ±1/2∂φ , from which we K = 2EC−1 φ˙21+φ˙22+φ˙2L+φ˙2R + 2ES−1 φ˙1−φ˙2 , (E4) H = 1EC∂2 2E cos(cid:18)φxCJJ(cid:19)cosφ+E (φ−φx)2 . where the first term comes from the junctions while the last CJJ −2 2 φ− J 2 L 2 term is the shunting capacitor energy with E = (2e)2/C . S S (E3) BydefiningφCJJ = φR +φL,φ = (φL φR)/2+φ2 φ1 − − and φ = (φ φ )/2 we get φ˙ = φ˙ φ˙ and φ˙ = lswomhcakelreledlowtooepthhineadveuexctnteaernngcaleelcflgteuivdxestφhφxexCtJ.eJrT=mheφ−eCq12JJu(,2aitE.ieoC.,n)t∂ahφ2beCoJflJvuesxirneφcdeCuJJctheiess −fluφ˙xLes±=φCJ−J2anφ˙d−1φ,±warhe2ecroenwsteanhtaavnedsl1eo,t2ckφ˙eCdJJto+=th±φe˙e=x−te0rn,ail.efl.,Ruxthees toEq.(18)withtheredefinitiCoJnJ φx 2π φx . (φCJJ = φxCJJ,φ = φx)duetothesmallinductances. Wecan CJJ (cid:55)→ − CJJ thenrewriteK inEq.(E4)as 1 (cid:16) (cid:17) 1(cid:18)E (cid:19)−1 d. CapacitivelyShunted(C-shunt)Flux-Qubit K = E−1 2φ˙2 +10φ˙2 + S φ˙2 2 C + − 2 4 − (cid:39) (cid:18) (cid:19)−1 The basic design of a C-shunt flux-qubit [46, 47] involves 1 E S φ˙2 , (E5) fourJosephsonjunctionsandalargeshuntingcapacitanceand (cid:39) 2 4 − 9 1 1.03 1.02 0.995 1.01 0.99 1 0.99 0.985 0.98 0.98 0.97 0.96 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 (a) (b) FIG.6. (a)OneC-shuntflux-qubitwith: ratiobetweentheexactgap∆(s)andthegapestimatedviatheperturbativeapproachdescribedin sectionCusedtodefinethecomputationalbasisalongtheannealandcomputetheprofilefunctionsA(s)andB(s). (b)TwocoupledCJJ flux-qubitswithh = 1,h = 0.4,J = −0.7: similarratiosbetweentheexactgapsandthegapscomputedwiththeHamiltonianwritten 1 2 12 inthecomputationalbasis. NotethattheexactgapsarewellapproximatedbythemappingtothecomputationalbasisdescribedinsectionC. Thedifferenceislargesttowardsthemiddleoftheanneal,wherethefirstorderapproximationinthecontrolfluxφxisislessaccurate. (E ,E ) (E ,E ) (E ,E ) (E ,E ) C J C J C J C J �x E �x E L L � �x � � �x � L" CJJ R# L" CJJ R# (a) (b) FIG.7.(a)CompoundJosephsonJunctionflux-qubit.(b)Capacitivelyshuntedflux-qubit. whereinthelaststepweneglectedthelight(high-frequency) whichreducestoEq.(13)afterwesetφ = 0(i.e. thevalue + mode φ (E E due to the large shunting capacitance). thatminimizethepotential),andrenameφ φ. + S C − (cid:28) (cid:55)→ The potential term due to the Josephson junctions is just the sumofthefourjunctionenergies: AppendixF:DerivationofEq.(16) P = E (cosφ +cosφ +cosφ +cosφ ) (E6) J 1 2 L R − =−2EJ[cosφ−cosφ++cos(φxCJJ/2)cos(φx+2φ−)] . TheeffectiveHamiltonianEq.(14)H1eff(s) = tf∆2(s)σz − g(s)σy iswritteninthebasisdefinedbytheinstantaneousen- WethengetthefinalHamiltonianfortheC-shuntqubit: ergyeigenbasis. Amoreconventionalchoiceistorewritethe Hamiltonianaboveinthecomputationalbasis,asinEq.(15). (cid:18) (cid:19) 1 E H = S ∂2 + (E7) Thiscanbedoneviaaunitarytransformationoftheform −2 4 φ− 2E [cosφ cosφ +cos(φx /2)cos(φx+2φ )] , V(s)=exp[iθ(s)σy] , (F1) − J − + CJJ − 10 withθ(s)tobedetermined. Now, We first discretized the flux-qubit Hamiltonian Eq. (1). For example, the one-qubit Hamiltonian Eq. (13a) is reduced to V(s)σzV†(s)= sin[2θ(s)]σx+cos[2θ(s)]σz, (F2) thefollowingL-dimensionalsystem: − fromwhichwefind,usingEq.(8):   2 1 − A(s)= ∆(s)sin[2θ(s)], B(s)= ∆(s)cos[2θ(s)], Hdiscr(φ,s,h) EC (L−1)2  1 ... ... + 2 2 (F3) 1 ≈− 8 (φL−φ−L)2  ... ... 1  fromwhichEq.(16a)follows. Forthegeometrictermweuse 1 2 − Eq.(10)toget P(φ ,s,h)  0 P(φ ,s,h) gy(s)σy ≡(cid:104)V(s)g(s)σyV(cid:105)†(s)+iV(s)V˙†(s) + 1 ...  , = g(s)+θ˙(s) σy. (F4) P(φ ,s,h) L−1 Sinceθ(s)=arctan[A(s)/B(s)]/2,wehave: wherethefirsttermisthediscretizedLaplacianandthecon- tinuousfluxφisdiscretizedasφ =φ +i(φ φ )/(L i −L L −L 2 (cid:104) (cid:105) 1),i=0,...,L 1,withLbeingthesizeofth−emesh. Sim−- θ˙(s)= A˙(s)B(s) A(s)B˙(s) . (F5) − ∆2(s) − ilarly we can discretize the two-qubit Hamiltonian Eq. (17) to obtain an L2-dimensional system. We used L = 600, CombiningthelasttwoequationsyieldsEq.(16b)reportedin whichwassufficientfornumericalconvergence. Wenumeri- themaintext. callycomputedallthestaticfunctionsonameshof100points fortheannealingparameters. Thevalueofallfunctionsatall otherintermediatepoints,whenrequired,wherecomputedvia AppendixG:NumericalMethodology acubicinterpolation. Once all the static quantities where computed, the “dy- All the “static” quantities, e.g., the quantities shown in namic”quantitiesofFigs.1(b),2(b)and3werecomputedby Figs.1(a),2(a),4,5and6,aredeterminedatagivenvalueof solvingtheSchro¨dingerequationsresultingfromtheeffective the schedule parameter s by first numerically computing the one-andtwo-qubitHamiltoniansEqs.(14),(15)and(19). We wavefunctions 0(s) and 1(s) [see,e.g.,Fig.4andFig.5]. usedastandardode45solverprovidedwithMatlab. | (cid:105) | (cid:105) [1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and [9] J. Brooke, T. F. Rosenbaum, and G. Aeppli, “Tunable quan- Michael Sipser, “Quantum Computation by Adiabatic Evolu- tum tunnelling of magnetic domain walls,” Nature 413, 610– tion,”arXiv:quant-ph/0001106 (2000). 613(2001). [2] EdwardFarhi,JeffreyGoldstone,SamGutmann,JoshuaLapan, [10] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, AndrewLundgren, andDanielPreda,“AQuantumAdiabatic F.Hamze, N.Dickson, R.Harris, A.J.Berkley, J.Johansson, EvolutionAlgorithmAppliedtoRandomInstancesofanNP- P.Bunyk,E.M.Chapple,C.Enderud,J.P.Hilton,K.Karimi, CompleteProblem,”Science292,472–475(2001). E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, [3] W. van Dam, M. Mosca, and U. Vazirani, “How powerful M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, isadiabaticquantumcomputation?”FoundationsofComputer J. Wang, B. Wilson, and G. Rose, “Quantum annealing with Science,2001.Proceedings.42ndIEEESymposiumon,Foun- manufacturedspins,”Nature473,194–198(2011). dations of Computer Science, 2001. Proceedings. 42nd IEEE [11] M W Johnson, P Bunyk, F Maibaum, E Tolkacheva, A J Symposiumon,279–287(8-11Oct.2001). Berkley,EMChapple,RHarris,JJohansson,TLanting,IPer- [4] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, minov, E Ladizinsky, T Oh, and G Rose, “A scalable con- Seth Lloyd, and Oded Regev, “Adiabatic quantum computa- trolsystemforasuperconductingadiabaticquantumoptimiza- tionisequivalenttostandardquantumcomputation,”SIAMJ. tion processor,” Superconductor Science and Technology 23, Comput.37,166–194(2007). 065004(2010). [5] TameemAlbashandDanielA.Lidar,“Adiabaticquantumcom- [12] R.Harris,M.W.Johnson,T.Lanting,A.J.Berkley,J.Johans- puting,”arXiv:1611.04471 (2016). son, P. Bunyk, E. Tolkacheva, E. Ladizinsky, N. Ladizinsky, [6] Tadashi Kadowaki and Hidetoshi Nishimori, “Quantum an- T. Oh, F. Cioata, I. Perminov, P. Spear, C. Enderud, C. Rich, nealinginthetransverseIsingmodel,”Phys.Rev.E58,5355 S.Uchaikin,M.C.Thom,E.M.Chapple,J.Wang,B.Wilson, (1998). M.H.S.Amin,N.Dickson,K.Karimi,B.Macready,C.J.S. [7] Giuseppe E. Santoro, Roman Martonˇa´k, Erio Tosatti, and Truncik, andG.Rose,“Experimentalinvestigationofaneight- Roberto Car, “Theory of quantum annealing of an Ising spin qubit unit cell in a superconducting optimization processor,” glass,”Science295,2427–2430(2002). Phys.Rev.B82,024511(2010). [8] ArnabDasandBikasK.Chakrabarti,“Colloquium: Quantum [13] PeterL.McMahon,AlirezaMarandi,YoshitakaHaribara,Ryan annealingandanalogquantumcomputation,”Rev.Mod.Phys. Hamerly, Carsten Langrock, Shuhei Tamate, Takahiro Ina- 80,1061–1081(2008). gaki, Hiroki Takesue, Shoko Utsunomiya, Kazuyuki Aihara,