ExactsamplinghardnessofIsingspinmodels B.Fefferman,1 M.Foss-Feig,2,3,1 and A.V. Gorshkov3,1 1Joint Center for Quantum Information and Computer Science, NIST/University of Maryland, College Park, MD 20742 USA 2United States Army Research Laboratory, Adelphi, MD 20783, USA 3Joint Quantum Institute, NIST/University of Maryland, College Park, MD 20742 USA WestudythecomplexityofclassicallysamplingfromtheoutputdistributionofanIsingspinmodel,which canbeimplementednaturallyinavarietyofatomic,molecular,andopticalsystems.Inparticular,weconstructa specificexampleofanIsingHamiltonianthat—aftertimeevolutionstartingfromatrivialinitialstate—produces aparticularoutputconfigurationwithprobabilityverynearlyproportionaltothesquareofthepermanentofa matrixwitharbitraryintegerentries.InasimilarspirittoBosonSampling,theabilitytosampleclassicallyfrom theprobabilitydistributioninducedbytimeevolutionunderthisHamiltonianwouldimplyunlikelycomplexity 7 theoretic consequences, suggesting that the dynamics of such a spin model cannot be efficiently simulated 1 withaclassicalcomputer. PhysicalIsingspinsystemscapableofachievingproblem-sizeinstances(i.e. qubit 0 numbers) large enough so that classical sampling of the output distribution is classically difficult in practice 2 maybeachievableinthenearfuture. UnlikeBosonSampling,ourcurrentresultsonlyimplyhardnessofexact classical sampling, leaving open the important question of whether a much stronger approximate-sampling n hardnessresultholdsinthiscontext. AsreferencedinarecentpaperofBouland,Mancinska,andZhang[1], a ourresultcompletesthesamplinghardnessclassificationoftwo-qubitcommutingHamiltonians. J 1 1 I. INTRODUCTION A ] time B h p It is often taken for granted that quantum computers can J2,1 - efficiently perform certain computational tasks that classical t n computers cannot. But finding a quantum task that, on the z H= Ji,j�ˆix ⌧ˆxj a onehand,admitscompellingcomplexity-theoreticarguments Xi,j u against efficient classical simulation, and on the other hand y q x [ admits experimental demonstration with technology that is feasible in the near future, remains an important and chal- FIG. 1. Schematic of the model: (a) Spins in sublattice (red) 1 A lengingtaskinthefieldofquantuminformationscience. An arecoupledtospinsinsublattice (blue)viaIsingcouplingsσˆxτˆx v B i j extremely exciting line of work, starting with results of Ter- andallofthemstartoffin . Tolowestorderintime, thematrix 7 |↓(cid:105) 6 hal and DiVincenzo and Bremner, Jozsa, and Shepherd, has elementofthetimeevolutionoperatorbetweenaninitialstatewith 1 shownthatquantumcomputersarecapableofsamplingfrom allspinsintializedin|↓(cid:105)andafinalstatewithallqubitsin|↑(cid:105)receives 3 distributions that cannot be sampled exactly by randomized contributionsinwhicheachspinisflippedpreciselyonce(onesuch 0 contributingterm,betweenthespinonthesecondsiteof andthe classicalalgorithms[2,3]. TheBosonSamplingprotocol[4], A . firstspinof ,isshown. 1 proposedbyAaronsonandArkhipov,givesahardnessofsam- B 0 pling result that may be within reach for near-term quantum 7 experiments. Thebasicideaistosendphotonsthroughanet- 1 be done with high fidelity and relative ease, and the ability : workoflinearopticaldevices,arrangedinsuchawaythatthe to massively parallelize spin-spin interactions between large v probabilities of typical output configurations of the photons numbers of qubits is reasonably sophisticated; experiments i X areproportionaltothesquaresofpermanentsofmatriceswith have successfully implemented some simple instances of the r independentandGaussian-distributedrandomentries. Given Isingmodelwithsystemsizesrangingfromtens[9]tomany a reasonableassumptionsaboutthehardnessofcomputingper- hundreds of spins [10]. Moreover, recent developments in manentsofsuchmatrices,theabilitytoefficientlyclassically ion-trappingexperimentsraisetheexcitingprospectofimple- sample from any distribution even close (in total variation mentingarbitraryIsinginteractiongraphsinsystemsof(po- distance)tothisdistributionwouldimplyextremelyunlikely tentially)manytensoftrappedions[11].Forthisreason,find- complexitytheoreticconsequences. ingresultsanalogoustoBosonSamplingforsimplespinmod- Anumberofproof-of-principleexperimentsimplementing elsishighlydesirable,andpotentiallyaffordsasimplerroute BosonSampling have already been carried out [5–8]. How- towardstheexperimentaldemonstrationofanefficientquan- ever, a remaining bottleneck to producing an experimentally tum task that, under extremely plausible assumptions about convincing demonstration of BosonSampling is the techni- classical complexity theory, cannot be efficiently performed cal difficulty of building linear-optical systems that are large byaclassicalsystem[3,12]. enoughandcleanenoughtorealizeBosonSamplinginstances Our goal in this manuscript is to show that the dynamics for which classical sampling is actually difficult. By com- ofanexperimentallyimplementablecommutingspinmodel— parison,statepreparationandreadoutofindividualspinscan theIsingmodelwithnotransversefield—caninduceanout- 2 putdistributionoverthespinstatesthatishardtosamplefrom anexcitedhyperfineleveloftheelectronicground-stateman- classically. Thegeneralstrategy,whichwillbeelaboratedon ifold or a dipole-forbidden optical excitation). The Ising in- below, is to divide a set of Ising spins into two mutually in- teractionscanthenbeimplementedviaaspatially-structured teracting registers, each having N spins (see Fig.1). The N Mølmer-Sørenseninteraction[11,15,16]. spins in the first and second register can be placed in corre- Weconsideraquantumquenchinwhichthesystemisini- spondencewiththeN rowandcolumnlabels,respectively,of tializedattimet=0withallofthespins(inbothregisters)in an N N matrix J; each of the N2 pairwise Ising couplings thespin-downstatealongthez-direction, × J between a spin (i) in one register and a spin (j) in the i,j otherisamatrixelementof J. Byinitializingthesystemina |ψ(0)(cid:105)= |↓(cid:105)i |↓(cid:105)j. (2) spatiallyhomogeneousproductstateandthenlettingitevolve (cid:79)i∈A (cid:79)j∈B underIsinginteractionsforashorttime,itcanbeshownthat WethenallowthesystemtoevolveundertheHamiltonianin asingleprobabilityoftheoutputdistributioninducedbymea- Eq.(1)foratimet. surementisproportionaltothesquareofthepermanentof J, plus an o(1) correction. This is enough, using a tool known as“Stockmeyercounting”[13],toimplyahardnessof“exact III. OUTPUTDISTRIBUTION sampling”result: noefficientclassicalrandomizedalgorithm cansamplefromexactlythisdistribution, underaubiquitous After evolution for a time t under the action of , mea- H hardness assumption (namely, that the Polynomial-time Hi- surementinthezbasissamplesfromtheinducedprobability erarchy does not collapse). Note that in a recent paper [12], distribution BosonSamplingwasdirectlygeneralizedtothecontextofspin Hamiltonians. However, our work encounters the permanent Pt(σ1,...,σN,τ1,...,τN) in a fundamentally different way; an important difference is = σ ,...,σ ,τ ,...,τ exp( i t) ,..., 2, (3) that our results do not rely on a “diluteness criterion”, and |(cid:104) 1 N 1 N| −H |↓ ↓(cid:105)| thus N is set by—as opposed to much less than—the num- whereσj,τj = , . Weareinterestedinjustonesuchproba- ↓ ↑ berofphysicalqubits. Muchlikeother“exactsampling”re- bility, sults,ourresultalsodemonstrateshardnesstoclassicallysam- P P( ,..., )= ,..., exp( it ) ,..., 2 M 2, plefromanydistributioninwhichallprobabilitiesarewithin t ≡ t ↑ ↑ |(cid:104)↑ ↑| − H |↓ ↓(cid:105)| ≡| t| aconstantmultiplicativefactoroftheidealquantumdistribu- toendinthestatewithallspinsinbothregisterspointingup. tion. However, unlike BosonSampling, a recent proposal of BywritinganindividualtermintheHamiltonianas Bremner, MontanaroandShepherd(sometimescalled“IQP” sampling),andQuantumFourierSampling,itisnotyetclear σˆixτˆxj =σˆ+iτˆ+j +σˆ+iτˆ−j +σˆ−iτˆ+j +σˆ−iτˆ−j, (4) whether the distributions we consider can be used to show it is straightforward to see that repeated applications of , an “approximate-sampling” hardness result [3, 4, 14]. This H and thus time evolution, generates population in all possible would show something far stronger: there is no classical al- spinstatesinthezbasis. Expandinge i tasapowerseriesin gorithmthatcansamplefromanydistributioninversepolyno- −H time, the lowest-order in time non-vanishing contribution to mialintotalvariationdistancefromtheidealquantumdistri- thematrixelement M = ,..., exp( it ) ,..., arises bution. t (cid:104)↑ ↑| − H |↓ ↓(cid:105) at order tN, because every spin needs to be flipped at least once. The contributing terms contain exactly N powers of operatorsσˆ+τˆ+, withnorepetitionsoftheindicesiand j, so II. THEMODEL i j that each qubit gets flipped from to exactly one time; |↓(cid:105) |↑(cid:105) see Fig. 2 for an illustration of such a term for N = 3. It is The model we consider consists of 2N spin-1/2 particles, straightforward to show that, to order tN, the matrix element whichwedivideintotwosublatticesofNspinseach,denoted M isgivenby t and (blue and red spins in Fig.1). We consider quench AdynamiBcs under an Ising Hamiltonian with exclusively two- ( it)N N M = − N! J +O(tN+2) body inter-sublattice interactions (but no interactions within t N! × σ(j),j eithersublattice),whichcantakearbitraryintegervalues, (cid:88)σ (cid:89)j=1 =( it)NPer(J)+O(tN+2), (5) − = J σˆxτˆx. (1) H i,j i j wherethesummationisoverallpermutationsσoftheintegers (cid:88)i,j i=1,...,N. Asaresult,anddefiningP = Per(J)2,wehave | | Here,Paulioperatorsσˆ actonthespinsofsublatticeA,while Pt =t2N P +O(t2) . (6) Paulioperatorsτˆ actonthespinsofsublattice . Thesespins B could be, for example, two subsets of ions in a Paul trap, Wenextaimtoplaceaconst(cid:0)raintonhow(cid:1) tmustscalewithN where the and are, respectively, the electronic ground inordertoensurethattheO(t2)additiveerrortothepermanent |↓(cid:105) |↑(cid:105) state and some long-lived metastable state (in general either iso(1)withrespecttothesystemsizeN. 3 A where tim e B η (2 [M(0)δM]+ δM 2)/t2N t ≡ (cid:60) t t | t| δM (2M(0) + δM )/t2N. (11) ≤| t| | t | | t| Fornotationalsimplicity,herewewillassumethattheentries of J aredrawnfromtheset 1,0,1 ;notethatnothingabout {− } our argument would change if arbitrary integers were used, J1,2�ˆ+1⌧ˆ+2 J3,1�ˆ+3⌧ˆ+1 J2,3�ˆ+2⌧ˆ+3 exceptthatthetimet wouldberescaledintheboundsbelow by max(J ). Using ,..., m ,..., N2m σˆx 2m = i,j (cid:104)↑ ↑|H |↓ ↓(cid:105) ≤ (cid:107) (cid:107) FIG.2. Exampleofasingletermcontributingtothematrixelement N2m, M(α) can be bounded as M(α) (N2t)N+2α/(N +2α)!. Mt at lowest order in time (tN, here with N = 3). Here, all spins Therefotre, | t | ≤ areflippedfromdowntoupbyaparticularpairingoffofthespins betweenthe and sublattices.Thedepictedprocesscontributesa (N2t)N term(J1,2×JA3,1×JB2,3)×(t3/3!)toMt. Thesetofallpossibleways |Mt(0)|≤ N! , (12) topairthespinsinsublattice withthespinsinsublattice isin one-to-onecorrespondencewitAhtermsinthepermanentoftheBmatrix δM (N2t)N ∞ (N4t2)α 2(N2t)N(N4t2). (13) t Ji,j,andthusMtisproportionaltothispermanent. | |≤ N! (cid:88)α=1 ≤ N! ThefinalinequalityinEq.(13)isvalidfort2 1/(2N4), be- ≤ IV. HIGHERORDERSINTIME cause 0 ≤ ∞α=1xα ≤ 2x whenever 0 ≤ x ≤ 1/2. Plugging Eqs.(12,13)intoEq.(11)leadsto (cid:80) As discussed above, the lowest-order in time contribution N4N to the matrix element Mt comes at order N. It is not hard to η 4N4t2 1+N4t2 (14) seethatallothercontributingtermsoccuratordermsuchthat t ≤ (N!)2 (cid:18) (cid:19) m N is a positive even integer. In particular, take N to N4N be−the number of times an operator σˆ+iτˆ−j occurs insid+e−the ≤6N4t2(N!)2 ≤t2poly(N)e2N(lnN+1), (15) matrix element, and similarly for N , N , and N , such + ++ that N + N + N + N = m.− Since we nee−d−to flip withthefinalinequalityobtainedbyStirling’sapproximation. ++ + + the same num−b−er of q−ubits−in both registers, we must have Itfollowsimmediatelythatηt =o(1)isguaranteedaslongas N = N . Also,thetotalnumberofflippedqubitsisequal to+2−(N −+N ), and since all qubits need to be flipped, we t=o(e−2NlnN). (16) ++ − −− have N N = N. Now,defining p(n)tobetheparityof ++ − −− theintegern,wehave V. HARDNESSOFSAMPLING p(m)= p(N +N +2N ) ++ + −− − Here we prove our main theorem, establishing a very un- = p(N +N ) ++ likely complexity theoretic consequence which would arise −− = p(N++ N ) naturallyfromthepresumedexistenceofaclassicalalgorithm − −− = P(N), (7) thatsamplesexactlyfromtheoutputdistributiondescribedin thepriorsections. Similarargumentstotheonesketchedhere whichshowsthatm Nisaneveninteger.Thematrixelement areimplicitinotherworksonquantumhardnessofsampling − inquestioncanthereforebeexpandedas resultsstartingwiththeBosonSamplingproposal[4]. We first begin with a very brief overview of the computa- M = ∞ ,..., (−itH)N+2α ,..., ∞ M(α), (8) tional complexity theoretic components necessary to under- t (cid:104)↑ ↑| (N+2α)! |↓ ↓(cid:105)≡ t standthishardnessofsamplingresult. Computingexactlythe (cid:88)α=0 (cid:88)α=0 permanent of an N N matrix X with integer entries is as × hardascomputingthenumberofsatisfyingassignmentstoa andfromabovewehave booleanformula. Wethereforesayitisa#P-hardproblem,as M(0) =( it)NPer(J). (9) establishedbyValiant[17]. When X hasnonnegativeinteger t − entriesthisproblemisalsoin#P. Defining δMt = ∞α=1Mt(α), such that Mt = Mt(0) +δMt, we comFopruotiunrgpmuruplotispelsic,awtievweielsltbimeaintetesrteosttehdeipnetrhmeacnoemnpt.leWxietysaoyf canwrite (cid:80) analgorithmA efficientlycomputesamultiplicativeestimate P = M(0)2+2 [M(0)δM]+ δM 2 to a function f if, given input x, the output of A is within a t | t | (cid:60) t t | t| 1 (cid:15)multiplicativefactorof f(x)intimepolynomialinNand =t2N P +ηt , (10) 1/±(cid:15). AfamousresultofJerrum,SinclairandVigodagivesan (cid:0) (cid:1) 4 algorithm for efficiently computing a multiplicative estimate trivially diagonalized. However, just as with non-interacting to the permanent of a matrix with nonnegative entries [18]. bosons, this point of view stems from a restricted notion of Ontheotherhand,itcanbeshownusingabinarysearchand whatitmeansto“simulate”aquantumsystem. Asinthecase paddingargumentthatcomputingsuchanestimatetotheper- of non-interacting bosons, it is indeed classically efficient to manent(oreventhesquareofthepermanent)ofamatrixwith compute low-order correlation functions of operators in the general integer entries is in fact #P-hard (see e.g., [4, 19]). modelwestudy[21,22],butsamplingfromtheoutputdistri- Therefore computing these estimates are as hard as comput- butionissimplyamoregeneral(andlesstrivial)task. ing the permanent exactly. How powerful is #P? We know Another interesting motivation for our result comes from from Toda’s Theorem that any problem in the Polynomial- thedesiretoclassifyalltwo-qubitcommutingHamiltonians. timehierarchy,orPH,canbesolvedusingtheabilitytosolve Suppose we start in a computational basis state of n qubits, a#P-hardproblem[20]. Beingabitmoreformal,Toda’sthe- and can apply a fixed two-qubit Hamiltonian to any pair of oremtellsusthatPH P#P. qubits. A recent result of Bouland, Mancinska, and Zhang ⊆ Now,foranyN N matrixXdefine X tobetheoutcome gaveahardnessofsamplingclassificationforthismodel[1]. × D distribution from Section III that arises from starting in the Theyprove,inallcasesexcepttheoneweconsider(inwhich ,..., state, evolving for a particular time t under the ac- the two qubit Hamiltonian is X X) that the corresponding t|↓ionof↓th(cid:105)eHamiltonianfromEq.(1)withcouplingconstants sampling task is classically hard⊗, as long as the commuting Ji,j set to the entries of X, and measuring in the z basis. As Hamiltonian is capable of generating entanglement from a showninSectionsIIIandIV,theprobabilityofobservingthe computationalbasisstate. Otherwise,theoutputisinaprod- ,..., outcome at time t is proportional to the square of uct state and clearly classically simulable. Thus our hard- |↑ ↑(cid:105) the permanent of X plus an o(1) correction, provided that t ness result completes the sampling hardness classification of ischosentobeo(e−2NlnN). Noticethatthisprobabilityisex- thecompleteclassoftwo-qubitcommutingHamiltonians(see ponentially small. Therefore, to get any reasonable estimate theirpaperforadditionaldetails[1]). byrepeatedsamplingwewouldneedanexponentialnumber of samples. Indeed, this does not imply an efficient quan- tumalgorithmforcomputingthepermanent. Nonetheless,we can use the fact that a single exponentially small amplitude VII. ACKNOWLEDGMENTS is proportional to the permanent to argue about the classical intractabilityofsamplingfromthisdistribution. Supposewehaveanefficientclassicalsamplerwhichsam- WethankA.DeshpandeandA.Boulandforhelpfuldiscus- plesfromthesamedistribution. Wedefinethistobeaneffi- sions. WealsothankA.Bouland,LauraMancinskaandXue cientrandomizedalgorithmthattakesasinputanN N inte- Zhangforsharinganearlyversionoftheirresults. A.V.G.ac- germatrix X andoutputsasamplefromthedistribu×tion . knowledges support by ARL CDQI, ARO MURI, NSF QIS, X D ARO, NSF PFC at JQI, and AFOSR. This material is based AclassicresultofStockmeyergivesanalgorithmforcomput- upon work supported by, or in part by, the U. S. Army Re- ing a multiplicative estimate to the probability of any given outcomeofanefficientclassicalsamplerinthethirdlevelof searchLaboratoryandtheU.S.ArmyResearchOfficeunder the PH, or Σ [13]. Using this result, together with the pre- contract/grantnumber025989-001. 3 sumedexistenceofanefficientclassicalsamplerforourquan- tumdistribution,wecancomputeamultiplicativeestimateto the square of the permanent of an arbitrary integer matrix in the third level of the PH. As mentioned above, this is a #P- [1] A.Bouland,L.Mancinska, andX.Zhang,in31stConference hardproblem. Thistellsuswecansolveanyproblemin#Pin on Computational Complexity, CCC 2016, May 29 to June 1, thethirdlevelofthePolynomial-timehierarchy, orformally, 2016,Tokyo,Japan(2016)pp.28:1–28:33. thatP#P Σ3. CombiningthiswithToda’stheorem,wehave [2] B.M.TerhalandD.P.DiVincenzo,QuantumInformationand ⊆ thatPH P#P Σ ,andsotheentirePolynomial-timeHier- Computation4,134(2004). archyco⊆llapses⊆tot3hethirdlevel,asclaimed. Therefore,itis [3] M.J.Bremner, R.Jozsa, andD.J.Shepherd,Proceedingsof the Royal Society of London A: Mathematical, Physical and veryunlikelythatanefficientclassicalsamplerforthedistri- EngineeringSciences467,459(2010). butionwithprobabilitiesgivenbyEq.(3)exists. [4] S. Aaronson and A. Arkhipov, Theory of Computing 9, 143 (2013). [5] M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, VI. DISCUSSIONANDIMPLICATIONS S.Aaronson,T.C.Ralph, andA.G.White,Science339,794 (2013). [6] J.B.Spring, B.J.Metcalf, P.C.Humphreys, W.S.Koltham- These results extend several key ideas of BosonSampling mer,X.-M.Jin,M.Barbieri,A.Datta,N.Thomas-Peter,N.K. to the context of spin dynamics under Ising spin Hamiltoni- Langford,D.Kundys,J.C.Gates,B.J.Smith,P.G.R.Smith, ans. Just like non-interacting bosons, the Ising model with- andI.A.Walmsley,Science339,798(2013). out a transverse field is often viewed—from the perspective [7] M.Tillmann,B.Dakic,R.Heilmann,S.Nolte,A.Szameit, and ofmany-bodyquantumphysics—tobetrivial,sinceitcanbe P.Walther,Nat.Photon7,540(2013). 5 [8] A.Crespi,R.Osellame,R.Ramponi,D.J.Brod,E.F.Galvao, (TQC2016),LeibnizInternationalProceedingsinInformatics N.Spagnolo,C.Vitelli,E.Maiorino,P.Mataloni, andF.Scia- (LIPIcs), Vol.61,editedbyA.Broadbent(SchlossDagstuhl– rrino,Nat.Photon7,545(2013). Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016) [9] P.Richerme,Z.-X.Gong,A.Lee,C.Senko,J.Smith,M.Foss- pp.1:1–1:19. Feig, S.Michalakis, A.V.Gorshkov, andC.Monroe,Nature [15] K.MølmerandA.Sørensen,Phys.Rev.Lett.82,1835(1999). 511,198(2014). [16] S. Korenblit, D. Kafri, W. C. Campbell, R. Islam, E. E. Ed- [10] J.G.Bohnet, B.C.Sawyer, J.W.Britton, M.L.Wall, A.M. wards, Z.-X. Gong, G.-D. Lin, L.-M. Duan, J. Kim, K. Kim, Rey, M. Foss-Feig, and J. J. Bollinger, Science 352, 1297 andC.Monroe,NewJ.Phys.14,095024(2012). (2016). [17] L.G.Valiant,TheoreticalComputerScience8,189(1979). [11] S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, [18] M.Jerrum,A.Sinclair, andE.Vigoda,J.ACM51,671(2004). K.Wright, andC.Monroe,Nature536,63(2016). [19] S.Aaronson,inProc.R.Soc.A,Vol.467(TheRoyalSociety, [12] B. Peropadre, A. Aspuru-Guzik, and J. J. Garci-Ripoll, 2011)pp.3393–3405. arXiv:1509.02703 (2015). [20] S.Toda,SIAMJ.Comput.20,865(1991). [13] L.J.Stockmeyer,SIAMJ.Comput.14,849(1985). [21] M.vandenWorm,B.C.Sawyer,J.J.Bollinger, andM.Kast- [14] B.FeffermanandC.Umans,in11thConferenceontheTheory ner,NewJ.Phys.15,083007(2013). of Quantum Computation, Communication and Cryptography [22] M.Foss-Feig,K.R.A.Hazzard,J.J.Bollinger, andA.M.Rey, Phys.Rev.A87,042101(2013).