* Gemma De las CuevasYing XuWolfgang DürHans J. BriegelVancouver, 23rd July 2010@ InnsbruckMaarten Van den Nest @ MPQ GarchingMiguel Angel Martin-Delgado @ MadridUnifying classical spin models using a quantum formalismOutline Motivation Completeness Summary ComplexityThe 4D lattice gauge theory is completeZ2Approximating the partition function of some models is BQP-completeMotivationMotivation Classical spin models:Classical magnetismSpin glassesEconophysicsNeural networks...Motivation Classical spin models:Classical magnetismSpin glassesEconophysicsNeural networks...Toy models to tackle complex systemsMake a simple microscopic model & study the macroscopic behaviorMotivationMany different kinds of classical spin modelsDifferent dimensions, defined on complicated graphs...=Many-body interactions...MotivationMany different kinds of classical spin modelsDifferent dimensions, defined on complicated graphs...=Many-body interactions...Local: lattice gauge theoriesH(s)=−Jsummationdisplay(i,j,k,l)∈∂fsisjskslvlocal flipvH(s)H(sprime)=Symmetries:Global: Ising, Potts ...H(s)=−Jsummationdisplay(i,j)∈Esisjglobal flipH(s)H(sprime)=MotivationCan one relate all these models?By studying one model, can one learn something of other models?MotivationCan one relate all these models?By studying one model, can one learn something of other models?Use Quantum Information tools to relate themCompleteness results:Models with different features can be mapped onto a single model Yes!In equilibrium the crucial quantity: partition functionZ=summationdisplayse−βH(s)CompletenessCompletenessM. Van den Nest, W. Dür, H. J. Briegel, Phys. Rev. Lett. 100, 110501(2008)A model is ‘complete’ Its partition function can specialize (by tuning its coupling strengths) to the partition function of any other classical spin modelon an arbitrary graphM. Van den Nest, W. Dür, H. J. Briegel, Phys. Rev. Lett. 100, 110501(2008)Completeness of the 2D Ising Result:✓ ✓ q-level systems, any q✓ any many-body int.Ising, Potts, ...=Zany classical spin model(J)J.Stat.Mech.(2009)P07001Completeness of classical spin models and universal quantum computationFigure6. The graph state |ϕG〉 (a specific instance of it is drawn in the figure)is generated from the cluster state |C〉 by applying a measurement pattern 〈β|on the cluster. In its turn, the cluster state is generated from the state |ϕ2D〉 bymeasuring all edge qubits VE(denoted by red dots) in the Y basis. Black dotsdenote vertex qubits.where |0Y〉VEis a tensorproduct of the (+1)-eigenstateof Y on all edge qubits,and Σprimeare the local Pauli operatorsappropriatefor the correspondingmeasurement outcomes.To summarize, |C〉 can be generated from |ϕ2D〉 via equation (20), which shows thatalso|ϕ2D〉isauniversalresourcestate. Giventheuniversality of the cluster state, it followsthatany state |ψ〉 (in particularany |ϕG〉) can be generatedfrom |C〉 via equation (19).Together, this implies that any state |ϕG〉 can be generated from |ϕ2D〉 by means of localmeasurements (seefigure 6).We are now ready to establish the connection between the evaluation of Ising partitionfunctionsanduniversalmeasurement-basedquantumcomputation.To doso,considerthefollowing procedure.First, the partitionfunctionof an Ising model on a graphG can beexpressedin the form(6). The stabilizerstate |ϕ2D〉 is obtainedfromtheclusterstate|C〉afterapplyinga certainmeasurement pattern|β〉 (i.e.we consider(19)with|ψ〉 = |ϕ2D〉).Finallythe cluster state |C〉 is obtainedfrom the state |ϕ2D〉 after measuring all edgequbits in the Y basis (see equation (20)andfigure6).This means that the partitionfunctionof the Ising model on the graph G can bewritten asZG({Jab,ha})=A〈γ|ϕ2D〉, (21)where A=2(|E|+|V|+M−n)/2is a constant and |γ〉 is a productstate,|γ〉 =Σ|α〉⊗Σprime|β〉⊗|0Y〉VE. Now, by comparingthe right handsideof (21)with(6)weseethatitcorrespondsto thepartitionfunctionof theIsing modelon a 2Dsquarelatticeevaluatedwith a set ofparameters{Jprimeij,hprimei} determinedby |γ〉.ThisallowsustoconcludethatZGcanbe writtenas follows:ZG({Jab,ha}) ∝Z2D({Jprimeij,hprimei}). (22)In other words, the partitionfunctionof the Ising model on an arbitrarygraphcan berecoveredas a specialinstanceof thepartitionfunctionof theIsing modelon a 2Dsquarelattice. This proves that the 2D Ising model is completefor Ising models on any othergraph.In the above derivation, we have introduced an intermediatestep to go from theresource |ϕ2D〉 to the 2D cluster state |C〉 in orderto show the universality of the statedoi:10.1088/1742-5468/2009/07/P07001 13Z2DIsingwithh(J,Jprime)Jprimelargeron an arbitrary graphM. Van den Nest, W. Dür, H. J. Briegel, Phys. Rev. Lett. 100, 110501(2008)Completeness of the 2D Ising Result:✓ ✓ q-level systems, any q✓ any many-body int.Ising, Potts, ...=Zany classical spin model(J)J.Stat.Mech.(2009)P07001Completeness of classical spin models and universal quantum computationFigure6. The graph state |ϕG〉 (a specific instance of it is drawn in the figure)is generated from the cluster state |C〉 by applying a measurement pattern 〈β|on the cluster. In its turn, the cluster state is generated from the state |ϕ2D〉 bymeasuring all edge qubits VE(denoted by red dots) in the Y basis. Black dotsdenote vertex qubits.where |0Y〉VEis a tensorproduct of the (+1)-eigenstateof Y on all edge qubits,and Σprimeare the local Pauli operatorsappropriatefor the correspondingmeasurement outcomes.To summarize, |C〉 can be generated from |ϕ2D〉 via equation (20), which shows thatalso|ϕ2D〉isauniversalresourcestate. Giventheuniversality of the cluster state, it followsthatany state |ψ〉 (in particularany |ϕG〉) can be generatedfrom |C〉 via equation (19).Together, this implies that any state |ϕG〉 can be generated from |ϕ2D〉 by means of localmeasurements (seefigure 6).We are now ready to establish the connection between the evaluation of Ising partitionfunctionsanduniversalmeasurement-basedquantumcomputation.To doso,considerthefollowing procedure.First, the partitionfunctionof an Ising model on a graphG can beexpressedin the form(6). The stabilizerstate |ϕ2D〉 is obtainedfromtheclusterstate|C〉afterapplyinga certainmeasurement pattern|β〉 (i.e.we consider(19)with|ψ〉 = |ϕ2D〉).Finallythe cluster state |C〉 is obtainedfrom the state |ϕ2D〉 after measuring all edgequbits in the Y basis (see equation (20)andfigure6).This means that the partitionfunctionof the Ising model on the graph G can bewritten asZG({Jab,ha})=A〈γ|ϕ2D〉, (21)where A=2(|E|+|V|+M−n)/2is a constant and |γ〉 is a productstate,|γ〉 =Σ|α〉⊗Σprime|β〉⊗|0Y〉VE. Now, by comparingthe right handsideof (21)with(6)weseethatitcorrespondsto thepartitionfunctionof theIsing modelon a 2Dsquarelatticeevaluatedwith a set ofparameters{Jprimeij,hprimei} determinedby |γ〉.ThisallowsustoconcludethatZGcanbe writtenas follows:ZG({Jab,ha}) ∝Z2D({Jprimeij,hprimei}). (22)In other words, the partitionfunctionof the Ising model on an arbitrarygraphcan berecoveredas a specialinstanceof thepartitionfunctionof theIsing modelon a 2Dsquarelattice. This proves that the 2D Ising model is completefor Ising models on any othergraph.In the above derivation, we have introduced an intermediatestep to go from theresource |ϕ2D〉 to the 2D cluster state |C〉 in orderto show the universality of the statedoi:10.1088/1742-5468/2009/07/P07001 13Z2DIsingwithh(J,Jprime)JprimelargercomplexGDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009)Completeness with real coupl.Analogous for q-level systemsIsing model: Result:J.Stat.Mech.(2009)P07001CompletenessofclassicalspinmodelsanduniversalquantumcomputationFigure12.Concatenationofmergerules. Athickgraylineovercertainvertexqubits(andedgequbitsinbetween)symbolizesthattheyhavetobemerged.Figure13.Measurementpatternforobtainingaplaquettewithadecoratedcrossingstartingfroma2Dsquarelattice.ItinvolvesYmeasurements, andhenceitcorrespondstocomplexparameters.Thefigureshowsexplicitlyhowtheunderlyinggraphchangeswiththemeasurementsapplied.doi:10.1088/1742-5468/2009/07/P07001 23J.Stat.Mech.(2009)P07001CompletenesofclasicalspinmodelsanduniversalquantumcomputationFigure12.Concatenationofmergerules.Athickgraylineovercertainvertexqubits(andedgequbitsinbetween)symbolizesthattheyhavetobemerged.Figure13.Measurementpatternforobtainingaplaquettewithadatedcrossingstartingfroma2Dsquarelattice.ItinvolvesYmeasurements,andhenceitcorrespondstocomplexparameters.Thefigureshowsexplicitlyhowtheunderlyinggraphchangeswiththemeasurementsapplied.doi:10.108/1742-5468/209/07/P070123J.Stat.Mech.(2009)P07001Completeness of classical spin models and universal quantum computationFigure14. We will first obtain a decorated 2D square lattice with crossings from adecorated 2D square lattice. This procedure involves complex parameters. Fromthe latter lattice, we will obtain a decorated 3D square lattice, in a procedurewhich involves only real parameters.Figure 15. Measurement pattern for generating a plaquette without a crossing.The plaquette needs to have the same size as the plaquette with a crossing.This pattern consists of deleting all inner vertices and merging the edges at theboundaries so that only one decoration remains at each side.Now we can proceed with the example. The outline of the procedure is as follows:first, we generate a 2D square lattice with crossings, with all edges decorated, from a2D decorated square lattice. This involves creation of crossings, which correspond tocomplex parameters. Then, we generate a decorated 3D square lattice from the decorated2D square lattice with crossings. This involves only merge and deletion rules, whichcorrespond to real parameters (see figure 14).In order to generate a decorated 2D square lattice with crossings from a decorated2Dsquare lattice, we need to generate plaquetteswithdecoratedcrossings,andplaquetteswithout crossings. To obtain a plaquette with a crossing we proceed as in figure 13.Toobtain a plaquette without a crossing, we only need to select a square in the 2D squarelattice of the same size as in figure 13,anddeleteallverticesinside.Thenwemergethevertices at the boundaries so that only one decoration remains at each side of the square(see figure 15).Now we want to generate a 3D square lattice starting from a 2D square lattice withcrossings by means of the merge and deletion rule alone. To do so, we first embed thefigure shown in figure 16(a), which we call a ‘face’, on the 2D square lattice with crossings(the face can be seen as part of a three-dimensional structure,as will be madeexplicitlaterin figure 19). We do it by tilting every square to the left so that the former vertical lines ofthe squares now coincide with the diagonal lines (going from the upper left corner to thedoi:10.1088/1742-5468/2009/07/P07001 25=realJprimelargerZIsing, any G(J)Z3D Ising(J, Jprime)✓ GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009)Completeness with real coupl.Analogous for q-level systemsIsing model: Result:J.Stat.Mech.(2009)P07001CompletenessofclassicalspinmodelsanduniversalquantumcomputationFigure12.Concatenationofmergerules. Athickgraylineovercertainvertexqubits(andedgequbitsinbetween)symbolizesthattheyhavetobemerged.Figure13.Measurementpatternforobtainingaplaquettewithadecoratedcrossingstartingfroma2Dsquarelattice.ItinvolvesYmeasurements, andhenceitcorrespondstocomplexparameters.Thefigureshowsexplicitlyhowtheunderlyinggraphchangeswiththemeasurementsapplied.doi:10.1088/1742-5468/2009/07/P07001 23J.Stat.Mech.(2009)P07001CompletenesofclasicalspinmodelsanduniversalquantumcomputationFigure12.Concatenationofmergerules.Athickgraylineovercertainvertexqubits(andedgequbitsinbetween)symbolizesthattheyhavetobemerged.Figure13.Measurementpatternforobtainingaplaquettewithadatedcrossingstartingfroma2Dsquarelattice.ItinvolvesYmeasurements,andhenceitcorrespondstocomplexparameters.Thefigureshowsexplicitlyhowtheunderlyinggraphchangeswiththemeasurementsapplied.doi:10.108/1742-5468/209/07/P070123J.Stat.Mech.(2009)P07001Completeness of classical spin models and universal quantum computationFigure14. We will first obtain a decorated 2D square lattice with crossings from adecorated 2D square lattice. This procedure involves complex parameters. Fromthe latter lattice, we will obtain a decorated 3D square lattice, in a procedurewhich involves only real parameters.Figure 15. Measurement pattern for generating a plaquette without a crossing.The plaquette needs to have the same size as the plaquette with a crossing.This pattern consists of deleting all inner vertices and merging the edges at theboundaries so that only one decoration remains at each side.Now we can proceed with the example. The outline of the procedure is as follows:first, we generate a 2D square lattice with crossings, with all edges decorated, from a2D decorated square lattice. This involves creation of crossings, which correspond tocomplex parameters. Then, we generate a decorated 3D square lattice from the decorated2D square lattice with crossings. This involves only merge and deletion rules, whichcorrespond to real parameters (see figure 14).In order to generate a decorated 2D square lattice with crossings from a decorated2Dsquare lattice, we need to generate plaquetteswithdecoratedcrossings,andplaquetteswithout crossings. To obtain a plaquette with a crossing we proceed as in figure 13.Toobtain a plaquette without a crossing, we only need to select a square in the 2D squarelattice of the same size as in figure 13,anddeleteallverticesinside.Thenwemergethevertices at the boundaries so that only one decoration remains at each side of the square(see figure 15).Now we want to generate a 3D square lattice starting from a 2D square lattice withcrossings by means of the merge and deletion rule alone. To do so, we first embed thefigure shown in figure 16(a), which we call a ‘face’, on the 2D square lattice with crossings(the face can be seen as part of a three-dimensional structure,as will be madeexplicitlaterin figure 19). We do it by tilting every square to the left so that the former vertical lines ofthe squares now coincide with the diagonal lines (going from the upper left corner to thedoi:10.1088/1742-5468/2009/07/P07001 25=realJprimelargerZIsing, any G(J)Z3D Ising(J, Jprime)same kind of interactions✓ GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009)Completeness with real coupl.Analogous for q-level systemsIsing model: Result:J.Stat.Mech.(2009)P07001CompletenessofclassicalspinmodelsanduniversalquantumcomputationFigure12.Concatenationofmergerules. Athickgraylineovercertainvertexqubits(andedgequbitsinbetween)symbolizesthattheyhavetobemerged.Figure13.Measurementpatternforobtainingaplaquettewithadecoratedcrossingstartingfroma2Dsquarelattice.ItinvolvesYmeasurements, andhenceitcorrespondstocomplexparameters.Thefigureshowsexplicitlyhowtheunderlyinggraphchangeswiththemeasurementsapplied.doi:10.1088/1742-5468/2009/07/P07001 23J.Stat.Mech.(2009)P07001CompletenesofclasicalspinmodelsanduniversalquantumcomputationFigure12.Concatenationofmergerules.Athickgraylineovercertainvertexqubits(andedgequbitsinbetween)symbolizesthattheyhavetobemerged.Figure13.Measurementpatternforobtainingaplaquettewithadatedcrossingstartingfroma2Dsquarelattice.ItinvolvesYmeasurements,andhenceitcorrespondstocomplexparameters.Thefigureshowsexplicitlyhowtheunderlyinggraphchangeswiththemeasurementsapplied.doi:10.108/1742-5468/209/07/P070123J.Stat.Mech.(2009)P07001Completeness of classical spin models and universal quantum computationFigure14. We will first obtain a decorated 2D square lattice with crossings from adecorated 2D square lattice. This procedure involves complex parameters. Fromthe latter lattice, we will obtain a decorated 3D square lattice, in a procedurewhich involves only real parameters.Figure 15. Measurement pattern for generating a plaquette without a crossing.The plaquette needs to have the same size as the plaquette with a crossing.This pattern consists of deleting all inner vertices and merging the edges at theboundaries so that only one decoration remains at each side.Now we can proceed with the example. The outline of the procedure is as follows:first, we generate a 2D square lattice with crossings, with all edges decorated, from a2D decorated square lattice. This involves creation of crossings, which correspond tocomplex parameters. Then, we generate a decorated 3D square lattice from the decorated2D square lattice with crossings. This involves only merge and deletion rules, whichcorrespond to real parameters (see figure 14).In order to generate a decorated 2D square lattice with crossings from a decorated2Dsquare lattice, we need to generate plaquetteswithdecoratedcrossings,andplaquetteswithout crossings. To obtain a plaquette with a crossing we proceed as in figure 13.Toobtain a plaquette without a crossing, we only need to select a square in the 2D squarelattice of the same size as in figure 13,anddeleteallverticesinside.Thenwemergethevertices at the boundaries so that only one decoration remains at each side of the square(see figure 15).Now we want to generate a 3D square lattice starting from a 2D square lattice withcrossings by means of the merge and deletion rule alone. To do so, we first embed thefigure shown in figure 16(a), which we call a ‘face’, on the 2D square lattice with crossings(the face can be seen as part of a three-dimensional structure,as will be madeexplicitlaterin figure 19). We do it by tilting every square to the left so that the former vertical lines ofthe squares now coincide with the diagonal lines (going from the upper left corner to thedoi:10.1088/1742-5468/2009/07/P07001 25=realJprimelargerZIsing, any G(J)Z3D Ising(J, Jprime)same kind of interactions✓ tradeoff between ‘completeness power’ and real parameters?✓ any dimensions✓ q-level systems, any q✓ any many-body int.realAbelian discreteZ4DZ2LGT(J,Jprime)= Zany classical spin model(J)lattice gauge theoryglobal & local symmetriesCompleteness of the 4D LGTZ2constructivelargerGDlC, W. Dür, H. J. Briegel, M. A. Martin-Delgado, Phys. Rev. Lett. 102, 230502 (2009); New J. Phys. 12, 043014 (2010) Main result: Idea of the proof:lattice gauge theoryCompleteness of the 4D LGTZ2Superclique4D LGTZ2all k-cliques for k=1,...,nwith Ising-type int.real couplingsJ=0,∞ Idea of the proof:lattice gauge theoryCompleteness of the 4D LGTZ2Superclique4D LGTZ2all k-cliques for k=1,...,nwith Ising-type int.real couplingsJ=0,∞ Idea of the proof:lattice gauge theoryCompleteness of the 4D LGTZ2Superclique4D LGTZ2all k-cliques for k=1,...,nwith Ising-type int.real couplingsJ=0,∞ Idea of the proof:lattice gauge theorySuperclique4D LGTZ2J12J23J34J14J1J2J3J4J123J134J124J1234Completeness of the 4D LGTZ2real couplingsJ=0,∞ Idea of the proof:lattice gauge theorySuperclique4D LGTZ2Any Abelian discrete classical spin modelHamiltonian!J12J23J34J14J1J2J3J4J123J134J124J1234Completeness of the 4D LGTZ2real couplingsJ=0,∞ Idea of the proof:lattice gauge theorySuperclique4D LGTZ2Any Abelian discrete classical spin modelHamiltonian!J12J23J34J14J1J2J3J4J123J134J124J1234Completeness of the 4D LGTZ2non planarany many-body int....=...Potts...qqJ.Stat.Mech.(2009)P07001Completenessofclassical spinmodelsanduniversal quantumcomputationFigure14.Wewill firstobtainadecorated2Dsquarelatticewithcrossingsfromadecorated2Dsquarelattice. Thisprocedureinvolvescomplexparameters. Fromthelatterlattice,wewillobtainadecorated3Dsquarelattice,inaprocedurewhichinvolvesonlyrealparameters.Figure15.Measurementpatternforgeneratingaplaquettewithoutacrossing.Theplaquette needs tohave the same size as theplaquette withacrossing.Thispatternconsistsofdeletingallinnerverticesandmergingtheedgesattheboundariessothatonlyonedecorationremainsateachside.Nowwecanproceedwiththeexample.Theoutlineof theprocedureisasfollows:first,wegeneratea2Dsquarelatticewithcrossings,withall edgesdecorated,froma2Ddecoratedsquare lattice. This involves creationofcrossings, whichcorrespondtocomplexparameters.Then,wegenerateadecorated3Dsquarelatticefromthedecorated2Dsquarelatticewithcrossings. Thisinvolvesonlymergeanddeletionrules,whichcorrespondtorealparameters(seefigure14).Inordertogenerateadecorated2Dsquarelatticewithcrossingsfromadecorated2Dsquarelattice, weneedtogenerateplaquetteswithdecoratedcrosings,andplaqueteswithoutcrossings.Toobtainaplaquettewithacrossingweproceedasinfigure13.Toobtainaplaquettewithoutacrossing,weonlyneedtoselectasquareinthe2Dsquarelatticeofthesamesizeasinfigure13,anddeletealverticesinside.Thenwemergetheverticesattheboundariessothatonlyonedecorationremainsateachsideof thesquare(seefigure15).Nowwewanttogeneratea3Dsquarelatticestartingfroma2Dsquarelatticewithcrossingsbymeansof themergeanddeletionrulealone.Todoso, wefirstembedthefigureshowninfigure16(a),whichwecalla‘face’,onthe2Dsquarelatticewithcrossings(thefacecanbeseenaspartofathree-dimensionalstructure,aswillbemadeexplicitlaterinfigure19).Wedoitbytiltingeverysquaretotheleftsothattheformerverticallinesofthesquaresnowcoincidewiththediagonallines(goingfromtheupperleftcornertothedoi:10.1088/1742-5468/2009/07/P07001 25qon high dim.{J1,...,J1234}{J1,...,J1234}{J1,...,J1234}real couplingsJ=0,∞ Quantum formulation of Abelian discrete LGTs6abcdv1234|s〉1:= |(sa+ sb+ sc+ sd)mo d q〉1FI G . 1: T he state |ψLG T〉 pl aces one qua ntum pa rticle (bl uedo ts, lab eled w ith num b ers) at each face, the reby cha racteriz -in g the in teractio n of cla ssic al spin s (bla ck dots, la b ele d wi thle tters) around that face. T he quantum spin at face f1, sf1isob tai ned by sum m ing m odulo q th e values of th e spins at th ebo undary of the face.an d eac h col um n (edge ) con tai ns 2( d − 1) on es, w here dis the dim ensio n of the la ttic e, and the rest are zeros. Inth e case of open boundary conditi ons, th e edges in th ebo undary participate in only (d − 1) fac es.Th ere is a standard way to com pute the stabilizers outof a m at ri x such as A (s ee, e.g. [? ]) . W e first note thatth e rank of th e m atr ix A de pends on the di m ens ion ofth e latti ce d.IfA ha s ful l rank , the n each colum n ofA co rres ponds to one X st abilizer, and there are no Zstabilizers. If A do es no t ha ve ful l rank , the n a set ofm lin early in dependent colu m ns in A co rres ponds to theX st abilizers, and one has to find a se t of |F | − mZstabilizers wh ich are orthogonal to each other and to allX st abilizers.Vi a th is procedure, one can see th at th e sta te |ψLG T〉de fine d on a 2D squa re lattice w ith open bounda ry con-di tions corresponds to the pr oduc t state |+ 〉⊗ |F |,where|+ 〉 is the eig enstate of the Pauli m atrix X ,with eigen-va lu e + 1, X |+ 〉 = |+ 〉. |ψLG T〉 de fine d on a 2D squa rela ttic e w it h perio dic boundary condit io ns corresponds toth e sta te |GH Z 〉 = |0〉⊗ |F |+ |1〉⊗ |F |.Forhigherdimen-si onal lattices, e.g. 3D lattices, the st ate |ψLG T〉 is le sstr ivial.Be low , we w ill use the state |ψLG T〉 de fine d on som ela ttic e as a resource for m easurem ent–based quantumco m putation [? ]inordertoprovethecompletenessof that LG T on that lat tice. T he fac t that |ψLG T〉 de -fine d on a 2D lattice contains eithe r no entang lem ent atal l (op en bou ndary con dition s) or a very sm al l am ou nt ofth em (p eriodic boundary conditi ons), and th us are use-le ss states from the poin t of vie w of m easurem ent–basedqu antum com putation, is in agreem ent w ith the fact that2D Z2LG T s are trivial [? ]andcannotbecomplete.As noti ced in [? ], the fact that |ψLG T〉 is a stabiliz erst ate reveals so m e sy m m etries in the partition function.Th at is, because |ψ〉 is le ft in varia nt under any opera-to r s ∈ S , s|ψ〉 = |ψ〉,this translates into the followingin varia nce in the partit io n functio nZ = 〈α|ψ〉 = 〈α|s|ψ〉. (1 2)Th is im plies that there is another set of couplings, de-te rm ined by 〈αprime| = 〈α|s th at yields th e sam e parti ti onfu nction as the original set 〈α|.B. Me rge and deletion rulesWe n ow p resen t tw o ru les, th e m erg e a n d d eletio n ru le,wh ich allow us to m anipulate the partition function ofam odel and relate it tothe partition function of an-ot her m odel. T he intuitive picture is that the m ergeru le ap plied to a m odel w ith, say, 4 fac es, tran sform sit to a m odel w it h 3 faces, one bein g la rger, and con-ta ining a 6–body inste ad of a 4–body inte racti on (s eeFi g. ?? (a )). An d applying th e deleti on rule to a faceam ou nts to m ap ping it to a m odel w here there is no suchfa ce (see F ig. ?? (b )). Al th ough th ese rules can be gen-er ally defi ned for ZqLG T s, we w ill hen cef orth focu s onth e case Z2,since this is what we require for the proof.(a )(b )FI G . 2: (a) T he m er ge and (b) del et ion rules are tools thatal low us to m ap on e interac tion pat tern to an ot her. Bl ue linesin dic ate faces w here there are in teractio nsMe rge rule. Th e rule works by setting the couplingst rength of a face, sa y Jf,to infinity. In order to see itseffect , we co nsider (?? ), and w e divide each coeffi ci en t byafactorofeβ Jf,|α〉f=summationdisplays1,... ,skeβ Jf(c os[pi (Pe∈∂ fse)mo d 2]− 1)|(summationdisplaye∈∂ fse)mo d 2〉f.(1 3)Si nc e thi s is a rescaling of the ene rgy, thi s do es no t m odi fyth e relevant physics th at one can derive from th e parti -ti on functi on. In E q. (?? )itis clear thatw hen Jf→∞ ,on ly the coeffci en t wi thco s2piq(summationdisplaye∈∂ fse)mo d2=1 , (1 4)i.e . (summationtexte∈∂ fse)mo d2=0 remains non-zero. That is, theov erlap w ith |αf(Jf= ∞ )〉 be com es a pro jection onto theH(s)=−summationdisplayf∈FJfcosbracketleftbigg2piq(s1+...+sk)modqbracketrightbiggHamiltonianPartition function:Completeness of the 4D LGTZ2ZG(J)=summationdisplayse−βH(s) Quantum formulation of Abelian discrete LGTs6abcdv1234|s〉1:= |(sa+ sb+ sc+ sd)mo d q〉1FI G . 1: T he state |ψLG T〉 pl aces one qua ntum pa rticle (bl uedo ts, lab eled w ith num b ers) at each face, the reby cha racteriz -in g the in teractio n of cla ssic al spin s (bla ck dots, la b ele d wi thle tters) around that face. T he quantum spin at face f1, sf1isob tai ned by sum m ing m odulo q th e values of th e spins at th ebo undary of the face.an d eac h col um n (edge ) con tai ns 2( d − 1) on es, w here dis the dim ensio n of the la ttic e, and the rest are zeros. Inth e case of open boundary conditi ons, th e edges in th ebo undary participate in only (d − 1) fac es.Th ere is a standard way to com pute the stabilizers outof a m at ri x such as A (s ee, e.g. [? ]) . W e first note thatth e rank of th e m atr ix A de pends on the di m ens ion ofth e latti ce d.IfA ha s ful l rank , the n each colum n ofA co rres ponds to one X st abilizer, and there are no Zstabilizers. If A do es no t ha ve ful l rank , the n a set ofm lin early in dependent colu m ns in A co rres ponds to theX st abilizers, and one has to find a se t of |F | − mZstabilizers wh ich are orthogonal to each other and to allX st abilizers.Vi a th is procedure, one can see th at th e sta te |ψLG T〉de fine d on a 2D squa re lattice w ith open bounda ry con-di tions corresponds to the pr oduc t state |+ 〉⊗ |F |,where|+ 〉 is the eig enstate of the Pauli m atrix X ,with eigen-va lu e + 1, X |+ 〉 = |+ 〉. |ψLG T〉 de fine d on a 2D squa rela ttic e w it h perio dic boundary condit io ns corresponds toth e sta te |GH Z 〉 = |0〉⊗ |F |+ |1〉⊗ |F |.Forhigherdimen-si onal lattices, e.g. 3D lattices, the st ate |ψLG T〉 is le sstr ivial.Be low , we w ill use the state |ψLG T〉 de fine d on som ela ttic e as a resource for m easurem ent–based quantumco m putation [? ]inordertoprovethecompletenessof that LG T on that lat tice. T he fac t that |ψLG T〉 de -fine d on a 2D lattice contains eithe r no entang lem ent atal l (op en bou ndary con dition s) or a very sm al l am ou nt ofth em (p eriodic boundary conditi ons), and th us are use-le ss states from the poin t of vie w of m easurem ent–basedqu antum com putation, is in agreem ent w ith the fact that2D Z2LG T s are trivial [? ]andcannotbecomplete.As noti ced in [? ], the fact that |ψLG T〉 is a stabiliz erst ate reveals so m e sy m m etries in the partition function.Th at is, because |ψ〉 is le ft in varia nt under any opera-to r s ∈ S , s|ψ〉 = |ψ〉,this translates into the followingin varia nce in the partit io n functio nZ = 〈α|ψ〉 = 〈α|s|ψ〉. (1 2)Th is im plies that there is another set of couplings, de-te rm ined by 〈αprime| = 〈α|s th at yields th e sam e parti ti onfu nction as the original set 〈α|.B. Me rge and deletion rulesWe n ow p resen t tw o ru les, th e m erg e a n d d eletio n ru le,wh ich allow us to m anipulate the partition function ofam odel and relate it tothe partition function of an-ot her m odel. T he intuitive picture is that the m ergeru le ap plied to a m odel w ith, say, 4 fac es, tran sform sit to a m odel w it h 3 faces, one bein g la rger, and con-ta ining a 6–body inste ad of a 4–body inte racti on (s eeFi g. ?? (a )). An d applying th e deleti on rule to a faceam ou nts to m ap ping it to a m odel w here there is no suchfa ce (see F ig. ?? (b )). Al th ough th ese rules can be gen-er ally defi ned for ZqLG T s, we w ill hen cef orth focu s onth e case Z2,since this is what we require for the proof.(a )(b )FI G . 2: (a) T he m er ge and (b) del et ion rules are tools thatal low us to m ap on e interac tion pat tern to an ot her. Bl ue linesin dic ate faces w here there are in teractio nsMe rge rule. Th e rule works by setting the couplingst rength of a face, sa y Jf,to infinity. In order to see itseffect , we co nsider (?? ), and w e divide each coeffi ci en t byafactorofeβ Jf,|α〉f=summationdisplays1,... ,skeβ Jf(c os[pi (Pe∈∂ fse)mo d 2]− 1)|(summationdisplaye∈∂ fse)mo d 2〉f.(1 3)Si nc e thi s is a rescaling of the ene rgy, thi s do es no t m odi fyth e relevant physics th at one can derive from th e parti -ti on functi on. In E q. (?? )itis clear thatw hen Jf→∞ ,on ly the coeffci en t wi thco s2piq(summationdisplaye∈∂ fse)mo d2=1 , (1 4)i.e . (summationtexte∈∂ fse)mo d2=0 remains non-zero. That is, theov erlap w ith |αf(Jf= ∞ )〉 be com es a pro jection onto theH(s)=−summationdisplayf∈FJfcosbracketleftbigg2piq(s1+...+sk)modqbracketrightbiggHamiltonianPartition function:Completeness of the 4D LGTZ2State defined on the faces:Product state with coefficients:|ψG〉=summationdisplayscirclemultiplydisplayf∈F|(s1+···+sk)modq〉f|α(J)〉=circlemultiplydisplayf|αf(Jf)〉|αf(Jf)〉=summationdisplayse∈∂feβJfcos[2piq(s1+...+sk)]|s1+...+sk〉fZG(J)=summationdisplayse−βH(s) Quantum formulation of Abelian discrete LGTs6abcdv1234|s〉1:= |(sa+ sb+ sc+ sd)mo d q〉1FI G . 1: T he state |ψLG T〉 pl aces one qua ntum pa rticle (bl uedo ts, lab eled w ith num b ers) at each face, the reby cha racteriz -in g the in teractio n of cla ssic al spin s (bla ck dots, la b ele d wi thle tters) around that face. T he quantum spin at face f1, sf1isob tai ned by sum m ing m odulo q th e values of th e spins at th ebo undary of the face.an d eac h col um n (edge ) con tai ns 2( d − 1) on es, w here dis the dim ensio n of the la ttic e, and the rest are zeros. Inth e case of open boundary conditi ons, th e edges in th ebo undary participate in only (d − 1) fac es.Th ere is a standard way to com pute the stabilizers outof a m at ri x such as A (s ee, e.g. [? ]) . W e first note thatth e rank of th e m atr ix A de pends on the di m ens ion ofth e latti ce d.IfA ha s ful l rank , the n each colum n ofA co rres ponds to one X st abilizer, and there are no Zstabilizers. If A do es no t ha ve ful l rank , the n a set ofm lin early in dependent colu m ns in A co rres ponds to theX st abilizers, and one has to find a se t of |F | − mZstabilizers wh ich are orthogonal to each other and to allX st abilizers.Vi a th is procedure, one can see th at th e sta te |ψLG T〉de fine d on a 2D squa re lattice w ith open bounda ry con-di tions corresponds to the pr oduc t state |+ 〉⊗ |F |,where|+ 〉 is the eig enstate of the Pauli m atrix X ,with eigen-va lu e + 1, X |+ 〉 = |+ 〉. |ψLG T〉 de fine d on a 2D squa rela ttic e w it h perio dic boundary condit io ns corresponds toth e sta te |GH Z 〉 = |0〉⊗ |F |+ |1〉⊗ |F |.Forhigherdimen-si onal lattices, e.g. 3D lattices, the st ate |ψLG T〉 is le sstr ivial.Be low , we w ill use the state |ψLG T〉 de fine d on som ela ttic e as a resource for m easurem ent–based quantumco m putation [? ]inordertoprovethecompletenessof that LG T on that lat tice. T he fac t that |ψLG T〉 de -fine d on a 2D lattice contains eithe r no entang lem ent atal l (op en bou ndary con dition s) or a very sm al l am ou nt ofth em (p eriodic boundary conditi ons), and th us are use-le ss states from the poin t of vie w of m easurem ent–basedqu antum com putation, is in agreem ent w ith the fact that2D Z2LG T s are trivial [? ]andcannotbecomplete.As noti ced in [? ], the fact that |ψLG T〉 is a stabiliz erst ate reveals so m e sy m m etries in the partition function.Th at is, because |ψ〉 is le ft in varia nt under any opera-to r s ∈ S , s|ψ〉 = |ψ〉,this translates into the followingin varia nce in the partit io n functio nZ = 〈α|ψ〉 = 〈α|s|ψ〉. (1 2)Th is im plies that there is another set of couplings, de-te rm ined by 〈αprime| = 〈α|s th at yields th e sam e parti ti onfu nction as the original set 〈α|.B. Me rge and deletion rulesWe n ow p resen t tw o ru les, th e m erg e a n d d eletio n ru le,wh ich allow us to m anipulate the partition function ofam odel and relate it tothe partition function of an-ot her m odel. T he intuitive picture is that the m ergeru le ap plied to a m odel w ith, say, 4 fac es, tran sform sit to a m odel w it h 3 faces, one bein g la rger, and con-ta ining a 6–body inste ad of a 4–body inte racti on (s eeFi g. ?? (a )). An d applying th e deleti on rule to a faceam ou nts to m ap ping it to a m odel w here there is no suchfa ce (see F ig. ?? (b )). Al th ough th ese rules can be gen-er ally defi ned for ZqLG T s, we w ill hen cef orth focu s onth e case Z2,since this is what we require for the proof.(a )(b )FI G . 2: (a) T he m er ge and (b) del et ion rules are tools thatal low us to m ap on e interac tion pat tern to an ot her. Bl ue linesin dic ate faces w here there are in teractio nsMe rge rule. Th e rule works by setting the couplingst rength of a face, sa y Jf,to infinity. In order to see itseffect , we co nsider (?? ), and w e divide each coeffi ci en t byafactorofeβ Jf,|α〉f=summationdisplays1,... ,skeβ Jf(c os[pi (Pe∈∂ fse)mo d 2]− 1)|(summationdisplaye∈∂ fse)mo d 2〉f.(1 3)Si nc e thi s is a rescaling of the ene rgy, thi s do es no t m odi fyth e relevant physics th at one can derive from th e parti -ti on functi on. In E q. (?? )itis clear thatw hen Jf→∞ ,on ly the coeffci en t wi thco s2piq(summationdisplaye∈∂ fse)mo d2=1 , (1 4)i.e . (summationtexte∈∂ fse)mo d2=0 remains non-zero. That is, theov erlap w ith |αf(Jf= ∞ )〉 be com es a pro jection onto theH(s)=−summationdisplayf∈FJfcosbracketleftbigg2piq(s1+...+sk)modqbracketrightbiggHamiltonianPartition function:Completeness of the 4D LGTZ2ZG(J)=〈α(J)|ψG〉State defined on the faces:Product state with coefficients:|ψG〉=summationdisplayscirclemultiplydisplayf∈F|(s1+···+sk)modq〉f|α(J)〉=circlemultiplydisplayf|αf(Jf)〉|αf(Jf)〉=summationdisplayse∈∂feβJfcos[2piq(s1+...+sk)]|s1+...+sk〉fZG(J)=summationdisplayse−βH(s) Tools to ‘transform’ the model:7|0〉fst ate, and im p ose s the condition (summationtexte∈ ∂ fse)mo d2=0on the re m ai ning term s. D ue to this con dition , on e ofth e spins around f is not free anym ore, but equals thesu m of the other k − 1spins (since it is mod 2), saysb= sa+ sc+ sdin F ig . ?? .T hisconditionissubstitutedin another face w here sbpa rticipa tes, e.g. in F ig. ?? ,thefa ce dep ending on sh+ sg+ se+ sbbe com es sh+ sg+ se+sa+ sc+ sd.T hus,thiseffect ivel y en larges the face, thatis , a 4–b o dy Isin g–typ e in teractio n has b ecom e a 6–b o dyIs ing–typ e interaction by m eans of the m erge rule. N oteth at th is rem aining 6–b o dy inte racti on has a couplingstrength given by the face wh ich has b een enlarged (seeFi g. ?? ).aabbccddeegghhffJf= ∞Jbe g h Ja dc eg h33 44=FI G . 3: M er ge rule. Set ting Jf= ∞ se ts the condition sa+sb+ sc+ sd=0 , and thus, one of the variables becomesde p ende nt, say sb= sa+ sc+ sd.Thisissubstitutedin theri ght face, w hich now dep ends on sh+ sg+ se+ sa+ sc+ sd,i.e.a6–b ody Ising–t yp e interac tion , w ith the cou pling strengt h ofth e enlarged face, Jbe g h(n ow Jab ceg h).Th e concatenation of m erge rules and the gauge fixingof som e part icles al low us to ac hieve k –b ody Ising inter-ac tion s, for an y k .Forexample,inordertogeneratea5–b ody interac tion , w e w ou ld ap ply the sam e pro cess asin F ig . ?? ,and we would gauge fix one ofthe spins at thebo undary, say sa.No te th at selecti ng w hat parti cle on th e b oundary off is dep endent on the others is an arbit rary choic e. T hatis , the face f in F ig . ?? co uld have b een m er ged w ithth e low er or right face (sc, sbde p ende nt, resp ectively;se e F ig. ?? ), or w ith oth er faces if had m ore th an 2 di-me nsions. H ow ever, all choices yield equivalent partitionfu nctions. It is even p ossible to cho ose a differ en t dep en -de nt variabl e for every ne ighb oring face, tha t is, subs ti-tu te th e conditi on for sbon the ri gh t fac e, the con ditionfo r saon the upp er fac e, an d so on . H ow ever, this doesno t lead to any kno w n m o de l.We a lso re m a rk th a t u sin g th e m e rg e ru le to tra n sfo rma k –b ody interac tion to a kprime–b ody interac tion , w ith kprime>k ,is only possible if k ≥ 3, sincekprime=2 k − 2, (1 5)(I n th e case of k =2 the spins would we sitting inth e verti ces and th e inte racti ons w ould b e th rough th eed ges ; how ev er , the argum en t still holds true: applyingth e m erge rule along an edge sim ply create s m ore 2–b o dyin teractio ns).aabbccddffiijjJfprime = ∞ 22Jda bf ij33Jcf ij=FI G . 4: O nce w e set Jf= ∞ it is arbit rary to choose in w hatdi rection thi s face is m erged. H ere, scis chosen to b e thede p ende nt variabl e, and thus f is m erged dow nw ards.De letion ru le. Th is rule is obtained by setting Jf=0 ,th at is, by deleti ng th e inte racti on at face f (F ig. ?? ).No te th at th is corresp onds to pro jecti ng th e face f on toth e sta te |+ 〉 = |0〉 + |1〉,i.e. |αf(Jf=0 )〉 = |+ 〉.aabbccddeegghhJf=0Jbe g hJbe g h=FI G . 5: D el et ion rule. Set ting Jf=0 deletes the interactionin that face.C. M ethod to obtain general n−bo dy interactionsHe re w e show th at a to ta lly general inte racti on b e-tw een n 2–l evel part icles can b e ge nerat ed if al l k –bo dy Ising–type interactions be tw een these n pa rticlesare avai lab le, for an y subset of k pa rticles, and allk =0 , 1,... ,n .Aninteractionpatternbetweenn pa r-ti cles w ith all p ossible k –b ody interac tion s is cal led ak –c lique. W e coi n the term su percliqu e fo r an interactionpa ttern b etw een n pa rticles containi ng all k –c liques, foral l k =0 , 1, 2,... ,n [? ]. A “sup ercliq ue of Isin g–typ e in -te racti ons” is a sup erclique such th at all its inte racti onsare Ising–t yp e; in this w ork , w hen w e re fer to a sup er-cl ique, w e w ill m ea n this kind of sup er cl ique. H en ce,we claim th at a totally gen eral interaction b etwe en npa rticles can b e gene rated by pr epa ring a sup erclique ofIs ing–typ e interactions am ong them , and tuning its cou-pl ing streng ths appr opr iately.In order to prove the claim , first note that a generalin teractio n b etw een n sp ins corresp onds to assi gning adi ffer en t en er gy λsto each spin configurati on s.Letusin dic ate w it h a subin dex on the couplin g strength w hic hpa rticles pa rticipa te in a given interaction of the sup er-cl ique; e. g. J123is the couplin g strength of the 3–b o dyin teractio n b etw een s1,s2an d s3.Hence,weneedtosh ow that the coupling st rengths in the su p erclique canFixing the spins using the gauge symmetry:No loops!Deletion rule:Merge rule:JbeghJadceghacde=abcdeb ghghJf=∞sb=sa+sc+sdCompleteness of the 4D LGTZ210cializes to a general n–body interaction. Note that herethe dependence on r1and r2also cancels, since the largeblue face depends on each of them twice (and the sum ismo d 2, thus r1+ r1=0,andsimilarlyforr2).4–b ody interactions can be generated similarly. Inthis case, the four logical particles are distributed closeto each other as shown in Fig. ??,andallcoverfacesare merged to give rise to the Ising–type interactionJ1234(−1)s1+s2+s3+s4. The procedure for the 5–body in-teraction analogous; in this case, one adds one more log-ical spin and merges the overall cover face (see ??).s1s2s3s4r1r2r3J1234FIG. 9: 4–body Ising–type interaction between spins s1,s2,s3and s4with coupling strength J1234.SeethecaptionofFig.??for an explanation of the symbols.s1s2s3s4s5r1r2r3r4J12345FIG. 10: 5–body Ising–type interactionJ12345(−1)s1+s2+s3+s4+s5.SethecaptionofFig.??for an explanation of the symbols.The generalization to k–body Ising–type interactions,for arbitrary k,isstraightforward.First,onepropagateseach of the “logical spins” s1,...,skin the lattice un-til they are as close to each other as possible, forminga “rectangular” shape without their red u–shapes touch-ing each other (as is the case for the 2–, 3–, 4– and 5–body interaction shown above). One can imagine this asadding more logical particles on the right of the 5–b odyinteraction of Fig. ??,therebyenlargingthe“rectangle”in length, until one has k logical particles, analogouslyto how particles have been “added” in the generationof the 5–b ody interaction when compared with a 3– or4–b ody interaction. Then one merges all cover faces ex-cept for one. This renders the k–body Ising–type interac-tion J1...k(−1)s1+...+sk,wherethecouplingJ1...kis deter-mined by the only cover face that has not been merged.The dependence on all auxiliary spins r1,r2,... will can-cel because, by construction, the boundary of the mergedface depends on them twice. The coupling strengths J1...kwill be tuned so that the Hamilton function of the super-clique equals the Hamilton function of the specific finalmo del (which we will refer to as the “target” mo del),according to Eq. (??).Thus, we have shown how to obtain k−body Ising–type interactions, for any k =1,... ,n.Nowwemustleteach spin participate in 2n−1interactions, as pointed outin (??). However, we have seen that a spin propagatesas in Fig. ??,andthispropagationendsinacertainface(called an “end”) that participates in a k–body interac-tion. There it is clear that spin s1can only participate intwo interactions, corresponding to the left and right ends.Mo re generally, the number of ends that an object (or en-coded particle) of dimension dein a lattice of dimensiond has are 2(d − de). Here the logical spin is never prop-agat ed alone, but always “carri es” the other three spinsof an adjacent face fixed (i.e. the shape of Fig. ??(a) ispropagated), hence we essentially have de=2. So,ford =3 theparticleisblockedtohaveonly2ends. Weneed to resort to a 4D lattice to obtain 2(d − de) > 2ends (see Fig. ?? for a replication in four dimensions ofone spin into five other ends). Then, this replication pro-cedure can be multiply applied until the particle has 2n−1ends, that is, one end for each interaction. Note that inthis replication procedure no loops of spins fixed by thegau ge are form ed.s3 s2s1s4s5s6s7s9s8r6r3r2 r1r4 r5r7 r8FIG. 11: Replication of spins in a 4D lattice: s1is replicatedinto s3,s5,s6,s8,s9.Yellowfaceshavethesamemeaningasblue faces, that is, s2propagates into s3by the same meansas it propagat es into s7.Notethatnoloopsofredspinsareformed.We remark that all faces which are not mentioned inthis construction have to be deleted using the deletionrule. We also mention that we have tried several otherprocedur es in order to obtain this result in 3D, but noneof them could avoid the form ation of loops of edges fixedby the gauge.The specific layout of interactions in the superclique isthe following. The logical particles are distributed along4-body10cializes to a general n–body interaction. Note that herethe dependence on r1and r2also cancels, since the largeblue face depends on each of them twice (and the sum ismo d 2, thus r1+ r1=0,andsimilarlyforr2).4–b ody interactions can be generated similarly. Inthis case, the four logical particles are distributed closeto each other as shown in Fig. ??,andallcoverfacesare merged to give rise to the Ising–type interactionJ1234(−1)s1+s2+s3+s4. The procedure for the 5–body in-teraction analogous; in this case, one adds one more log-ical spin and merges the overall cover face (see ??).s1s2s3s4r1r2r3J1234FIG. 9: 4–body Ising–type interaction between spins s1,s2,s3and s4with coupling strength J1234.SeethecaptionofFig.??for an explanation of the symbols.s1s2s3s4s5r1r2r3r4J12345FIG. 10: 5–body Ising–type interactionJ12345(−1)s1+s2+s3+s4+s5.SethecatinofFig.??for an explanation of the symbols.The generalization to k–body Ising–type interactions,for arbitrary k,isstraightforward.First,onepropagateseach of the “logical spins” s1,...,skin the lattice un-til they are as close to each other as possible, forminga “rectangular” shape without their red u–shapes touch-ing each other (as is the case for the 2–, 3–, 4– and 5–body interaction shown above). One can imagine this asadding more logical particles on the right of the 5–b odyinteraction of Fig. ??,therebyenlargingthe“rectangle”in length, until one has k logical particles, analogouslyto how particles have been “added” in the generationof the 5–b ody interaction when compared with a 3– or4–b ody interaction. Then one merges all cover faces ex-cep t for one. This renders the k–body Ising–type interac-tion J1...k(−1)s1+...+sk,wherethecouplingJ1...kis deter-mined by the only cover face that has not been merged.The dependence on all auxiliary spins r1,r2,... will can-cel beca use, by construction, the boundary of the mergedface depends on them twice. The coupling strengths J1...kwill be tuned so that the Hamilton function of the super-clique equals the Hamilton function of the specific finalmo del (which we will refer to as the “target” mo del),accord ing to Eq. (??).Thus, we have shown how to obtain k−body Ising–type interactions, for any k =1,... ,n.Nowwemustleteach spin participate in 2n−1interactions, as pointed outin (??). However, we have seen that a spin propagatesas in Fig. ??,andthispropagationendsinacertainface(called an “end”) that participates in a k–body interac-tion. There it is clear that spin s1can only participate intwo interactions, corresponding to the left and right ends.Mo re generally, the number of ends that an object (or en-coded particle) of dimension dein a lattice of dimensiond has are 2(d − de). Here the logical spin is never prop-agat ed alone, but always “carri es” the other three spinsof an adjacent face fixed (i.e. the shape of Fig. ??(a) ispropagated), hence we essentially have de=2. So,ford =3 theparticleisblockedtohaveonly2ends. Weneed to resort to a 4D lattice to obtain 2(d − de) > 2ends (see Fig. ?? for a replication in four dimensions ofone spin into five other ends). Then, this replication pro-ced ure can be multiply applied until the particle has 2n−1ends, that is, one end for each interaction. Note that inthis replication procedure no loops of spins fixed by thegau ge are form ed.s3 s2s1s4s5s6s7s9s8r6r3r2 r1r4 r5r7 r8FIG. 11: Replication of spins in a 4D lattice: s1is replicatedinto s3,s5,s6,s8,s9.Yellowfaceshavethesamemeaningasblue faces, that is, s2propagates into s3by the same meansas it propagat es into s7.Notethatnoloopsofredspinsareformed.We remark that all faces which are not mentioned inthis construction have to be deleted using the deletionrule. We also mention that we have tried several otherprocedur es in order to obtain this result in 3D, but noneof them could avoid the form ation of loops of edges fixedby the gauge.The specific layout of interactions in the superclique isthe following. The logical particles are distributed along5-bodyConstruction of many-body Ising-type int.:...2-bodyXnk¼ 0nkC18C19¼ 2nJ’s (columns), and 2nC21s’s (ro ws). But by construction allro ws are linearly independent; hence, it has a nonzerodeterminant, and thus it is invertible.2.4. Explicit construction.— We no w use the tools ofSect. 2.2 in order to sho w that we can obtain all interactionsrequired in Sect. 2.3 in a 4D Z2LGT . The proof will requirefixing some spins using the gauge symmetry of the model(i.e., fixing them to zero while lea ving the Hamilton func-tion invariant), a technique which can be applied as long asthe edges whose spins are fix ed form at most a maximaltree (i.e., do not form a closed loop) [11 ].First, a ‘‘single-body interaction’ ’ of s1(analogous to amagnetic field) is obtained by letting s1interact with allother spins around a face fix ed by the gauge [Fig. 2(a) ].A two-body interaction is obtained by mer ging the front,lower and back face and creating the face with blueboundaries of Fig. 2(b) . By fixing with the gauge six ofthe spins at the boundary of the blue face, this face dependsonly on s1þ s2þ r þ r ¼ s1þ s2(since the sum ismod 2) [see Fig. 2(b) ]. Thus, this effecti vely correspondsto a two-body Ising-type interaction between s1and s2withan interaction strength J12. Notice that by setting J12¼ 1as well, we force s1þ s2¼ 0, which can be seen as apropagation of s1into s2(since s1¼ s2). A concatenatedapplication of this two-body interaction results in an effec-tive propagation of a spin through a certain path (the turn-ings of the path can be done similarly).A three-body interaction is obtained by bringing threespins s1, s2, s3close to each other and then mer ging thelar ge blue face as indicated in Fig. 2(c) . The interaction inthe blue face corresponds to a three-body Ising-type inter -action between s1, s2and s3(since r1and r2are summedtwice) and with an interaction strength J123.The generalization to k-body interactions with k C21 4can be done in a similar way as in Fig. 2(c) . The spins sjtaking place in the final k-body interaction are ne ver ad-jacent, and each of them is part of a face at the front, backor side with three spins fix ed by the gauge (red u shapes).All but one of the remaining faces are mer ged, and theinteraction strength J1... kin that face determines the k-bodyIsing-type interaction.Thus we hav e sho wn ho w to obtain k-body Ising-typeinteractions between any group of k particles, for k ¼1; .. .;n (the zero-body interaction required in 2.3 is aconstant factor , so we obtain Z up to this factor). Sincethe total number of interactions is 2n, we only need to sho wthat a given spin can participate in 2n=n interactions. Thismeans that each spin must hav e this number of ‘‘endfaces’ ’, i.e., faces at the end of a propagation that partici-pate in a (man y-body) interaction. Fo r example , if we useFig. 2(b) to propagate s1(i.e. we set J12¼ 1 ), then s1hastwo end faces, the left and the right one, each of which canparticipate in, say , a three-body interaction like the onesho wn in Fig. 2(c) . But, as can be seen from Fig. 2(b) , thepropagation of a particle (in 3D) essentially beha ves as a‘‘pipe’ ’ which has only two end faces. In fact, the numberof ends that an encoded particle of dimension dein a latticeof dimension d can hav e are 2ðd C0 deÞ. Here we essentiallyha ve de¼ 2, and thus for d ¼ 3 the particle is blocked toha ve only 2 ends. We need to resort to a 4D lattice in orderto obtain 2ðd C0 deÞ > 2 ends, and then this replication indif ferent directions can be multiply applied until the par -ticle has 2n=n ends (see Fig. 3 for a replication of one spins1into three other ‘‘end faces’ ’ s3, s5and s6). We refer thereader to [12 ] for the detailed construction. We remark thatall faces which are not mentioned in this construction hav eto be deleted using the deletion rule. We also mention thatwe hav e tried se veral other procedures to obtain this resultin 3D, but none of them could avoid the formation of loopsof edges fix ed by the gauge.This pro ves that we can generate a totally generaln-body interaction between n particles in a 4D Z2LGT .This includes all classical spin models with q ¼ 2 inarbitrary dimensions d, arbitrary graphs, and arbitraryinteraction pattern. Moreo ver, by encoding a q-level par -ticle in mq¼ dlog qe two-le vel particles, this also includesgeneral interactions between n0q-level particles, with n0¼n=mq. This pro ves that the 4D Z2LGT is complete for allAbelian discrete classical spin models, including allAbelian discrete LGTs and discrete SSMs.2.5. Appr oximate completeness for Abelian continuousLGTs and continuous SSMs.— We can go further and sho wthat the 4D Z2LGT is also approximately complete forAbelian continuous models, that is, the partition functionof a continuous model can be exp ressed, up to a certainaccurac y, as a specific instance of the partition function ofthe 4D Z2LGT . To see this, we just need to let q !1 (thelattice spacing remaining discrete) and determine whatapproximation can be obtained (see belo w).2.6. Efficiency results.— The construction presentedabo ve enables one to generate, from a 4D Z2LGT ,Hamilton functions that contain M terms with at mostk-body interactions with an overhead that scales poly( M ,2k) for q ¼ 2. In the case of q-state models with M generalk0-body interaction terms, at most 2k0mqIsing-type inter -actions between k0mqtwo-le vel particles are required foreach term. Therefore, the overhead in the system size of theFIG. 2 (color online). Spins fixed by the gauge are marked inred. A single-body , a two-body and a three-body Ising-typeinteraction with coupling strengths J1, J12, and J123are sho wnin (a), (b), and (c), respecti vel y.PRL 102, 230502 (2009)PHYSICAL REVIEW LET TE RSweek ending12 JUNE 2009230502-33-bodyXnk¼ 0nkC18C19¼ 2nJ’s (columns), and 2nC21s’s (ro ws). But by construction allro ws are linearly independent; hence, it has a nonzerodeterminant, and thus it is invertible.2.4. Explicit construction.— We no w use the tools ofSect. 2.2 in order to sho w that we can obtain all interactionsrequired in Sect. 2.3 in a 4D Z2LGT . The proof will requirefixing some spins using the gauge symmetry of the model(i.e., fixing them to zero while lea ving the Hamilton func-tion invariant), a technique which can be applied as long asthe edges whose spins are fix ed form at most a maximaltree (i.e., do not form a closed loop) [11 ].First, a ‘‘single-body interaction’ ’ of s1(analogous to amagnetic field) is obtained by letting s1interact with allother spins around a face fix ed by the gauge [Fig. 2(a) ].A two-body interaction is obtained by mer ging the front,lo wer and back face and creating the face with blueboundaries of Fig. 2(b) . By fixing with the gauge six ofthe spins at the boundary of the blue face, this face dependsonly on s1þ s2r þ r ¼ s1þ s2(since the sum ismod 2) [see Fig. 2(b) ]. Thus, this effecti vely correspondsto a two-body Ising-type interaction between s1and s2withan interaction strength J12. Notice that by setting J12¼ 1as well, we force s1þ s2¼ 0, which can be seen as apropagation of s1into s2(since s1¼ s2). A concatenatedapplication of this two-body interaction results in an effec-tive propagation of a spin through a certain path (the turn-ings of the path can be done similarly).A three-body interaction is obtained by bringing threespins s1, s2, s3close to each other and then mer ging thelar ge blue face as indicated in Fig. 2(c) . The interaction inthe blue face corresponds to a three-body Ising-type inter -action between s1, s2and s3(since r1and r2are summedtwice) and with an interaction strength J123.The generalization to k-body interactions with k C21 4can be done in a similar way as in Fig. 2(c) . The spins sjtaking place in the final k-body interaction are ne ver ad-jacent, and each of them is part of a face at the front, backor side with three spins fix ed by the gauge (red u shapes).All but one of the remaining faces are mer ged, and theinteraction strength J1... kin that face determines the k-bodyIsing-type interaction.Thus we hav e sho wn ho w to obtain k-body Ising-typeinteractions between any group of k particles, for k ¼1; .. .;n (the zero-body interaction required in 2.3 is aconstant factor , so we obtain Z up to this factor). Sincethe total number of interactions is 2n, we only need to sho wthat a given spin can participate in 2n=n interactions. Thismeans that each spin must hav e this number of ‘‘endfaces’ ’, i.e., faces at the end of a propagation that partici-pate in a (man y-body) interaction. Fo r example , if we useFig. 2(b) to propagate s1(i.e. we set J12¼ 1 ), then s1hastwo end faces, the left and the right one, each of which canparticipate in, say , a three-body interaction like the onesho wn in Fig. 2(c) . But, as can be seen from Fig. 2(b) , thepropagation of a particle (in 3D) essentially beha ves as a‘‘pipe’ ’ which has only two end faces. In fact, the numberof ends that an encoded particle of dimension dein a latticeof dimension d can hav e are 2ðd C0 deÞ. Here we essentiallyha ve de¼ 2, and thus for d ¼ 3 the particle is blocked toha ve only 2 ends. We need to resort to a 4D lattice in orderto obtain 2ðd C0 deÞ > 2 ends, and then this replication indif ferent directions can be multiply applied until the par -ticle has 2n=n ends (see Fig. 3 for a replication of one spins1into three other ‘‘end faces’ ’ s3, s5and s6). We refer thereader to [12 ] for the detailed construction. We remark thatall faces which are not mentioned in this construction hav eto be deleted using the deletion rule. We also mention thatwe hav e tried se veral other procedures to obtain this resultin 3D, but none of them could avoid the formation of loopsof edges fix ed by the gauge.This pro ves that we can generate a totally generaln-body interaction between n particles in a 4D Z2LGT .This includes all classical spin models with q ¼ 2 inarbitrary dimensions d, arbitrary graphs, and arbitraryinteraction pattern. Moreo ver, by encoding a q-level par -ticle in mq¼ dlog qe two-le vel particles, this also includesgeneral interactions between n0q-level particles, with n0¼n=mq. This pro ves that the 4D Z2LGT is complete for allAbelian discrete classical spin models, including allAbelian discrete LGTs and discrete SSMs.2.5. Appr oximate completeness for Abelian continuousLGTs and continuous SSMs.— We can go further and sho wthat the 4D Z2LGT is also approximately complete forAbelian continuous models, that is, the partition functionof a continuous model can be exp ressed, up to a certainaccurac y, as a specific instance of the partition function ofthe 4D Z2LGT . To see this, we just need to let q !1 (thelattice spacing remaining discrete) and determine whatapproximation can be obtained (see belo w).2.6. Efficiency results.— The construction presentedabo ve enables one to generate, from a 4D Z2LGT ,Hamilton functions that contain M terms with at mostk-body interactions with an overhead that scales poly( M ,2k) for q ¼ 2. In the case of q-state models with M generalk0-body interaction terms, at most 2k0mqIsing-type inter -actions between k0mqtwo-le vel particles are required foreach term. Therefore, the overhead in the system size of theFIG. 2 (color online). Spins fixed by the gauge are marked inred. A single-body , a two-body and a three-body Ising-typeinteraction with coupling strengths J1, J12, and J123are sho wnin (a), (b), and (c), respecti vel y.PRL 102, 230502 (2009)PHYSICAL REVIEW LET TE RSweek ending12 JUNE 2009230502-31-bodyXnk¼ 0nkC18C19¼ 2nJ’s (columns), and 2nC21s’s (ro ws). But by construction allro ws are linearly independent; hence, it has a nonzerodeterminant, and thus it is in vertible.2.4 . Explicit construction.— W e no w use the tools ofSect. 2.2 in order to sho w that we can obtain all interactionsrequired in Sect. 2.3 in a 4D Z2LGT . The proof will requirefixing some spins using the gauge symmetry of the model(i.e., fixing them to zero while lea ving the Hamilton func-tion in variant), a technique which can be applied as long asthe edges whose spins are fix ed form at most a maximaltree (i.e., do not form a closed loop) [11 ].First, a ‘‘single-body interaction’ ’ of s1(analogous to amagnetic field) is obtained by letting s1interact with allother spins around a face fix ed by the gauge [Fig. 2(a) ].A two-body interaction is obtained by mer ging the front,lo wer and back face and creating the face with blueboundaries of Fig. 2(b) . By fixing with the gauge six ofthe spins at the boundary of the blue face, this face dependsonly on s1þ s2þ r þ r ¼ s1þ s2(since the sum ismod 2) [see Fig. 2(b) ]. Thus, this ef fecti vely correspondsto a two-body Ising-type interaction between s1and s2withan interaction strength J12. Notice that by setting J12¼ 1as well, we force s1þ s2¼ 0, which can be seen as apropagation of s1into s2(since s1¼ s2). A concatenatedapplication of this two-body interaction results in an ef fec-tive propagation of a spin through a certain path (the turn-ings of the path can be done similarly).A three-body interaction is obtained by bringing threespins s1, s2, s3close to each other and then mer ging thelar ge blue face as indicated in Fig. 2(c) . The interaction inthe blue face corresponds to a three-body Ising-type inter -action between s1, s2and s3(since r1and r2are summedtwice) and with an interaction strength J123.The generalization to k-body interactions with k C21 4can be done in a similar way as in Fig. 2(c) . The spins sjtaking place in the final k-body interaction are ne ver ad-jacent, and each of them is part of a face at the front, backor side with three spins fix ed by the gauge (red u shapes).All but one of the remaining faces are mer ged, and theinteraction strength J1... kin that face determines the k-bodyIsing-type interaction.Thus we hav e sho wn ho w to obtain k-body Ising-typeinteractions between any group of k particles, for k ¼1; .. .;n (the zero-body interaction required in 2.3 is aconstant factor , so we obtain Z up to this factor). Sincethe total number of interactions is 2n, we only need to sho wthat a gi ven spin can participate in 2n=n interactions. Thismeans that each spin must hav e this number of ‘‘endfaces’ ’, i.e., faces at the end of a propagation that partici-pate in a (man y-body) interaction. Fo r example , if we useFig. 2(b) to propagate s1(i.e. we set J12¼ 1 ), then s1hastwo end faces, the left and the right one, each of which canparticipate in, say , a three-body interaction like the onesho wn in Fig. 2(c) . But, as can be seen from Fig. 2(b) , thepropagation of a particle (in 3D) essentially beha ves as a‘‘pipe’ ’ which has only two end faces. In fact, the numberof ends that an encoded particle of dimension dein a latticeof dimension d can hav e are 2ðd C0 deÞ. Here we essentiallyha ve de¼ 2, and thus for d ¼ 3 the particle is blocked toha ve only 2 ends. W e need to resort to a 4D lattice in orderto obtain 2ðd C0 deÞ > 2 ends, and then this replication indif ferent directions can be multiply applied until the par -ticle has 2n=n ends (see Fig. 3 for a replication of one spins1into three other ‘‘end faces’ ’ s3, s5and s6). W e refer thereader to [12 ] for the detailed construction. W e remark thatall faces which are not mentioned in this construction hav eto be deleted using the deletion rule. W e also mention thatwe hav e tried se veral other procedures to obtain this resultin 3D, but none of them could avoid the formation of loopsof edges fix ed by the gauge.This pro ves that we can generate a totally generaln-body interaction between n particles in a 4D Z2LGT .This includes all classical spin models with q ¼ 2 inarbitrary dimensions d, arbitrary graphs, and arbitraryinteraction pattern. Moreo ver , by encoding a q-level par -ticle in mq¼ dlog qe two-le vel particles, this also includesgeneral interactions between n0q-level particles, with n0¼n=mq. This pro ves that the 4D Z2LGT is complete for allAbelian discrete classical spin models, including allAbelian discrete LGTs and discrete SSMs.2.5 . Appr oximate completeness for Abelian continuousLGTs and continuous SSMs.— W e can go further and sho wthat the 4D Z2LGT is also approximately complete forAbelian continuous models, that is, the partition functionof a continuous model can be exp ressed, up to a certainaccurac y, as a specific instance of the partition function ofthe 4D Z2LGT . To see this, we just need to let q !1 (thelattice spacing remaining discrete) and determine whatapproximation can be obtained (see belo w).2.6 . Efficiency results.— The construction presentedabo ve enables one to generate, from a 4D Z2LGT ,Hamilton functions that contain M terms with at mostk-body interactions with an overhead that scales poly( M ,2k) for q ¼ 2. In the case of q-state models with M generalk0-body interaction terms, at most 2k0mqIsing-type inter -actions between k0mqtwo-le vel particles are required foreach term. Therefore, the overhead in the system size of theFIG. 2 (color online). Spins fixed by the gauge are marked inred. A single-body , a two-body and a three-body Ising-typeinteraction with coupling strengths J1, J12, and J123are sho wnin (a), (b), and (c), respecti vel y.PRL 102, 230502 (2009)PHYSICAL REVIEW LET TE RSweek ending12 JUNE 2009230502-3 Construction of the supercliqueJ1(−1)1J12(−1)s1+s2J123(−1)s1+s2+s3J1234(−1)s1+s2+s3+s4J12345(−1)s1+s2+s3+s4+s5Completeness of the 4D LGTZ29th e Ha m ilto n function of a to ta lly general inte ractionof n 2–l evel part icles (e.g. including com plicat ed m an y–bo dy interactions, etc) equals the Hamilton function of aco m plica ted inter act ion patter n (a super clique) , but withsim ple interactions (Ising–type interactions). Th is m ap-pi ng m ay ha ve appl ications in the Ham iltoni an formul a-tion of LGTs [? ]andintheirrenormalizationgroupan alysis [? ].D. Explicit construction of the supercliqueIn the followi ng we show that we can construct a su-pe rclique of Ising–type interactions from a 4D Z2LG T.Be cause of the result of the previ ous section, this m eansth at, by tu ning th e coupling str ength s of th e Ising–typeinteractio ns in the supercliq ue, this m odel can specia liz eto any oth er (Ab elian, discrete ) classical spin m odel.In order to generate the superclique starting from the4D Z2LG T we will only m ake use of the m er ge andde letion rul e, and of the gaug e fix ing .We w ill fi rst sh ow th e gen eration of k–b ody Ising–t ypeinteractio ns, for any k =1 ,...,n in a 3D Z2LG T. Thenwe will argue that the fourth dim ension is needed to repli-ca te the spins, and ther eb y let ea ch spin participate inall the interac tion s re quire d in the superc lique.Fi rst, a “single–body” Ising–type interaction of s1(a nalogous to a m agnetic field), i.e. J1(−1)s1,isobtainedby letting s1interact with all other spin s around a facefix ed by the gaug e (see Fig. ?? (a )).s1s1s2s1s2s3r r1r2(a ) (b ) (c )J1J12J123FI G. 6: “Logica l” spins (i.e. the spins that will participateinth e final superclique) are m arked in bold black. Blue shadedfa ces indicate m erged fa ces as in Fig. ?? ,and spinsfixed byth e gauge are m arked in red. Figures (a ), (b ) and (c ) showasingle–body,a2–body and a3–body Ising–typeinteractionwi th coupling strengths J1, J12an d J123re spectively. Spin rdo es no t pa rticipa te in the interaction becaus e the bl ue facede pends on the m twice, i.e. r + r =0,and the same holds forr1an d r2.A2–body Ising–type interaction is obtained by con-ca ten ating the m er ge rule on the front, lower and backfa ce of a cube and creating the fa ce with blue boundariesof Fig. ?? (b ). This face depends on all of th e spins at itsbo undary (i.e. all spins which are attached to the thick,bl ue line in Fig. ?? (b ), e.g. th e upper, right, and leftsp ins on the front face, the lateral sp ins on the lower face,et c) . Howev er , six of thes e spins are fixed by the gauge(r ed spins in Fig. ?? (b )), th at is, th eir value is fixed tozer o. Hen ce, the big blue face only dep en ds on the spinswh ich are not fixed, that is on s1+ s2+ r + r = s1+ s2(s ince th e sum is perform ed m od 2). This correspondsto th e 2–body Ising–type inte raction between s1an d s2wi th coupling strength determ ined by the only face wh ichha s no t been m erged (the upp er face), viz. J12(−1)s1+s2.Fu rtherm ore, notice that by setting J12= ∞ as well, on een forces s1+ s2=0,i.e.s1= s2.Thiscanbeseenasa“propagation”ofthe value ofs1into s2.A concate-na ted appl ication of thi s 2–body interaction resul ts in aneffect ive propagation of a spin through a cer tain path inth e latti ce (s ee Fig. ?? ). The direction of th is propaga-tion can be changed by m erging all “covering” faces be-tw een the incom ing and the outgoing spin, as indicatedin Fig . ?? . Th is wi ll be im portant in the constructionof the superc lique, where on e needs to prop agat e logi calpa rticles in the 4D lattice to br ing to the pl ace whe re theinteractio n occurs.s1s2s3r1r2FI G. 7: Propagation of a s1to s3by concatenating 2–bodyinteractions with J12= ∞.Particles1ha s two ends (i.e. facesth at can participate in a k–b ody interac tion ): itself, an d theright face where s3is.s1s1s2s2rr(a ) (b )FI G. 8: (a) Turn in the path from a left–to–right propagation(“ incom ing” spin s1)to a down–to–up propagation (“outgo-in g” spin s2). (b ) Sim ilar tu rn, but here s2pr opa gates fromba ck to front. The de pende nc e of each bl ue face on r ca ncel sbe cause it depe nds twice on it.In order to generate a 3–body Ising–type interaction,on e prop agat es thre e “logi cal” spins in the lat tice in ord erto bring as close to each oth er as possible, with th e con-di tion tha t the ir “red u– sha pes” are no t adj acent. The non es m erge s all but on e of the “c over” fac es into a largebl ue face as indi cated in Fig. ?? (c ). This blue face nowco ntains the inter act ion J123(−1)s1+s2+s3,thatis,a 3–bo dy Ising–type interaction be tween s1,s2an d s3as re -qu ired. The interaction strength J123is determ in ed byth e only face th at has not been m erged, and it is th ispa ram eter tha t will be tune d so tha t the sup erclique spe-Propagation9th e Ha m ilto n function of a to ta lly general inte ractionof n 2–l evel part icles (e.g. including com plicat ed m an y–bo dy interactions, etc) equals the Ham ilton function of aco m plica ted inter act ion patter n (a super clique) , but withsim ple interactions (Is ing–type interactions). Th is m ap-pi ng m ay ha ve appl ications in the Ham iltoni an formul a-tion of LG Ts [? ]andintheirrenormalizationgroupan al ysis [? ].D. Explicit construction of the supercliqueIn the followi ng we show that we can construct a su-pe rclique of Ising–type interactions from a 4D Z2LG T.Be cause of the result of the previ ous section, this m eansth at, by tu ning th e coupling str ength s of th e Ising–typeinteractio ns in the supercliq ue, this m odel can specia liz eto any oth er (Ab elian, discrete ) classical spin m odel.In order to generate the superclique starting from the4D Z2LG T we will only m ake use of the m er ge andde letion rul e, and of the gaug e fix ing .We w ill fi rst sh ow th e gen eration of k–b ody Ising–t ypeinteractio ns, for any k =1 ,...,n in a 3D Z2LG T. Thenwe w ill argue that the fourth dim ension is needed to repli-ca te the spins, and ther eb y let ea ch spin participate inal l the interac tion s re quire d in the superc lique.Fi rst, a “single–body” Ising–type interaction of s1(a nalogous to a m agnetic field), i.e. J1(−1)s1,isobtainedby letting s1interact with all other spin s around a facefix ed by the gaug e (see Fig. ?? (a )).s1s1s2s1s2s3r r1r2(a ) (b ) (c )J1J12J123FI G . 6: “Logica l” spins (i.e. the spins that will participateinth e final superclique) are m arked in bold black. Blue shadedfa ces indicate m erged fa ces as in Fig. ?? ,and spins fixed byth e gauge are m arked in red. Figures (a ), (b ) and (c ) showasingle–body,a 2–body and a3–body Ising–type interactionwi th coupling strengths J1, J12an d J123re spectively. Spin rdo es no t pa rticipa te in the interaction becaus e the bl ue facede pends on the m twice, i.e. r + r =0 ,and the same holds forr1an d r2.A2–body Ising–type interaction is obtained by con-ca ten ating the m er ge rule on the front, lower and backfa ce of a cube and creating the fa e with blue boundariesof Fig. ?? (b ). This face depe ds on all of th e spins at itsbo undary (i.e. all spins which are attached to the thick,bl ue line in Fig. ?? (b ), e.g. th e upper, right, and leftsp ins on the front face, the lateral sp ins on the lower face,et c) . Howev er , six of hes e spins are fixed by the gauge(r ed spins in Fig. ?? (b )), th at is, th eir value is fixed tozer o. Hen ce, the big blue face only dep en ds on the spinswh ich are not fixed, that is on s1+ s2+ r + r = s1+ s2(s ince th e sum is perform ed m od 2). This correspondsto th e 2–body Ising–type inte raction between s1an d s2wi th coupling strength determ ined by the only face wh ichha s no t been m erged (the upp er face), viz. J12(−1)s1+ s2.Fu rth erm ore, n otice th at by settin g J12= ∞ as well, on een forces s1+ s2=0,i.e. s1= s2.Thiscanbeseenasa“propagation” ofthe v lue fs1into s2.A concate-na ted appl ication of thi s 2–body interaction resul ts in aneffect ive propagation of a spin through a cer tain path inth e latti ce (s ee Fig. ?? ). The direction of th is propaga-tion can be changed by m erging all “covering” faces be-tw een the incom ing and the outgoing spin, as indicatedin Fig . ?? . Th is wi ll be im portant in the constructionof the superc lique, where on e needs to prop agat e logi calpa rticles in the 4D lattice to br ing to the pl ace whe re theinteractio n occurs.s1s2s3r1r2FI G . 7: Propagation of a s1to s3by concatenating 2–bodyin teractio ns with J12= ∞.Particles1ha s two ends (i.e. facesth at can participate in a k–b ody interac tion ): itself, an d theright face where s3is.s1s1s2s2rr(a ) (b )FI G . 8: (a) Turn in the path from a left–to–right propagation(“ incom ing” spin s1)to a down–to–up propagation (“outgo-in g” spin s2). (b ) Sim ilar tu rn, but here s2pr opa gates fromba ck to front. The de pende nc e of each bl ue face on r ca ncel sbe cause it depe nds twice on it.In order to generate a 3–body Is ing–type inter ction,on e prop agat es thre e “l ogi cal s s in the lat tice in ord erto bring as close to each oth er as possible, with th e con-di tion tha t the ir “red u– sha pes” are no t adj acent. The non es m erge s al l but on e of the “c over” fac es into a largebl ue face as indi cated in Fig. ?? (c ). This blue face nowco ntains the inter act ion J123(−1)s1+ s2+ s3,that is,a 3–bo dy Ising–type interaction be tween s1,s2an d s3as re -qu ired. The interaction strength J123is determ in ed byth e only f ce th at has not been m erged, and it is th ispa ram eter tha t will be tune d so tha t the sup erclique spe-TurnsTransportation in the 4D lattice:10cializes to a general n–body interac tion. Note that herethe dependence on r1and r2also cancels, since the largeblue face depends on each of them twice (and the sum ismo d 2, thus r1+ r1=0,andsimilarlyforr2).4–b ody interac tions can be generat ed similarly. Inthis case, the four logical particles re distributed closeto each other as shown in Fig. ??,andall overfacesare merge d to give rise to the Ising–t ype interac tionJ1234(−1)s1+s2+s3+s4. Th e procedure for the 5–body in-teraction analogous; in this case, one adds one more log-ical spin and merges the overall cover face (see ??).s1s2s3s4r1r2r3J1234FIG. 9: 4–body Ising–type interaction between spi s s1,s2,s3and s4with coupling strength J1234.SeethecaptionofFig.??for an explanation of the symbols.s1s2s3s4s5r1r2r3r4J12345FIG. 10: 5–body Ising–type interactionJ12345(−1)s1+s2+s3+s4+s5.SethecaptioofFg.??for an explanation of the symbols.Th e generalization to k–body Ising–t ype interac tions,for arbitrary k,isstraightforward.First,onepropagateseach of the “logical spins” s1,...,skin the lattice un-til they are as close to each other as possible, forminga “rectangular” shape without their red u–shapes touch-ing each other (as is the case for the 2–, 3–, 4– and 5–body interaction shown above). One can imagine this asadding more logi cal part icles on the right of the 5–b odyinteraction of Fig. ??,therebyenlargingthe“rectangle”in length, until ne has k logical particles, analogouslyto how particles have been “added” in th generationof the 5–b ody interac tion when com pare d with a 3– or4–b o y interac tion Then one merge s all cover faces ex-cep t for one. This renders the k–body Ising–t ype interac -tion J1...k(−1)s1+...+sk,wherethecouplingJ1...kis deter-mined by the only cover face that has not been me rged.Th e dependence on all auxiliary spins r1,r2,... will can-cel beca use, by const uction, the boundary of the mergedface depends on them twice. The coupling strengths J1...kwill be tuned so that the Hamilton function of the super-clique equals the Hamilton function of the specific finalmo del (which we will refer to as the “target” mo del),accord ing to Eq. (??).Thus, we have shown how to obtain k−body Ising–type interactions, for any k =1,... ,n.Nowwemustleteach spin participate in 2n−1interactions, as pointed outin (??). However, we have seen that a spin propagatesas in Fig. ??,andthispropagationendsinacertainface(called an “end”) that participates in a k–body interac -tion. There it is clear that spin s1can only participate intwo interactions, corresponding to the left and right ends.Mo re generally, the num ber of ends that an object (or en-coded particle) of dimension dein a lattice of dimensiond has are 2(d − de). He re the logical spin is never prop-agat ed alone, but always “carri es” the other three spinsof an adjacent face fixed (i.e. the shape of Fig. ??(a) ispropagated), hence we essentially have de=2. So,ford =3 theparticleisblockedtohaveonly2ends. Weneed to resort to a 4D lattice to obtain 2(d − de) > 2ends (see Fig. ?? for a replication in four dimensions ofone spin into five other ends). Then, this replication pro-ced ure can be multiply applied until the particle has 2n−1ends, that is, one end for each interaction. Note that inthis replication procedure no loops of spins fixed by thegau ge are form ed.s3 s2s1s4s5s6s7s9s8r6r3r2 r1r4 r5r7 r8FIG. 11: Replication of spins in a 4D lattice: s1is replicatedinto s3,s5,s6,s8,s9.Yellowfaceshavethesamemeaningasblue faces, that is, s2propagates into s3by the same meansas it propagat es into s7.Notethatnoloopsofredspinsareformed.We rem ark that all faces which are not m entioned inthis construction have to be deleted using the deletionrule. We also mention that we have tried several otherprocedur es in order to obtain this result in 3D, but noneof them could avoid the form ation of loops of edges fixedby the gauge.Th e specific layout of interactions in the superclique isthe following. The logical particles are distributed alongReplication4th dimension required to avoid loops! Construction of the supercliqueCompleteness of the 4D LGTZ211th e x di rection w ith one “idl e” spa ce am ong the m (seeFi g. ?? ). T h en each of th em is p rop agate d in th e y di -re ction . T he idea is to use this 3D spac e (i.e. the spac ewi th w =0 ) to propagate the particles, and to use the3D spac e defined by w =1 to create the interactionsre quire d for the sup erc lique.Fo r e x a m p le , in F ig . ?? we see 3 lo g ica l p a rticles a lo n gth e x di rection w hi ch are pr opa gated in the y di rection.Th en, at som e sites, they are also propagated to the spacede fine d by w =1 . In particular, in the first site, they areal l prop agat ed to w =1 , where the 1–body interaction ofea ch of the particl es w ill take place. In the follow ing site,s1an d s2are prop agat ed to w =1 , in order to gener-at e the 2–b o dy interac tion am on g them . A fter som e idlepr opa gation in the y di rection (pr ecisely, A (2 ) id le site s,as w ill b e explai ned b elow ), s1an d s3are prop agat edto th e sp ace w =1 , where they will generate a 2–bodyin teractio n am on g th em . T h is go es on for all 2–b o d y in -te racti on s, th en for all 3–b o d y inte racti on s, 4–b o d y, an dso on, up to the n –b o dy interac tion . For exam ple, the 4–bo dy interaction be tw een s1,s2,s3,s4an d then b etw eens1,s2,s3,s5are show n in F igs . ?? , ?? ...................s1 s1s1 s1s1s2s2 s2s2s2s3s3 s3s3s3xyzwsis1 ,s 2s1 ,s 3A (2 )FI G . 12: 3D sp ace w ith w =0 . Logical particles are dis-tr ib u te d alon g th e x di rection and the y are pr opa gated alongth e y di rection.No te th at th e id le sp ace on e h as to leave in th e y di rec-ti on am on g each p rop agati on to th e w =1 space dependson k .T hisisbecause,when thek pa rticles are pr opa -gat ed to the w =1 space, they are distributed in a line.Th ere, one has to rearrange them in the rectangular formex plained in F igs. ?? , ?? .Itfollowsfrom theconstructionth at th is rearran gem ent requ ires to leave sp aceA (k )= 2ceilingleftk/ 4ceilingright +2 ∼ k (2 6)be tw een interactions. A n overall layout of the propaga-ti on of p arti cles in th e w =0 space is shown in Fig. ?? .Fi n ally, n ote th at, as in d icated in Fi g. ?? ,o ne requiresa4 D lattice of size(x, y , z , w )= (2n,nsummationdisplayk=0A (k )parenleftbiggnkparenrightbigg, 1, 1) ∼ 2n(2 7)s1s1s2s3s4s4J1234FI G . 13: A 4–b o d y inter act ion in th e su p er cl iq u e. T h e fou rpa rticles s1, s2, s3an d s4ar e p rop agat ed into th e sp ac e w ithw =1 , shown here. Here they interact in a 4–body Ising–ty p e interaction as th e on e p resented in F ig. ?? wi th cou p lin gst ren gth Jij k l.B lack arrows indicate propagation ofthe spin(a s in F igs. ?? , ?? ;the corresponding merged faces are notde pi cted to avoid overloadi ng ).s1 s1s2s2s3 s3s4s5J1234J1235A (4 )FI G . 14: V iew of p art of th e w =1 space. First, parti-cl es s1,s2,s3,s4ar e p rop agat ed into th is sp ac e, an d th ey ar ebr oug ht close to each othe r (pr opa gations indi cated in bl ackar row s) in or d er to interac t in a 4–b o d y interac tion w ith in -te racti on str en gth J1234.A fterA (4 ) id le p arti cles in th e ydi rection, pa rticles s1,s2,s3,s5ar e p rop agat ed into th is sp ac ean d , agai n , th ey ar e b rou gh t clos e to eac h ot h er to interac tin th e 4–b o d y in teractio n w it h stren gth J1235.to gen erate a su p ercliqu e of n pa rticles. T he re is an ex-po nential overhead in the system size since one has toge nerat e an exp on ential num b er of interac tion s. W e re -ma rk th at effi ci en t co nstruct ions ca n b e found for sp eci ficta rget m o d els, e.g. in S ec. ?? we sh ow th a t th e co n stru c-ti on of th e 2D Isin g m o d el on ly requ ires a lin ear overh ead .We a lso p o in t o u t th a t th e c o n stru c tio n o f th e 4 – c liq u e(i .e. th e p art of th e su p ercliqu e w ith 4–b o d y inte racti on s)is th e essentia l in gred ie nt of th e m ean –fi eld th eory th atwe w ill co n stru ct in S ec. ?? .12.........................................................s1s1s1s1s1 s1s1s2s2 s2s2 s2s2snsnsnsn snsnxyzw2n1A (2 )`n2´A (3 )`n3´A ( n )`nn´11FI G . 1 5 : 3 D s p a ce w it h w =0 . Logical particles are dis-tr ib u te d a lo n g th e x di r e c t io n a nd t he y a r e pr o pa g a t e d a lo ngth e y di r e c t io n.E. M a in r e s u ltNo w w e c a n fi n a lly g a th e r th e r e s u lts w e h a v e p r o v e nin th e la s t s e c tio n s in o r d e r to s ta te o u r m a in r e s u lt . InSe c . ?? we h a v e s h o w n t h a t b y s e t t in g s o m e c o u p lin gst r e n g th s to in fi n ity o r z e r o (m e r g e o r d e le tio n r u le ), th epa r titio n func tio n o f a 4 D Z2LG T ca n b eco m e th e p a r ti-ti o n fu n c ti o n o f a s u p e r c liq u e . T h e n , in S e c . ?? ,w e haves h o wn th a t if o n e tu n e s th e c o u p lin g s tr e n g th s o f a s u -pe rc liq u e a p p ro p ria te ly, its H a m ilto n fu n c tio n spe c ia liz esto a to ta lly g e n e r a l Ha m ilto n fu n c ti o n b e tw e e n n 2–l e v e lpa r tic le s , a nd th us the c o r r e s p o ndi ng pa r titio n func tio nsare al s o e q u al . T h e re fore , w e h a v e s h o w n th at th e p art i-ti o n fu n c ti o n o f a n e n la r g e d 4 D Z2LG T w ith a p p r o p r ia tein h o m o g e n e o u s c o u p lin g s tr e n g th s c a n s p e c ia liz e to th epa r titio n func tio n o f a n y H a m ilto n func tio n o f n 2–l e v e lpa r tic le s . Mo r e s p e c ific a lly, w e ha v e s e e n tha t, fo r a n ycl a s s ica l s p in s y s tem , th er e is a s u b s y s tem o f th e co m -pl e te m o de l (the s up e r c liq ue ) tha t b e ha v e s lik e it (w he nth e a p p r o p r ia te c o u p lin g s tr e n g th s a r e s e t o n it).Let u s el a b o r a te o n th e cl a s s o f m o d el s th a t a r e em -br a c e d b y thi s r e s ul t. F ir s t o f a ll, the c o m pl e te ne s s r e s ul tho lds fo r m o de ls w ith a n ar b it r ar y in t e r ac t ion p at t e r n be -tw e e n t h e s e n 2–l e v e l p art ic le s , w h ic h in c lu d e s• Mo de ls in r e g ul a r la ttic e s in a r bi tr a r y di m e ns io n;e. g . a n 8 D Z2LG T ca n b e m a p p ed to a n en la r g ed4D Z2LG T w ith a p p r o p r ia te in h o m o g en eo u s co u -pl ing s ;• Mo de ls o n a r bi tr a r y g r a phs ; e .g . a Z2LG T d efi n edon a c om p lic at e d , irre gu lar grap h (n ot e th at u s u al lyAb e lia n d is c r e te L G T s a r e o n ly d e fi n e d o n h y p e r -cu b ic la ttices a n d h er e a m u c h m o r e g en er a l cl a s sis c o n s id e r e d );• Mo de ls w ith di ff er en t n u m b er o f p a r ticl es p a r tici -pa ting in the m a n y – b o dy in te r a c tio ns ; e .g . m o de lswi th 6 – b o d y in te r a c tio n s c a n b e m a p p e d to th e 4 DZ2LG T , w h ic h h a s 4 – b o d y in ter a ct io n s .• Mo de ls w ith di ff er en t ty p es o f m a n y – b o d y in ter a c-ti o n s ; e .g . m o d e ls c o n ta in in g m o r e g e n e r a l 4 – b o d yin te r a c tio n s (th e m o s t g e n e r a l c a s e b e in g to a s s ig nad iff er en t en er g y to ea c h o f th e 1 6 co n fi g u r a tio n s o fth e 4 p a r ti c le s ) c a n b e m a p p e d to th e 4 D Z2LG T ,wh ic h o n ly c o n ta in s Is in g – ty p e in te r a c tio n s .In th e s e c o n d p la c e , n o tic e th a t th e in fo r m a tio n o fwh e th e r th e m o d e l p o s s e s s e s a g lo b a l o r a lo c a l s y m m e -tr y is a ls o e n c o d e d in th e Ha m ilto n fu n c ti o n . S in c e a llHa m ilto n fu n c ti o n s a r e in c lu d e d in o u r r e s u lt, th is m e a n sth a t th e c o m p le te n e s s r e s u lt is v a lid fo r• Mo de ls w ith lo c a l s y m m e tr ie s , i.e . o the r A b e lia ndi s c r e te L GT s ;• Mo de ls w ith g lo ba l s y m m e tr ie s , i.e . A b e lia n di s -cr et e S S M s ; e. g . th e Is in g m o d el o r th e P o tts m o d elca n b e m a p p ed to a m o d el w ith lo ca l s y m m et r ies ,th e 4 D Z2LG T .We w ill d is c u s s h o w m o d e ls w it h d iff er en t ty p es o f s y m -me tr ie s c a n b e ma p p e d to e a c h o th e r in S e c . ?? .Fu r t h e r m o r e , t h e c o m p le t e n e s s r e s u lt a ls o in c lu d e sge n e ral H am ilton fu n c tion s b e tw e e n q − le v e l p a r tic le s ,si n c e o n e ju st n e e d s to e n c o d e e a c h q –l e v e l p art ic le inmq= ceilingleft lo g q ceilingright 2–l e v e l p art ic le s . T h e n , a tot al ly ge n e ral in -te r a c ti o n b e tw e e n nprimeq − le v e l p a r tic le s is g e n e r a te d w it h asu p e r c liq u e o f n 2–l e v e l p art ic le s , w ith n = nprimemq. Th u s ,ou r re s u lt al s o h ol d s for• Mo de ls w ho s e pa r tic le s ha v e a n a r bi tr a r y n um b e r o fle v e ls ; e .g . ZqLG T s , w h ic h h a v e q –l e v e l p art ic le s ,ca n b e m a p p ed to th e 4 D Z2LG T , w h ic h h a s 2 –le v e l p a r tic le s .In c o n c lu s io n , w e h a v e s h o wn th a t th e 4 D Z2LG Tis c o m p le te fo r a ll A b e lia n d is c r e te c la s s ic a l s p in m o d e ls ,in c lu d in g al l Ab e lia n d is c r e te L G T s a n d Ab e lia n d is c r e teSSMs . In s y m b o ls , the m a in r e s ul t o f thi s w o r k c a n b esu m m a r iz e d a sZAb e lia n d is c r e t e c la s s ic a l(J )= Z4D Z2LG T(J, Jprime)( 28)wh e r e J is th e s e t o f c o u p lin g s in th e ta r g e t m o d e l, a n dJprimeis th e s e t o f c o u p lin g s in th e a d d it io n a l p a r tic le s o f th eco m p let e m o d el .F. E ffi ci e n cy r e s u lt sWe h a v e e m p h a s iz e d t h a t a ll c o m p le t e n e s s r e s u lt s r e -qu ir e a la r ger ,i nhom ogeneous com plete m odel w hen com -pa r e d to the ta r g e t m o de l. H e r e w e in v e s tig a te ho w thenu m b e r o f p a r t ic le s in t h e c o m p le t e m o d e l nprimes c a le s wi thth e n u m b e r o f p a r ti c le s o f th e ta r g e t m o d e l n .T hat is, west u d y h o w th e sy st e m si z e o f th e c o m p le te m o d e l in c r e a sewh e n th e s y s te m s iz e o f th e ta r g e t m o d e l in c r e a s e s .Fi r s t, w e fo c u s o n th e n u m b e r o f p a r tic le s p a r tic ip a t-in g in in te r a c tio n s in th e ta r g e t H a m ilt o n fu n c tio n . Ifth e ta r g e t Ha m ilto n fu n c ti o n c o n ta in s a t m o s t k − bo d yin te r a c tio n s (a n d q =2 ), in general one needs to generateas uperclique of k pa r tic le s in the 4 D Z2LG T fo r ea c h o fth e s e in te r a c ti o n s (b e c a u s e th e m e th o d o f S e c . ?? co u ldSuperclique: complicated interaction pattern with simple interactionsLayout of the superclique: Construction of the supercliqueCompleteness of the 4D LGTZ2Hamiltonian of supercliqueHamiltonian of any classical spin model1. General Hamiltonian on n 2-level systems: different E(s)for each s2. Show that one can invert the system of equationsdifferent energies2nnsummationdisplayk=0parenleftbiggnkparenrightbigg=2ncouplings3. All rows are linearly independent, thus the determinant is non zero1(−1)0...(−1)0+0+...+01(−1)0...(−1)0+0+...+1...1(−1)1...(−1)1+1+...+1bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipuprightCJJ1...J12...n=E(s=(0,0,...,0))E(s=(0,0,...,1))...E(s=(1,1,...,1))ceilingleftlog2qceilingright2-level sys.4. q-level models: encode each q-level system into q.e.d.Completeness of the 4D LGTZ2 Note: efficient constructions for specific target models17s1 ,1s1 ,2s1 ,3s1 ,4J1 ,1; 1 ,2J1 ,2; 1 ,3J1 ,3; 1 ,4FI G . 18: G en er ation of a 1D array of Isin g–ty p e inter act ion s:si, jin teracts w it h sp in si, j +1vi a a 2–b o d y Isin g–typ e interac-ti on w ith cou p lin g str en gth Ji, j ;i, j +1.A rrowsindicate propa-gat ion of th e sp in ac cor d in g to F ig. ?? ,a nd the cubes markedin b lu e in d ic ate a 2–b o d y in teractio n accord in g to F ig . ?? (b ).to constr uct th e 1D array of F ig. ?? ,w e make use ofth e fourth dim ension in order to link th em as show n inFi g. ?? .Theyellowcubeshavethesamemeaningasth e blue cub es in F ig. ?? ,that is, they correspond to 2–bo dy Ising–type interactions. In this m anner, spin s1 ,1in teracts w it h s2 ,1wi th strength J1 ,1; 2 ,1,a nd so on. Thisco m plet es the co nstruct ion of the 2D Ising m o del .s1 ,1s1 ,2s1 ,3s1 ,4s2 ,1s2 ,2s2 ,3s2 ,4s3 ,1s3 ,2s3 ,3s3 ,4xyzwJ2 ,4; 3 ,4J1 ,4; 2 ,4J2 ,1; 3 ,1J1 ,1; 2 ,1FI G . 19: C on stru ct ion of th e 2D Isin g m o d el . E ach 1D arrayin teracts w it h th e n ex t on e v ia th e fou rth d im en sio n , th at is ,si, jin teracts w it h si+1 ,jvi a a yellow face, w ith interactionst ren gth Ji, j ;i+1 ,j.E very layer for diff er en t w co rres p on d s toth e 1D array of inte racti on s of F ig. ?? (b lu e cu b es are n otsh ow n to avoid overload in g). A s in F ig. ?? ,yellow cubesha ve the sam e m eani ng as bl ue cub es, i.e. 2–b o dy Ising –ty p ein teractio n s.As can b e observed in F ig. ?? ,the construction of a2D Ising m o del of size n × m re quire s a 4D lat tice of size(x, y , z , w )= (2n, 4, 1,m ), i.e. th e scaling is linear in th esy st em si ze.VI . IM P LIC AT IO N S O F T H E M AI N R E SU LTIn this section w e wi ll draw tw o im plications of thema in result. Fi rst, in Sec. ?? we w ill con clu d e th at com -put ing the pa rtition func tion of 4D Z2LG T is # P hard;th at is, com puta ti onally diffi cu lt. T hen , in Sec. ?? wewi ll argue that our result provides a new m etho d to com -put e the m ean– fie ld– the ory of a Z2LG T , w hich w orks forfini te di m ens ion.A. C om putational com plexity of 3D and 4D Z2LG TOu r m ain result im plies, in particular, that the parti-ti on functi on of th e 2D Ising m o del w ith m agneti c fieldsca n b e ex pres sed as a sp eci fic instance of the partitionfu nction of the 4D Z2LG T . T he co m putation of the par-ti ti on functi on of th e 2D Ising m o del w ith m agneti c fieldsis a # P –com ple te proble m [? ]–roughlyspeaking,thisme ans that it is comp utationally diffi cu lt [? ]. T hus, w eco ncl ude that co m puting the partition funct ion of the 4DZ2LG T in the rea l param et er reg im e is # P –hard, i.e. atle ast as hard as the other proble m . T hat is , w e havepr oven tha t one can m ap all m o de ls to a m o de l w hi ch isha rd to solve.Th e construction presented ab ove also gives insightin to the com ple xit y of the 3D Z2LG T . M ore preci sel y,in Sec. ?? we saw th at a 3D Z2LG T ca n prep are m o d-el s w ith k –b o dy Ising–t yp e interac tion s, for an y k =1,... ,n ,as long as as every particle participates in atmo st tw o interactions (this w as the limi tation of the tw oen ds of F ig. ?? th at m ade us m ove to th e 4D latti ce).Th is im plies, in particular, that the 3D Z2LG T m ustbe as hard as any vertex m odel w ith q =2 and k− bo dyIs ing–typ e interactions.On the other hand, using a m etho d intro duced in [?], one can show that approxim atin g the partit io n func-ti on of th e 3D Z2LG T in a cer tain co m plex param et erre gi m e w ith p ol ynom ial ac curac y is as hard as sim ulat ingarb itrary quan tum com putat ion s, i.e. B Q P–c om plete [?].B. Me an–F ield T heoryTh e m ean–field theory of a m o del is an approxim ationto th at m o del w here th e inte racti on of a variable w ith itsne ighb ors is repl aced by an interaction of thi s variabl ewi th a m ean field. In this m anner, the theory is reducedto a 1–b o dy problem , w hich is useful to gain insight intoat heory that is diffi cu lt to solve ex act ly. T hus, ther eare as m an y w ays to con stru ct a m ean –fi eld theory of amo del as w ays to average over the influence of neighb or-in g varia ble s over a giv en varia ble .In SSM s, m ean–field theories of SSM s are generallyea sy to co nstruct . For ex am ple, in the Ising m o del , theExample: 2D Ising model: linear overhead ✓ Completeness of the 4D LGTZ2Note: 2D Ising can magnetize, but LGT cannot We have proven that:✓ any dimensions✓ q-level systems, any q✓ any many-body int.realAbelian discreteZ4DZ2LGT(J,Jprime)= Zany classical spin model(J)constructiveglobal & local symmetriesCompleteness of the 4D LGTZ2Target hamiltonian with M terms and k-body int: scaling poly(M,2k)largerResult holds approx for continuous models: letq →∞Applications of completenesse.g. 2D Ising with fields poly larger#P-hard #P-hard4D LGTZ2Mapping models with poly overhead: infer comput. complexityMany different universality classes are mapped to a single modelThey should be reproducible in the phase diagram of the complete modelthis includes ‘unexplored’ modelsSymmetries of the states symmetries of the partition functionZG(J)=〈α(J)|S|ϕG〉〈α(Jprime)|=ZG(Jprime)Computational complexityM. Van den Nest, W. Dür, R. Raussendorf, H. J. Briegel, Phys. Rev. A 80, 052334 (2009)Mapping partition functions to quantum circuitsIBoltzmann weight of each int. Quantum gate, e.g.Contraction of quantum gates = CircuitproductdisplayawaCProduct of interactionsOutput & Input of circuitR =(sR1,...,sRn)L =(sL1,...,sLn) |L〉=|sL1〉...|sLn〉|R〉=|sR1〉...|sRn〉Left & Right bound. cond.other geometries✓ PBCZ=TrC✓ Classical spin model Quantum circuitwa=e−βha(s1,s2)Wa(12)(12)=summationdisplaye−βha(s1,s2)|s1,s2〉〈s1,s2|ZL,R=〈L|C|R〉5... ... ... ...sL1sL2sLnsR1sR2snijklwa( si,sj,sk,sl)〈 sL1|〈 sL2|〈 sLn|Wa( ij )( kl )ijkl|sR1〉|sR2〉|sRn〉ti m eFI G . 1 : ( L ef t ) In a v er t ex m o d el , p a r t icl es ( b la c k d o t s ) s itat t h e e d ge s an d in t e r ac t ion s ( p al e r e d d ot s ) t ak e p lac e in t h eve r t ic e s . ( R ig h t ) T h is m o d e l is m a p p e d t o a q u a n t u m c ir c u it ,wh e r e e a c h in t e r a c t io n b e c o m e s a tw o – q u b it g a t e .Th is c o n c lu d e s th e m a p p in g b e tw e e n m a trix e le m e n ts o fqu a n tu m c irc u its a n d p a rtitio n fu n c tio n s o f c la ssic a l sp inmo d e ls.In th e fo llo wi n g w e m a k e so m e re m a rk s re g a rd in g th isma p p in g .(i ) No te th a t th e q u a n tu m g a te s a re sp e c ifi e d b y th epa ra m e te rs o f the c la ssic a l m o de l, na m e ly b y theBo ltz m a n n w e ig h ts o f lo c a l in te ra c tio n s. It fo llo w sth a t o n ly in c e rta in p a ra m e te r re g im e s, th e re su lti n gci rcu it C is a se q u e n c e o f un ita r y qu a n tu m g a te s.(i i) W e str e ss th a t th is m a p p in g c a n b e e a sily e x te n d e dto o p e n b o u n d a ry c o n d iti o n s, i.e . sy ste m s w h e re le ftan d ri gh t sp in s are ‘fre e ’ an d th u s fu lly su m m e dou t in th e p art ition fu n c tion . T h is c an b e e as -ily a ch ie v e d b y re p la c in g th e le ft a n d rig h t sta te s|L 〉 an d |R 〉 by th e s ta te |+ 〉⊗ n,w here |+ 〉 =q− 1 / 2summationtextqi=0|i〉 is a su p e rp o sit io n o v e r a ll q si n g lesp in sta te s. Th is y ie ld s th e id e n tityZOB Cvm= qn〈+ |⊗ nC| + 〉⊗ n. (1 2 )Fu r t h e r , p e r io d ic b o u n d a r y c o n d it io n s c a n a ls o b eta k e n in to a c c o u n t b y su m m in g o v e r th e d ia g o n a lma trix e le me n ts, w h ich re su lts inZPB Cvm=T r(C ) . (1 3 )(i ii) S im ila rly, o n e c a n c o n sid e r o th e r g e o m e tr ie s su ch a s,e. g ., v er tex m o d el s o n a 2 D tilted tria n g u la r la ttice[9 ], w h e re 6 – b o d y in te ra c tio n s ta k e p la c e a t v e rtic e san d th e B ol tz m an n w e igh ts c an b e arran ge d in toq3× q3ma tric e s, c o rre sp o n d in g to a q u a n tu m c irc u itwi th 3 -b o d y q u a n tu m g a te s. O n e su ch m o d e l is th e32 v e rt e x m o d e l [9 ]. A ls o 3 D m o d e ls , su ch a s m o d -el s o n a tilted 3 D sq u a re la ttice, ca n b e co n sid er edof th is ty p e an d c an th u s b e m ap p e d to q u an tu mci rcu its. In th is ca se, o n e d ea ls w ith 3 -p a rticl e g a tesac tin g on a 2D arra y of q u an tu m p art ic le s. Ge mmaas k M aart e n w h y n ot 4- p art ic le gat e s?B. E d g e m o d e lsGe mma put he re o n in the ba ck g ro und w ha t the p o ttsmo d e l is: Th e P o tts m o d e l d e fi n e d o n a g ra p h G is m o d e lsu ch th a t q –l e v e l p art ic le sit at th e v e rt ic e s of a grap h ,sa=0 , 1 ,... ,q − 1, an d in te rac t al on g th e e d ge s ac c ord in gtohe( s )= − Jeδ (sa− sb) , (1 4 )wh e re th e e d g e e is a d ja c e n t to v e rtic e s a, b ,a nd δ (sa−sb)= 1 if si− sj=0 and it is zero otherwise [10 ]. T h eHa m ilto n ia n is a su m o f th e se 2 – lo c a l te rm s o v e r a ll e d g e sH ( s )=summationdisplaye∈ Ehe( s ) . (1 5 )In th e fo llo wi n g w e wi ll p re se n t a sim ila r m a p p in g fo red g e m o d el s. In co n tra st to v er tex m o d el s, in ed g e m o d -el s th e cl a ssica l sp in s sit a t th e v er tices o f th e g ra p h ; w ewi ll a lso c o n sid e r c la ssic a l sp in s wi th q po ssib le sta te ssi∈ { 0 ,... ,q − 1 } .I n this case interactions take placeal on g th e e d ge s. C on sid e r, th u s, a q -s ta te e d g e m o d e l o nan n × m sq u a re la ttic e wi th a n e d g e – d e p e n d e n t e n e rg yfu n c tio n he(si,sj)— se e F ig . 2 .L etwe(si,sj): = e− β he(si,sj)(1 6 )de no te the c o rre sp o ndi ng B o ltz m a nn w e ig h t. T he n thepa rtitio n func tio n is g iv e n b y Z =summationtextsproducttexte = ijwe(si,sj).As p re v io u sly, th e n sp in s in th e le ftm o st a n d rig h tm o stco lu m n o f th e la ttice a re fi x ed in th e co n fi g u ra tio n s sL:=(sL1,... ,sLn)a nd sR:= (sR1,... ,sRn), re sp e c ti v e ly. W ithea ch h o rizo n ta l ed g e e ,w e now associate a q × q ma trixWhe:=summationdisplaysi,sjwe(si,sj)|sj〉〈 si| . (1 7 )Fu r t h e r m o r e , w it h e a c h v e r t ic a l e d g e e ,w e associate theq2× q2diag on al ma trixWve:=summationdisplaysi,sjwe(si,sj)|si,sj〉〈 si,sj| . (1 8 )Th e m a tric e s Whean d Wvewi ll b e re g a rd e d a s (p o ssi-bl y no n- uni ta ry ) q ua n tum g a te s a c ting o n a sing le , re -sp e c tiv e ly a p a ir, o f q -l e v e l q u a n tu m sy ste m s. W e n o wco n sid er a o n e- d im en sio n a l q u a n tu m sy stem co m p o sedof nq -l e v e l sy ste m s a n d th e q u a n tu m c irc u it C ac tin gon th is sy ste m as d e p ic te d in F ig. 2 .T he circuit C co n -sists o f a lte rn a tin g la y e rs o f o p e ra tio n s a sso c ia te d wi thth e h o riz o n ta l a n d v e rti c a l e d g e s o f th e 2 D la tti c e . E a chrou n d of C as so c iat e d w ith a la y e r of h ori z on tal e d ge sco n sists o f a p ro d u ct o f o n e- lo ca l o p er a to rs Whe,w hereasev er y ro u n d a sso ci a ted w ith a la y er o f v er tica l ed g es isap roduct of two-local operations Wve.W e define com-put a tio na l ba sis sta te s |L 〉 an d |R 〉 as so c iat e d to th e le ftan d ri gh t b ou n d ary c on d ition s, re sp e c tiv e ly, an al ogou slyto E q . (10 ). W ith th e se d e fi n iti o n s, o n e h a s th e fo llo w in gco rres p o n d en ce:ZL, Rem= 〈L |C |R 〉 . (1 9 )Mapping partition functions to quantum circuitsIParticles at the edges Mapping for vertex modelsZL,Rvm= 〈L|C|R〉Interaction at vertex Two-qudit gateaWa(ij)(kl)=summationdisplaye−βha(sisjsksl)|si,sj〉〈sksl|wa(s)=summationdisplaye−βha(sisjsksl)Particles at the vertices Mapping for edge models6... ... ......sL1sL2sL3sR1sR2sR3ijwhijwvjki jk kWhijWvjk〈sL1|〈sL2|〈sLn||sR1〉|sR2〉|sRn〉ti m eFI G . 2 : (L ef t) In a n ed g e m o d el , p a rticl es (b la ck d o ts) sitat th e v e rtic e s an d in te rac tion s (p al e re d an d b lu e e llip se s)ta k e p la c e a lo n g th e e d g e s. (R ig h t) T h is m o d e l is m a p p e d toaq uantum circuit, where interactions along the time direc-ti o n b e c o m e sin g le – q u b it g a te s, a n d th o se p e rp e n d ic u la r to itbe co m e tw o – q u b it g a tes.Th is e q u a tio n is re a d ily v e rifi e d b y e m p lo y in g th e d e fi n i-ti o n s o f th e g a te s Whean d Wve.In th e fo llo wi n g w e g iv e so m e sim p le m o d ifi c a tio n s o fth e th is m a p p in g th a t w ill b e u se fu l b e lo w . F irst, c o n -si d e r th a t a t si te i in th e la ttic e a lo c a l m a g n e tic fi e ldis p re se n t. T h is is re p re se n te d b y a n a d d it io n a l te rmhi(si)i n the energy function and corresponding Boltz-ma n n w e ig h twi(si)= e− β hi( si), (2 0 )wi th si=0 ,... ,q − 1. T h e n w e in tro d u c e th e d iagon alq × q ma trixWi:=summationdisplaysiwi(si)|si〉〈 si| . (2 1 )No w a m a p p in g to a q u a n tu m c irc u it C ca n b e es ta b lish edin a sim ila r fa sh io n a s a b o v e , w it h th e d is tin c tio n th a tea ch la y er a sso ci a ted w ith a slice o f v er tica l ed g es n o wco n sists o f a p ro d u ct o f th e a sso ci a ted tw o – q u b it g a tesWvean d th e as so c iat e d sin gl e –q u b it gat e s Wi.N ote that,as al l su ch gat e s are d iagon al op e rat ion s, th e re is n o p rob -le m re g a rd in g o p e ra to r o rd e rin g . W it h th is ch o ic e o f C ,it c a n re a d ily b e v e rifi e d th a t th e a sso c ia te d p a rtit io nfu n c tio n c a n b e w ritte n a s (19 ).Se c o nd, thi s m a ppi ng c a n a lso b e e x te nde d to o p e n a ndpe rio d ic bo u n d a ry co n d itio n s, in a co m p letely a n a lo g o u sfa sh io n a s fo r v e rte x m o d e ls (se e S e c . IV A ).Fi n a lly, w e re ma rk th a t th e a b o v e ma p p in g s fro m p a r-ti ti o n fu n c ti o n s to q u a n tu m c irc u its m a y e a sily b e g e n -er a lized to g ra p h s o th er th a n th e 2 D la ttice, sim ila rly a sfo r v e rte x m o d e ls. In p a rtic u la r, b e lo w w e w ill c o n sid e rth e fo llo w in g c la ss o f su b g ra p h s o f th e 2 D sq u a re la tti c e :ag raph G is sa id to b e a pl an ar c ir c u it g raph if it c a n b eob tai n e d from an n × m re c tan gu lar gri d (for som e n an dm )b y de le tin g as ubset of ver tica l ed g es a n d co n t r a c t in gas ubset of hor iz on tal ed g es . If G is su ch a su b g ra p h o fan n × m re c tan gu lar gri d , w e c al l n th e v e rti c a l d im e n -si o n o f G ;n ote that this quantity is uniquely defined forev er y p la n a r ci rcu it g ra p h . S im ila r a s fo r th e 2 D sq u a rela ttic e , o n e c a n a sso c ia te a q u a n tu m c ir c u it C wi th e v e rypl a na r c irc ui t g ra ph; m o re pr e c ise ly, o ne a sso c ia te s e a chho riz o n ta l a nd v e rtic a l e dg e e wi th th e g a te s Whean dWve,r espectively, and each vertex i wi th th e g a te Wi;s eeFi g . 3 fo r a n e x a m p le . If th e v e rtic a l d im e n sio n o f th egrap h is n th e n C ac ts on nq -l e v e l sy ste m s. A n id e n titysi m ila r to (19 ), o r to (12 )i n the case of open boundaryco n d itio n s, is ea sily seen to h o ld fo r p la n a r ci rcu it g ra p h sas w e ll (b ot h w ith or w ith ou t an e x te rn al fi e ld ).... ... ... ...sL1sL2sL3sR1sR2sR3wi wijwjkWiWheWve〈sL1|〈sL2|〈sLn||sR1〉|sR2〉|sRn〉ti m eFI G . 3 : (L ef t) E d g e m o d el d efi n ed o n a p la n a r ci rcu it g ra p h .Th e la tte r is o b ta in e d fr o m a n re c ta n g u la r g rid b y d e le tin gso m e v e rtic a l e d g e s a n d c o n tra c tin g so m e h o riz o n ta l e d g e s.(R ig h t) M a p p in g o f a c la ssic a l sp in m o d e l d e fi n e d o n a p la n a rci rcu it g ra p h o n to a q u a n tu m ci rcu it. H o rizo n ta l a n d v er tic aled g e in ter a ct io n s a re m a p p ed to sin g le– q u b it n o n – d ia g o n a lan d tw o–q u b it d iagon al gat e s, re sp e c tiv e ly, an d lo c al in te r-ac tion s (e .g. m agn e tic fi e ld s) ar e m ap p e d on to sin gl e –q u b it(d ia g o n a l) g a te s.We n o w s p e c ia liz e t h e a b o v e d is c u s s io n t o t h e c a s e o fth e 2 D Isin g m o d e l. W e w ill c o n sid e r th e Isin g m o d e lon (su b lat tic e s of ) th e 2D lat tic e in th e p re se n c e of anex ter n a l fi el d : T h e in ter a ct io n b et w een tw o sp in s sian dsjlo c a te d a t th e e n d p o in ts o f a n e d g e e = ij is g iv e nby he(si,sj)= − Jeδ (si+ sj), a n d th e c o n tr ib u ti o n o fth e m a g n e ti c fi e ld a t site i is hi(si)= − hisi.H ere thesp in st a te s sima y ta k e va lu e s 0 a n d 1 , th e su m is p e r-fo rm e d m o d u lo 2 , a n d δ (·)i s 1 if the argum ent is 0 andit is 0 o th e rw is e . F u rth e r, Jean d hiare c on stan ts w h ichre p re se n t th e stre n gt h s of th e p ai rw ise in te rac tion an dma g n e tic fi e ld , re sp e c tiv e ly. W ith th e d e fi n itio n s (17 ),(18 )a nd (21 ), w e h a v eWhe=bracketleftbiggeβ Je11 eβ Jebracketrightbigg,Wve=d iag(eβ Je, 1 , 1 ,eβ Je)Wi=bracketleftbiggeβ hi001bracketrightbigg.(2 2 )C. L a ttic e g a u g e th e o r ie sWe p r o c e e d t o p r e s e n t a s im ila r m a p p in g fo r a n e n t ir e lydi ff er en t cl a ss o f m o d el s, n a m el y Z2LG T s. W e ref er th ere ad e r to [3 ]f or an introduction to these m odels. For thepr e se n t pur p o se s w e w ill b e in te re ste d in the fo llo w ingfe a tu re s o f Z2LG T s. T h ey a re m o d el s w h o se cl a ssica lsp in s c a n ta k e tw o va lu e s se∈ { 0 , 1 } an d sit at th e e d ge sof a sq u are lat tic e . T h e re is an in te rac tion al on g e v e ryfa c e ; in p a rtic u la r, fo r sp in s si,sj,sk,slat th e b ou n d aryof fac e f ,t he interaction takes the formhf(s )= − Jfδ (si+ sj+ sk+ sl) , (2 3 )ZL,Rem= 〈L|C|R〉Mapping partition functions to quantum circuitsIInt. at edge in time dir.Single qudit gateInt. at edge in space dir. Two qudit diagonal gatewij= e−βh(si,sj)w(i)(j)=summationdisplaye−βh(si,sj)|si〉〈sj|w(jk)(jk)=summationdisplaye−βh(sj,sk)|sjsk〉〈sjsk|wjk=e−βh(sj,sk)8sL1sL2sR1sR2〈sL1|〈sL2||sR1〉|sR2〉timewa,bWtfwa, b,c,dWsfFI G . 4: (L ef t) In a 3D L G T , p articl es (b lack an d gray d ots) sit at th e ed ge s an d interac tion s (p al e red an d b lu e ellip ses) takepl ace on the faces. G ray do ts indi cate pa rticles w ho se state ha s b een fix ed by the gaug e. (R ight) T hi s m o de l is m app ed to aqu antu m circu it, w h ere interaction s alon g th e tim e d irection b ecom e tw o–q u b it gat es, an d th os e p erp en d icu lar to it b ecom efo u r–q u b it gates.A. S ix –vertex m o d elWe w ill n o w u se th e m a p p in g s b e tw e e n v e r te x m o d e lsan d qu an tu m circ u its d escri b ed in S ec. IV A to sh ow th atap p ro xim at in g th e p art ition fu n ction Z of som e vert exmo d els is in certain (comp lex) p arame ter regime s BQ P –co m p let e [1].We c o n sid e r th e q =2 ‘six-vertex model’ (or: ‘ice–typemo d el’) an d th e ‘eight-vertex mo d el’ [8]o n a (tilted) 2Dsqu are lattice. In th e six-vertex m o d el, on ly six of th e16 p os sib le sp in con fi gu rat ion s gi ve ri se to a n on -zeroBo ltzm an n w eight. M ore p recisely, Wais a 4 × 4m atrixof th e formWa=w00 ,0000 00 w01 ,01w01 ,1000 w10 ,01w10 ,10000 0w11 ,11. (3 7)Th e eight-vertex m o d el [8]is obtained by additionally al-lo w in g th e entrie s w00 ,11,w11 ,00to b e n on –zero. W e con -sid er a p aram eter regim e of th e classical m o d el wh ere allma trices Waare u n itary , th at is, th e circ u it C is a u n it aryci rcu it of tw o–qu b it qu antu m gates . N otice th at th is gen -er ally co rres p on d s to (n on –p hysica l) co m p lex p aram et er sfo r eith er cou p lin g stren gth s or th e inverse tem p eratu reβ .F inally,weassumethatwehavestaggeredleftanrightbo undary conditions of the form L = R =( 0101... ).In th is case, w e sh ow th at ap p roxim atin g th e p artitionfu n ction of six–vertex m o d els on a n × po ly (n )lattice isBQ P –c om p lete. L et u s fi x som e n ot at ion b efore start in gth e p ro of. He n ceforth w e w ill d en ote en co d ed sta te s an dop erat ors by b ol d fac e sym b ol s, an d w e w ill al so om it th ete n sor p ro d u ct sym b ol ⊗ to keep n ota ti on sim p le. No wwe ca n p ro ceed to p rove th e cla im o f th is sectio n . To d oso, w e wi ll sh ow th at any qu antu m com p u tation can b ere d u ced to th e eval u at ion of th e p art ition fu n ction of asix–vertex m o d el on a tilted 2D squ are lattice wi th stag-ge re d b ou n d ary con d ition s. W e w ill p ro ve th is stat em entin th ree step s:(i ) W e sh ow th at qu antu m gate s of th e form (37 )a reco m p u tation al u n iver sal for en coded qu antu m com -put ation;(i i) T h e en co d ed in iti al sta te |0〉⊗ Nca n b e p rep aredfr om th e state corresp on d in g to staggered b ou n d aryco n d ition s |0101 ... 〉;(i ii) For any given p oly–size qu antu m circu it C ,o ne caneffi ci en tly ap p roxim ate th e m atrix el em en t 〈0 |C |0〉by u sin g en co d ed q u a nt u m sta tes a n d g a tes o f th efo rm (37 ).To sh o w (i), w e con sid er th e exch an ge (o r He isenb erg)in teractio n ,Hex= σx⊗ σx+ σy⊗ σy+ σz⊗ σz(3 8)wi th corresp on d in gtw o–qu b itt gatesU = eit Hex. (3 9)Th ese are of th e form (37 )w ith the non–zero entriesw00 ,00= w11 ,11= ei2tw01 ,01= w10 ,10=c os(2t)w01 ,10= w10 ,01= i si n(2t) .(4 0)Th e H eisenb erg interaction is (en co d ed ) u n iversal forqu antu m com p u tation [12 , 13 ]. In oth er w ord s, by u s-in g gates of th e form (39 ), on e can p rep are any qu antu mst ate |ψ 〉 = C |0〉 in an en co d ed form . H ere, w e u se afo u r-qu b it en co d in g |0〉 wi th|0〉 =12(|01 〉− |10 〉)⊗ 2. (4 1)An d th e |1〉 ?We n o w tu r n to (ii )a nd consider an operation V of th efo rm (37 )w ith the non–zero entriesw00 ,00= w11 ,11=1w01 ,01= w10 ,10= w01 ,10= − w10 ,01=1 /√2 .(4 2)It is straightforw ard to ch eck th at V |01 〉 =( |01 〉−|10 〉)/√2, an d h en ce|0〉 = V⊗ 2|0101 〉 . (4 3)Re gardi ng (iii ), w e observe that m atrix elem ents ofth e form 〈0 |C |0〉 ca n b e effi ci en tly ap p roxim ated by aMapping partition functions to quantum circuitsI Mapping for lattice gauge theoriesParticles at the edgesInt. at face in time dir. Single qudit gateInt. at face in space dir. Four qudit diagonal gatewij= e−βh(si,sj)w(i)(j)=summationdisplaye−βh(si,sj)|si〉〈sj|w(jk)(jk)=summationdisplaye−βh(sj,sk)|sjsk〉〈sjsk|wjk=e−βh(sj,sk)ZL,RLGT= 〈L|C |R〉& Fixing the temporal gaugeBQP-completeness resultsII Main idea:ModelGates corresp. to that modelShow that they form a universal gate setApproximating that partition function is as hard as simulating arbitrary quantum computationZ = 〈L|C|R〉BQP-completeness resultsII Main idea:ModelGates corresp. to that modelShow that they form a universal gate setApproximating that partition function is as hard as simulating arbitrary quantum computationZ = 〈L|C|R〉BQP-completeness resultsII Main idea:ModelGates corresp. to that modelShow that they form a universal gate setApproximating that partition function is as hard as simulating arbitrary quantum computationProvide a quantum algorithmProve BQP-completeness of computing ZZ = 〈L|C|R〉 Six vertex model(Encoded) universal interactionU = eitHexwithHex=σx⊗σx+σy⊗σy+σz⊗σzEncoding|0〉 =12(|01〉−|10〉)⊗2Preparation of|0〉|0〉 ...|0〉from |R〉 = |0〉|1〉|0〉|1〉... possible The exchange int. is achieved with the six-vertex model-type gate:BQP-completeness resultsIIW(ij)(jk)=ei2tcos(2t) isin(2t)isin(2t) cos(2t)ei2t Six vertex model(Encoded) universal interactionU = eitHexwithHex=σx⊗σx+σy⊗σy+σz⊗σzEncoding|0〉 =12(|01〉−|10〉)⊗2Preparation of|0〉|0〉 ...|0〉from |R〉 = |0〉|1〉|0〉|1〉... possible The exchange int. is achieved with the six-vertex model-type gate:Approximating the partition function of the six vertex model on a certain complex parameter regime is BQP-completeBQP-completeness resultsIIW(ij)(jk)=ei2tcos(2t) isin(2t)isin(2t) cos(2t)ei2t Potts modelEach Potts gate is characterized by the pair (eβJii,eβJinegationslash=j)Trivial preparation of |0〉...|0〉 |R〉 = |0〉|1〉...|0〉|1〉fromSingle qubit identityPhase gateTwo qubit identityControlled phase gateBQP-completeness resultsII|0〉 =|0〉|1〉|1〉 =|1〉|2〉Encoding:Construct an (encoded) universal gate set:11is a bit more involved and we refer the reader toAp pendix B for the details.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij〉〈ij| , (56)is trivially obtained by applying a two qutrit–gatebetween the two physical qutrits of the first logicalqu bit with (µ, ν)= (1, 1), an d doing the sam e forthe other logical qubit (see Fig. 6a).• Finally, the phase gate between logical qubitsCZ =1summationdisplayi,j=0(−1)ij|ij〉〈ij| (57)is achieved by applying a two qutrit–gate be-tw een the lower–qutrit of the first logical qubit andthe upper qutrit of the second logical qudit with(µ, ν)= (−1, 1). We also need to ap ply the sam egat e between the lower qudit of the secon d logi calqu bit and an auxiliary particle in the state |2〉 (seeFig. 6b).|2〉(1, 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a) (b)time timeFI G. 5: (a) Logical single–qubit identity I1.(b)Logicalpha se gate P .Eachgateisdeterminedbythepairofnumbers(µ, ν)(Eq.(52 )) which are indicated next to it, and its coloris just a guide to the eye to identify equal gates. Auxilia rysp ins (i.e. fixed sp ins) are colored in gray, and physical sp insin black. Note that in both figures tim e runs from right toleft.Ge mma uni fy the two fig ures in one ?In summary, we have proven that by letting the qutritsinteract according to a Potts-type nearest-neighbor inter-action , we can perform universal quantum com putationat the logi cal level. From Eq . (3)itfollowsthatthecom-put ation of the pa rtition func tion of the Potts mode l with3-level systems is a BQ P–com plete prob lem.We now give a few rem arks regarding this construc-tion. First, we observe that the single–qubit identity I1requires to set ν =0,i.e.Jinegationslash=j= −∞ .Thiscaveatcanbe circumvented by applying a modified gate, Iprime1with(µ, ν)= (1, 1) an d is thus within the usual param eterran ge of the Potts model. It can be read ily verified that|2〉(1, 1)(1, 1)(−1, 1)(−1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉 CZ |ψ1〉|ψ2〉(a)(b)time timeFI G. 6: (a) Logical two–qubit identity I2.(b)Logicalcon-trolled phase gate CZ .SeethecaptionofFig.5 for theme aning of the pair of numbers and the color associated toeach gate.the use of Iprimeinstead of I results in a prefactor in the ob -tained partition function, namely Zprime=3IZ ,whereI isthe number of times Iprimeha s been appl ied. Thus, the com-plexity of comput ing Z is the same as that of computingZ .even though I ma y scale with the system size?Se cond, no te tha t the implementation of the gates H ,P an d CZ require com plex values of the energy Jii,moreprecisely:βJii= −ipi/2, 0,−∞ , ± ln epsilon1, pi/2forHβJii= ipi/8forP (58)βJii= ipi for CZ ,wh ich is outside the usual (real) parameter range wh erethese spin models are defined.We rem ark that the schem e presented ab ove enableson e to perform x-rotations Rx(θ)withanarbitraryangleθ.Thisisachievedbysettingthefirstsingle-qutritgateacting on the upper qutrit to (µ, ν)= (−i cot θ, 1), an dthe two last single-qutrit gates to (µ, ν)= (i sin θ, 1). Thesame is true for z-rotations: they can be performed overan arb itrary an gle ξ by letting the two–qutrit gate thatacts on the lower qutrit have (µ, ν)= (eiξ, 1). In thiscase the parameter regime corresponds additionally toβJii=ln(−i cot θ), ln(i sin θ)forRx(θ)βJii= iξ for Rz(ξ) .(59)Th is gives a larger class of Potts models wh ose partitionfunction is BQ P–com plete.Ge mma Place this rema rk about the constraints.Wewo uld like to point out that our BQ P–com pleteness re-sults for the Potts model has (i) constraints in the pa-ram eter regime (basically the regime are all imagi narynu mbers, zero and infinite – so everything but the usu-ally con sidered regime), an d (ii) geom etric con strai ntsdue to the enc oding (coupl ing s have to be distribut ed inaspecificwaytomakethecomputationofitspartitionfunction have this complexity; e.g. obviously if they wereeverywhere zer o, or everywhere but in a trivial region, thecomplexity of the partition function would not be BQ P.11is a bit m ore involved and we refer the reader toAp pendix B fo r the details.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij 〉〈ij | , (5 6)is triv ia lly obtain ed by apply in g a two qutrit–gatebe tween the two physical qutrits of the first logicalqu bit with (µ, ν)= (1, 1) , an d doing the sam e forth e oth er logical qubit (s ee Fig. 6a) .• Fi nally, the phase gate between logical qubitsCZ =1summationdisplayi,j=0(−1)ij|ij 〉〈ij | (5 7)is achieved by apply in g a two qutrit–gate be-tw een the lower–qutrit of the first logical qubit andth e upper qutr it of th e second logical qudit with(µ, ν)= (−1, 1) . We also need to ap ply the sam egat e between the lower qudit of the secon d logi calqu bit and an auxi liary particle in the state |2〉 (s eeFi g. 6b) .|2〉(1 , 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a ) (b )tim e tim eFI G . 5: (a) Logica l single– qubit iden tity I1.(b)Logicalpha se gate P .Eachgateisdeterminedbythepairofnumbers(µ, ν)(Eq.(52 )) which are indicate d next to it, and its coloris just a guid e to the eye to id entify equal gates. A uxilia rysp ins (i.e. fixed sp ins) are colored in gray, and physical sp insin black. N ote that in both figures tim e runs from right toleft.Ge mma uni fy the two fig ur es in one ?In sum m ary, we have proven that by letting the qutritsinteract accordin g to a Potts-type nearest-neig hbor inter-ac tion , we can perform universal quan tum com putat ionat the logi cal level. From Eq . (3)itfollowsthatthecom-put ation of the pa rtition func tion of the Potts m ode l with3- level system s is a BQ P–c om plete prob lem .We n ow give a few rem arks regard in g th is con stru c-tion. First, we observe th at th e single–qubit identity I1re quire s to set ν =0,i.e.Jinegationslash= j= −∞ .Thi caveatcanbe circumvented by applying a mod fied gate, Iprime1wi th(µ, ν)= (1, 1) an d is thus within the usual param eterran ge of the Pot ts m odel. It can be re ad ily verified that|2〉(1 , 1)(1 , 1)(−1, 1)(−1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉CZ |ψ1〉|ψ2〉(a )(b )tim e tim eFI G . 6: (a) Logica l two–qubit iden tity I2.(b)Logicalcon-tr olled phase gate CZ .SeethecaptionofFig.5 fo r theme aning of the pair of numbers and the color associated toea ch gate.th e use of Iprimein stead of I re sults in a pre fac tor in the ob -ta ined partition function, nam ely Zprime=3IZ ,whereI isth e number of tim es Iprimeha s been appl ied. Thus , the com -pl exity of com put ing Z is the sam e as that of com putin gZ .ev en though I ma y scale with the system size?Se cond, no te tha t the im pl em entation of the gates H ,P an d CZ re quire com plex values of the energy Jii,morepr ecis ly:βJii= −ipi/2, 0, −∞ , ± ln epsilon1, pi/2forHβJii= ipi/8forP (5 8)βJii= ipi fo r CZ ,wh ich is outside the usual (real) param eter range wh ereth ese spin m odels are defined.We rem ark th at th e sch em e p resented ab ove en ab leson e to perform x-rotations Rx(θ)with an arbitraryangleθ.Thisisachievedbysettingthefirstsingle-qutritgateac ting on the upper qutrit to (µ, ν)= (−i co t θ, 1) , an dth e two last single-qutr it gate s to (µ, ν)= (i sin θ, 1) . Thesa m e is true for z-rotations: they can be perform ed overan arb itrary an gle ξ by letting the two–qutrit gate thatac ts on t lower qutrit have (µ, ν)= (eiξ, 1) . In thisca se the param et er reg im e co rres ponds additionally toβJii=ln(−i co t θ), ln (i sin θ)forRx(θ)βJii= iξ fo r Rz(ξ) .(5 9)Th is gives a larger class of Potts m odels wh ose partitionfu nction is BQ P–c om plete.Ge mma Place thi s rema rk about the cons traints.Wewo uld like to point out that our BQ P–c om pleteness re -su lts for the Potts m odel has (i) constraints in the pa-ram eter re gim e (bas ically the re gim e are all im agi narynu m bers, zero and infinite – so everything but the usu-ally con sidere d re gim e), an d (ii) ge om etric con strai ntsdue to the enc odi ng (coupl ing s ha ve to be di stribut ed inaspecific way tom kethe com utation ofits paritionfu nction have this com plexity; e.g. obviously if they wereev er yw er e zer o, or ev er ywher e but in a trivial eg ion, theco m plex ity of the partition funct ion would not be BQ P.11is a bit more involved and we refer the reader toAp pendix B for the details.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij〉〈ij| , (56)is trivially obtained by applying a two qutrit–gatebetween the two physical qu rits of the first logicalqubit with (µ, ν)= (1, 1), an doing the sam e forthe other logical qubit (see Fig. 6a).• Finally, the phase gate between logical qubitsCZ =1summationdisplayi,j=0(−1)ij|ij〉〈ij| (57)is achieved by applying a two qutrit–gate be-tween the lower–qutrit of the first logical qubit andthe upper qutrit of the second lo ical qudit with(µ, ν)= (−1, 1). We also need to apply the sam egat e between the lower qudit of the second logi calqubit and an auxiliary particle in the state |2〉 (seeFig. 6b).|2〉(1, 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a) (b)time timeFIG. 5: (a) Logical single–qubit identity I1.(b)Logicalpha se gate P .Eachgateisdeterminedb thepairofnumbers(µ, ν)(Eq.(52)) which are indicated next to it, and its coloris just a guide to the ye to identify equal gates. Auxilia ryspins (i.e. fixed spins) are colored in gr y, and physical spinsin black. Note that in both figures tim e runs from right toleft.Ge mma uni fy the two figures in one?In summary, we have proven that by letting the qutritsinteract according to a Potts-type nearest-neighbor inter-action, we can perform universal quantum com putationat the logi cal level. From Eq . (3)itfollowsthatthecom-put ation of the partition func tion of the Potts model with3-level systems is a BQP–com plet prob lem.We now give a few rem arks r garding this co struc-tion. First, we observe that the single–qubit identity I1requires to set ν =0,i.e.Jinegationslash=j= −∞ .Thiscaveatcanbe circumvented by applying a modified gate, Iprime1with(µ, ν)= (1, 1) and is thus within the usual param eterran ge of the Potts model. It can be readily verified that|2〉(1, 1)(1, 1)(−1, 1)( 1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉 CZ |ψ1〉|ψ2〉(a))time ti eFIG. 6: (a) Logical two–qubit identittrolled phase gate CZ for theme aning of the pair of numbers and t l i ted toeach gate.the use of Iprimeinstead of I results in a prefactor in the ob-tained partition function, namely Zprime=3IZ,whereI isthe number of times Iprimehas been appl ied. Thus, the com-plexity of comput ing Z is the same as that of computingZ.even though I ma y scale with the system size?Second, note that the implementation of the gates H ,P and CZ require com plex values of the energy Jii,moreprecisely:βJii= −ipi/2, 0,−∞ , ± ln epsilon1, pi/ HβJii= ipi/8frP (58)βJii= ipi for CZ ,wh ich is outside the usual (real) parameter range wh erethes spin models are defin d.We rem ark that the schem e presented above enablesone to perform x-rotations Rx(θ)withanarbitraryangleθ.Thisisachievedbysettingthefirstsingle-qutritgatacting on the upper qutrit to (µ, ν)= (−i cot θ, 1), andthe two last single-qutrit gates to (µ, ν)= (i sin θ, 1). Thesame is true for z-rotations: they can be performed overan arb itrary angle ξ by letting the two–qutrit gate thatacts on the lower qutrit have (µ, ν)= (eiξ, 1). In iscase the parameter regime corresponds additionally toβJii=ln(−i cot θ), ln(i sin θ)forRx(θ)βJii= iξ for Rz(ξ) .(59)Th is gives a larger class of Potts models wh ose partitionfunction is BQP–com plete.Ge mma Place this rema rk about the constraints.Wewo uld like to point out that our BQP–com pleteness re-sults for the Potts model has (i) constraints in the pa-ram eter regime (basically the regime are all imagi narynu mbers, zero and infinite – so everything but the usu-ally considered regim ), and (ii) geom etric constraintsdue to the encoding (coupl ings have to be distribut ed inaspecificwaytomakethecomputationofitspartitionfunction have this complexity; e.g. obviously if they wereeverywhere zer o, or everywhere but in a trivial region, thecomplexity of the partition function would not be BQP.11is a bit m ore involved and we refer the reader toAp pendix B fo r the details.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij 〉〈ij | , (5 6)is triv ia lly obtain ed by apply in g a two qutrit–gatebe tween the two physical qutrits of the first logicalqu bit with (µ, ν)= (1, 1) , an d doing the sam e forth e oth er logic l qubit (s ee Fig. 6a) .• Fi nally, the phase gate between logical qubitsCZ =1summationdisplayi,j=0(−1)ij|ij 〉〈ij | (5 7)is achieved by apply in g a two qutrit–gate be-tw een the lower–qutrit of the first logical qubit andth e upper qutr it of th e second logical qudit with(µ, ν)= (−1, 1) . We also need to ap ply the sam egat e b tween the lower qudit of the secon d logi calqu bit and an auxi liary parti le in the state |2〉 (s eeFi g. 6b) .|2〉(1 , 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a ) (b )tim e tim eFI G . 5: (a) Logica l single– qubit iden tity I1.(pha se gat P .Eachgateisdeterminedbythepair rs(µ, ν)(Eq.(52 )) w ich are indicate d nex to it, and oloris just a guid e to t e eye to id entify qual gates. ilia rysp ins (i.e. fixed sp ins) are c lored in gray, and physical sp insin black. N ote that in both figures tim e runs from right toleft.Ge mma uni fy the two fig ur es in one ?In sum m ary, we have proven that by letting the qutritsinteract accordin g to a Potts-type nearest-neig hbor inter-ac tion , w can perform universal quan tum com putat ionat the logi cal level. From Eq . (3)itfollows hatthecom-put ation of the pa rtition func tion of the Potts m ode l with3- level system s is a BQ lete prob lem .We n ow give a few r s regard in g th is con stru c-tion. First, we observe e single–qubit identity I1re quire s to set ν =0 Jinegationslash= j−∞ .Thiscaveatcanbe circumvented by applying a modified gate, Iprime1wi th(µ, ν)= (1, 1) an d is thus within the usual param eterran ge of the Pot ts m odel. It can be re ad ily verified that|2〉(1 , 1)(1 , 1)(−1, 1)(−1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉CZ |ψ1〉|ψ2〉(a )(b )tim e tim eFI G . 6: (a) Logica l two–qubit iden tity I2.(b)Logicalcon-tr olled phase gate CZ .SeethecaptionofFig.5 fo r theme aning of the pair of numbers and the color associated toea ch gate.th e use of Iprimein stead of I re sults in a pre fac tor in the ob -ta ined partition function, nam ely Zprime=3IZ ,whereI isth e number of tim es Iprimeha s been appl ied. Thus , the com -pl exity of com put ing Z is the sam e as that of com putin gZ .ev en though I ma y scale with t e syste size?Se cond, no te tha t the im pl em entation of the gates H ,P an d CZ re quire com plex values of the energy Jii,morepr ecisely:βJii= −ipi/2, 0, −∞ , ± ln epsilon1, pi/2forHβJii= ipi/8forP (5 8)βJii= ipi fo r CZ ,wh ich is outside the usual (real) param eter range wh ereth ese spin m odels are defined.We rem ark th at th e sch em e p resented ab ove en ab leson e to perform x-rotations Rx(θ)with an arbitraryangleθ.Thisisachievedbysettingthefirstsingle-qutritgateac ting on the upper qutrit to (µ, ν)= (−i co t θ, 1) , an dth e two last single-qutr it gate s to (µ, ν)= (i sin θ, 1) . Thesa m e i true for z-rotations: they can be perform d overan arb itrary an gle ξ by letting the two–qutrit gate thatac ts on the lower qutrit hav (µ, ν)= (eiξ, 1) . In thisca se the param et er reg im e co rres ponds additionally toβJii=ln(−i co t θ), ln (i sin θ)forRx(θ)βJii= iξ fo r Rz(ξ) .(5 9)Th is gives a larger class of Potts m odels wh ose partitionfu nction is BQ P–c om plete.Ge mma Place thi s rema rk about the cons traints.Wewo uld lik to point out that our BQ P–c om pleteness re -su lts for the Potts m odel has (i) constraints in the pa-ram eter re gim e (bas ically the re gim e are all im agi narynu m bers, zero a d infinite – so everything but the usu-ally con sidere d re gim e), an d (ii) ge om etric con strai ntsdue o the enc odi ng (coupl ing s ha ve to be di stribut ed inaspe ific way tomak the computation ofis partitionfu nction have this com plexity; e.g. obviously if they wereev er ywher e zer o, or ev er ywher e but in a trivial reg ion, theco m plex ity of the partition funct ion would not be BQ P.11is a bit more involved and we refer the reader toAp pendix B for the details.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij〉〈ij | , (5 6)is trivially obtained by applying a two qutrit–gatebe tween the two physical qutrits of the first logicalqu bit with (µ, ν)= (1, 1), an d doing the sam e forth e oth er logical qubit (see Fig. 6a).• Fi nally, the phase gate between logical qubitsCZ =1summationdisplayi,j=0(−1)ij|ij〉〈ij | (5 7)is achieved by applying a two qutrit–gate be-tw een the lower–qutrit of the first logical qubit andth e upper qutrit of th e second logical qudit with(µ, ν)= (−1, 1). We also need to ap ply the sam egat e between the lower qudit of the se on d logi calqu bit and an auxiliary particle in the s ate |2〉 (seeFi g. 6b) .|2〉(1 , 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a) (b )time timeFI G. 5: (a) Logica l single– qubit iden tity I1.(b)Logicalpha se gate P .Eachgateisdeterminedbythepairofnumbers(µ, ν)(Eq.(52 )) which are indicated next to it, and its coloris just a guide to the eye to identify equal gates. Auxilia rysp ins (i.e. fixed sp ins) are colored in gray, and physical sp insin black. Note that in both figures tim e runs from right toleft.Ge mma uni fy the two fig ur es in one ?In summary, we have proven that by letting the qutritsinteract according to a Potts-type nearest-neighbor inter-ac tion , we can perform universal quan tum com putationat the logi cal level. From Eq . (3)itfollowsthatthecom-put ation of the pa rtition func tion of the Potts mode l with3-level systems is a BQ P–c om plete prob lem.We now give a few rem arks regarding this construc-tion. First, we observe th at th e single–qubit identity I1requires to set ν =0,i.e.Jinegationslash=j= −∞ .Thiscaveatcanbe circumvented by applying a modified gate, Iprime1wi th(µ, ν)= (1, 1) an d is thus within the usual param eterran ge of the Potts model. It can be read ily verified that|2〉(1 , 1)(1 , 1)(−1, 1)(−1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉 CZ |ψ1〉|ψ2〉(a)(b )time timeFI G. 6: (a) Logica l two–qubit iden tity I2.(b)Logicalcon-trolled phase gate CZ .SeethecaptionofFig.5 for theme aning of the pair of numbers and the color associated toea ch gate.th e use of Iprimeinstead of I results in a prefac tor in the ob -ta ined partition function, namely Zprime=3IZ ,whereI isth e number of times Iprimeha s been appl ied. Thus , the com-plexity of comput ing Z is the same as that of computingZ .even though I ma y scale with the system size?Se cond, no te ha t the implementation of the gates H ,P an d CZ require com plex values of the energy Jii,morepr ecisely:βJii= −ipi/2, 0, −∞ , ± ln epsilon1, pi/2foHβJii= ipi/8frP (5 8)βJii= ipi for CZ ,wh ich is tside he usual (real) parameter range wh ereth ese spin models are defined.We rem ark that the schem e presented ab ove enableson e to perform x-rotations Rx(θ)withanarbitraryangleθ.Thisisachievedbysettingthefirstsingle-qutritgateac ting on the upper qutrit to (µ, ν)= (−i co t θ, 1), an dth e two last single-qutrit gates to (µ, ν)= (i sin θ, 1). Thesame is true for z-rotations: they can be performed overan arb itrary an gle ξ by letting the two–qutrit gate thatac ts on the lower qutrit have (µ, ν)= (eiξ, 1). In thisca se the parameter reg ime co rresponds additionally toβJii=ln(−i co t θ), ln(i sin θ)forRx(θ)βJii= iξ for Rz(ξ) .(5 9)Th is gives a larger class of Potts models wh ose partitionfunction is BQ P–c om plete.Ge mma Place this rema rk about the cons traints.Wewo uld like to point out that our BQ P–c om pleteness re-su lts for the Potts model has (i) constraints in the pa-ram eter regime (basically the regime are all imagi narynu mbers, zero and infinite – so everything but the usu-ally con sidered regime), an d (ii) ge om etric con strai ntsdue to the enc oding (coupl ing s ha ve to be distribut ed inaspecificwaytomakethecomputationofitspartitionfunction have this complexity; e.g. obviously if they wereeverywhere zer o, or everywhere but in a trivial reg ion, theco mplex ity of the partition function would not be BQ P.11is a bit m ore involved and we refer the reader toAp pendix B fo r the details.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij 〉〈ij | , (5 6)is triv ia lly obtain ed by apply in g a two qutrit–gatebe tween the two physical qutrits of the first logicalqu bit with (µ, ν)= (1, 1) , an d doing the sam e forth e oth er logical it (s ee Fig. 6a) .• Fi nally, the phase gate between l gical qubitsCZ =1summationdisplayi,j=0(−1)ij|ij 〉〈ij | (5 7)is achieved by apply in g a two qutrit–gate be-tw een the lower–qutrit of the first logical qubit andth e upper qutr it of th e second logical qudit with(µ, ν)= (−1, 1) . We also need t ap ply the samgat e between the lower qudit of the secon d logi calqu bit and an auxi liary particle in the state |2〉 (s eeFi g. 6b) .|2〉(1 , 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a ) (b )tim e tim eFI G . 5: (a) Logica l single– qubit iden tity I1.(b)Lgicalpha se gate P .Eachgateisdeterminedbythepairofnumb rs(µ, ν)(Eq.(52 )) which are indicate d next to it, and its coloris just a guid e to the eye to id entify equal gates. A uxilia rysp ins (i.e. fixed sp ins) are colored in gray, and physical sp insin black. N ote that in both figures tim e runs from right toleft.Ge mma uni fy the two fig ur es in one ?In sum m ary, we have proven that by letting the qutritsinteract accordin g to a Potts-type nearest-neig hbor inter-ac tion , we can perform universal quan tum com putat ionat the logi cal level. From Eq . (3)itfollowsthatthecom-put ation of the pa rtition func tion of the Potts m ode l with3- level system s is a BQ P–c om plete prob lem .We n ow give a few rem arks regard in g th is con stru c-tion. First, we observe th at th e s ngle–qubit identity I1re quire s to set ν =0,i. .Jinegationslash= j= −∞ .Thiscaveatcanbe circumvented by applying a modified gate, Iprime1wi th(µ, ν)= (1, 1) an d is thus within the usual param eterran ge of the Pot ts m odel. It can be re ad ily verified that|2〉(1 , 1)(1 , 1)(−1, 1)(−1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉CZ |ψ1〉|ψ2〉(a )(b )tim e tim eFI G . 6: (a) Logica l two–qubit iden tity I2.(b)Logicalcon-tr olled phase gate CZ .SeethecaptionofFig.5 fo r theme aning of the pair of numbers and the color associated toea ch gate.th e use of Iprimein stead of I re sults in a pre fac tor in the ob -ta ined partition function, nam ely Zprime=3IZ ,whereI isth e number of tim es Iprimeha s been appl ied. Thus , the com -pl exity of com put ing Z is the sam e as that of com putin gZ .ev en though I ma y scale with the system size?Se cond, no te tha t the im pl em entation of the gates H ,P an d CZ re quire com plex values of the energy Jii,morepr ecisely:βJii= −ipi/2, 0, −∞ , ± ln epsilon1, pi/2forHβJii= ipi/8forP (5 8)βJii= ipi fo r CZ ,wh ich is outside the usual (real) param eter range wh ereth es spin m odels are defined.We rem ark th at th e sch em e p resented ab ove en ab leson e to perform x-rotations Rx(θ)with an arbitraryangleθ.Thisisachevedbysettingthefirstsingle-qutritgateac ting on the upper qutrit to (µ, ν)= (−i co t θ, 1) , an dth e two last single-qutr it gate s to (µ, ν)= (i sin θ, 1) . Thesa m e is true for z-r tations: they can be perform ed overan arb itrary an gle ξ by letting the two–qutrit gate thatac ts on the lower qutrit have (µ, ν)= (eiξ, 1) . In thisca se the param et er reg im e co rres ponds additionally toβJii=ln(−i co t θ), ln (i sin θ)forRx(θ)βJii= iξ fo r Rz(ξ) .(5 9)Th i give a larger class of Potts m odels wh ose partitionfu nction is BQ P–c om plete.Ge mma Place thi s rema rk about the cons traints.Wewo uld like to point out that our BQ P–c om pleteness re -su lts for the Potts m odel has (i) constraints in the pa-ram eter re gim e (bas ically the re gim e are all im agi narynu m bers, zero and infinite – so everything but the usu-ally con sidere d re gim e), an d (ii) ge om etric con strai ntsdue to the enc odi ng (coupl ing s ha ve to be di stribut ed inaspecific way tomakethe computation ofits partitionfu nction have this com plexity; e.g. obviously if they wereev er ywher e zer o, or ev er ywher e but in a trivial reg ion, theco m plex ity of the partition funct ion would not be BQ P.11is a bit more involved and we refer the reader toAp pendix B fo r the etails.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij 〉〈ij | , (5 6)is trivially obtained by applying a two qutrit–gatebe tween the two physical qutrits of the first logicalqu bit with (µ, ν)= (1, 1) , an d doing the sam e forth e oth er logical qubit (see Fig. 6a) .• Fi nally, the phase gate between logical qubitsCZ =1summationdisplayi,j=0(−1)ij|ij 〉〈ij | (5 7)is achieved by applying a two qutrit–gate be-tw een the lower–qutrit of the first logical qubit andth e upper qutrit of th e second logical qudit with(µ, ν)= (−1, 1) . We also need to ap ply the sam egat e between the lower qudit of the secon d logi calqu bit and an auxiliary particle in the state |2〉 (seeFi g. 6b) .|2〉(1 , 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a ) (b )tim e tim e. 5: (a) Logica l single– qubit iden tity I1.(b)Logicalse gate P .Eachgateisdeterminedbythepairofnumbers(µ, ν)( q.(52 )) which are indicate d next to it, and its coloris just a guid e to the eye to id entify equal gates. Auxilia rysp ins (i.e. fixed sp ins) are colored in gray, and physical sp insin black. Note that in both figures tim e runs from right toleft.Ge mma uni fy the two fig ur es in one ?In summary, we have proven that by letting the qutritsinteract according to a Potts-type nearest-neighbor inter-ac tion , we can perform universal quan tum com putat ionat the logi cal level. From Eq . (3)itfollowsthatthecom-put ation of the pa rtition func tion of the Potts mode l with3- level systems is a BQ P–c om plete prob lem.We now give a few rem arks regarding this construc-tion. First, we observe th at th e single–qubit identity I1requires to set ν =0,i.e.Jinegationslash=j= −∞ .Thiscaveatcanbe circumvented by applying a modified gate, Iprime1wi th(µ, ν)= (1, 1) an d is thus within the usual param eterran ge of the Pot ts model. It can be read ily verified that|2〉(1 , 1)(1 , 1)(−1, 1)(−1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉CZ |ψ1〉|ψ2〉(a )(b )tim e tim eFI G. 6: (a) L gica l two–qubit iden tity I2.(b)Logicalcon-trolled phase gate CZ .SeethecaptionofFg.5 for theme aning of the pair of numbers and the color associated toea ch gate.th e use of Iprimeinstead of I results in a prefac tor in the ob -ta ined partition function, nam ely Zprime=3IZ ,whereI isth e number f tim es Iprimeha s been appl ied. Thus , the com-pl exity of comput ing Z is the same as that of computingZ .ev en though I ma y scale with the system size?Se cond, no te tha t the impl e entation of the gates H ,P an d CZ require com plex values of the energy Jii,morepr ecisely:βJii= −ipi/2, 0, −∞ , ± ln epsilon1, pi/2forHβJii= ipi/8frP (5 8)βJii= pi fo r CZ ,wh ich is outside the usual (real) parameter range wh ereth ese spin m odels are defined.We rem ark that the sch m e presented ab ove enableson e to perform x-rotations Rx(θ)with na bitr ryangleθ.Th isachivedbysettingthefirstsingle-qutri gateac ting on the upper qutrit to (µ, ν)= (−i co t θ, 1) , an dth e two la t single-qutrit gate s to (µ, ν)= (i sin θ, 1) . Thesa me is true for z-rotations: they can be performed overan arb itrary an gle ξ by letting the two–qutrit gate thatac ts on the lower qutrit have (µ, ν)= (eiξ, 1) . In thisca se the parameter reg ime co rres ponds additionally toβJii=ln(−i co t θ), ln (i sin θ)forRx(θ)βJii= iξ fo r Rz(ξ) .(5 9)Th is gives a larger class of Potts models wh ose partitionfu nction is BQ P–c om plete.Ge mma Place thi s rema rk about the cons traints.Wewo uld like to point out that our BQ P–c om pleteness re-su lts for the Potts model has (i) constraints in the pa-ram eter regime (bas ically the regime are all imagi narynu mbers, zero and infinite – so everything but the usu-ally con sidered regime), an d (ii) ge om etric con strai ntsdue to the enc odi ng (coupl ing s ha ve to be di stribut ed inaspecificway tomakethe computation ofitspartitionfu nction have this com plexity; e.g. obviously if they wereev er ywher e zer o, or ev er ywher e but in a trivial reg ion, theco mplex ity of the partition function would not be BQ P.11is a bit m ore involved and we refer the reader toAp pendix B fo r the details.• Th e two–qubit identity gateI2=1summationdisplayi,j=0|ij 〉〈ij | , (5 6)is triv ia lly obtain ed by apply in g a two qutrit–gatebe tween the two physical qutrits of the first logicalqu bit with (µ, ν)= (1, 1) , an d doing the sam e forth e oth er logical qubit (s ee Fig. 6a) .• Fi nally, the phase gate between l gical qubi sCZ =1summationdisplayi,j=0(−1)ij|ij 〉〈ij | (5 7)is achieved by apply in g a two qutrit–gate be-tw een the lower–qutrit of the first logical qubit andth e upper qutr it of th e second logical qudit with(µ, ν)= (−1, 1) . We also need to ap ply the sam egat e between the lower qudit of the secon d logi calqu bit and an auxi liary parti le in the state |2〉 (s eeFi g. 6b) .|2〉(1 , 1)(eipi/8, 1)|ψ〉I1|ψ〉|ψ〉P |ψ〉(a ) (b )tim e tim eFI G . 5: (a) Logica l single– qubit iden tity I1.(b)Logicalpha se gat P .Eachgateisd terminedbythep irofnumbers(µ, ν)(Eq.(52 )) which are indicate d next to it, and its coloris just a guid e to the eye to id entify equal gates. A uxilia rysp ins (i.e. fixed sp ins) are colored in g ay, and physical sp insin black. N ote th t in both figures tim e runs from right toleft.Ge mma uni fy the two fig ur es in one ?In sum m ary, we have proven that by letting the qutritsinterac accordin g to a Potts-type nearest-neig hbor inter-ac tion , we can perform universal quan tum com putat ionat the logi cal level. From Eq . (3)itfollowsthatthecom-put ation of the pa rtition func tion of the Potts m ode l with3- level system s i a BQ P–c om plete prob lem .We n ow give a few rem arks regard in g th is con stru c-tion. First, we observe th at th e single–qubit identity I1re quire s to set ν =0,i.e.Jinegationslash= j= −∞ .Thiscaveatcanbe circumvented by applying a modified gate, Iprime1wi th(µ, ν)= (1, 1) an d is thus within the usual param eterran ge of the Pot ts m od l. It can be re ad ily verified that|2〉(1 , 1)(1 , 1)(−1, 1)(−1, 1)|ψ1〉|ψ2〉|ψ1〉|ψ2〉I2|ψ1〉|ψ2〉CZ |ψ1〉|ψ2〉(a )(b )tim e tim eFI G . 6: (a) Logica l two–qubit iden tity I2.(b)Logicalcon-tr olled phase gate CZ .SeethecaptionofFig.5 fo r theme aning of the pair of numbers and the color associated toea ch gate.th e use of Iprimein stead of I re sults in a pre fac tor in the ob -ta ined partition function, nam ely Zprime=3IZ ,whereI isth e number of tim es Iprimeha s been appl ied. Thus , the com -pl exity of com put ing Z is the sam e as that of com putin gZ .ev en though I ma y scale with the system size?Se cond, no te tha t the im pl em entation of the gates H ,P an d CZ re quire com plex values of the energy Jii,morepr ecisely:βJii= −ipi/2, 0, −∞ , ± ln epsilon1, pi/2forHβJii= ipi/8forP (5 8)βJii= ipi fo r CZ ,wh ich is outside the usual (real) param eter range wh ereth ese spin m odels are defined.We rem ark th at th e sch em e p resented ab ove en ab leson e to perform x-rotations Rx(θ)with an arbitraryangleθ.Thisisachievedbysettingthefirstsingle-qutritgateac ting on the upper qutrit to (µ, ν)= (−i co t θ, 1) , an dth e two last single-qutr it gate s to (µ, ν)= (i sin θ, 1) . Thesa m e is true for z-rotations: they can be perform ed overan arb itrary an gle ξ by letting the two–qutrit gate thatac ts on the lower qutrit have (µ, ν)= (eiξ, 1) . In thisca se the param et er reg im e co rres ponds additionally toβJii=ln(−i co t θ), ln (i sin θ)forRx(θ)βJii= iξ fo r Rz(ξ) .(5 9)Th is gives a larger class of Potts m odels wh ose partitionfu nction is BQ P–c om plete.Ge mma Place thi s rema rk about the cons traints.Wewo uld like to point out that our BQ P–c om pleteness re -su lts for the Potts m odel has (i) constraints in the pa-ram eter re gim e (bas ically the re gim e are all im agi narynu m bers, zero and infinite – so everything but the usu-ally con sidere d re gim e), an d (ii) ge om etric con strai ntsdue to the enc odi ng (coupl ing s ha ve to be di stribut ed inaspecific way tomakethe computation ofits partitionfu nction have this com plexity; e.g. obviously if they wereev er ywher e zer o, or ev er ywher e but in a trivial reg ion, theco m plex ity of the partition funct ion would not be BQ P.GDlC, M. Van den Nest, W. Dür, H. J. Briegel, M.A. Martin-Delgado (in preparation)12Do you want to include this paragraph? From thepoint of view of the complexity results, to have a discreteparameter regime of the Potts model for which its com-putation is BQP–complete is a stronger result than withacontinuousparameterregime.However,fromthepointof view of a quantum algorithm, the larger the param e-ter regime, the stronger the result, because it can includemore Potts model for which we propose a quantum al-gorithm. Note, however, that both param eter regimesare complex, and thus the quantum algorithms cannotbe used to compute Potts model with real, i.e. physical,parameters. This problem was already encountered inRef. [4–6].Third, in the constructions presented above we needaconstantsupplyofauxiliaryqutrits. Thereforeween-visage two possible setups. One possibility is to haveauxiliary qutrits in the middle of a 2D square lattice incontact with the nodes, but this requires to set bound-ary conditions also at the middle of the lattice. Thisdrawback is circumvented in the second setup, in whichphysical qubits are in contact with four auxiliary qubits:one in |0〉,onein|1〉,anotheronein|2〉 and the fourthauxiliary in any of these values (it is four instead of threebecause of symmetry reasons), thus forming a triangularlattice (see Fig. 7a). Gates in the direction of time corre-spond to a single qutrit gates, whereas gates perpendic-ular to this direction correspond to two–qutrit gates (seeFig. 7b). All single–qutrit gates for auxiliary particlesare single–qutrit identity gates. Note that the auxiliaryparticles are left unchanged after any gate.Fourth, we see with our construction that the Pottsmodel in a 1D array is not BQP–complete, whereas thismodel on a 2D setup (and with complex parameters) isBQP–complete. This is in agreement with the fact thatthe Potts model in 1D array or a tree–like structure isefficiently simulatable classically [14].Finally, this result can be generalized to Potts modelwith any q.Inthiscase,theencodedstatesarestilgiven by Eq. (51), and all gates are performed with thesame procedure except for the Hadamard. For this gate,one adds filters for the |3〉 ... |q − 1〉 components on theupper and the lower qudit right after the filters for the |2〉and the |0〉 component of Fig. 11.Thatis,thenumberof filters scales linearly with q (since one requires q − 2filters for each qudit). Moreover, each physical qudit hasto be connected to 2ceilingleftq/2ceilingright auxiliary particles, each fixedin a different state, namely |0〉,..., |q −1〉.Thisamountsto a similar construction to that of Fig. 7 but where eachphysical qudit is connected to ceilingleftq/2ceilingright auxiliary qudits tothe left and to the right. Gemma do we need some extrafigure on that? I wouldn’t add one, otherwise it’ll be toolongD. Z2Lattice gauge theoryNow we turn to a different class of models, namelyLGTs. Using the same tools (presented in Sec. IV C), we|0〉|0〉|0〉|1〉|1〉|1〉|2〉|2〉|2〉|2〉|2〉|2〉|0〉|0〉|0〉|1〉|1〉|1〉aux.aux.aux.phys.phys.phys.aux.aux.aux.time|ψt1〉|ψt2〉|ψt+11〉|ψt+12〉|ψt1〉|ψt2〉(1, 1)(1, 0)==(a)(b)FIG. 7: Setup for a 2D Potts model with the physical (phys.)qutrits surrounded by auxiliary (aux.) qutrits, i.e. by qutritswhose value is fixed. Single–qutrit gates are applied in thetime direction, and two–qutrit gates are applied in a fixed timeslice. (a) A time slice of the lattice at time t,whereonecanseethe triangular structure with two auxiliary qutrits connectedto each physical qutrit. Each logical qutrit is composed of twophysical qutrits. (b) Two time slices of the lattice, at times tand t +1. Thefigureshowsanexampleofacircuit,whereaphase gate P is applied to |ψt1〉 and the gate CZ is appliedto |ψt+11〉|ψt+12〉.will prove that computing the partition function of the3D Z2LGT (in a specific, complex parameter regime) isBQP–complete. Gemma check this Here we will make useof the gauge symmetry to fix the value of some spins, in-stead of fixing them boundary conditions as in Sec. VB,VC.Inparticular,wewillfixthespinsinthetimedi-rection of edges that connect logical qubits (see below)at different time slices, and some other spins (not in thetime direction), as will be specified below.Our goal is to construct, at the logical level, the uni-versal gate setRz(ξ)= |0〉〈0| + eiξ|1〉〈1|H =summationtext1i,j=0,1(−1)ij|j〉〈i|σz⊗ σz=summationtext1i,j=0(−1)i⊕j|ij〉〈ij| .(60)18|0〉|0〉|0〉|0〉|0〉|1〉|1〉|1〉|1〉|1〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|0〉|0〉|0〉|0〉|0〉|1〉|1〉|1〉|1〉|1〉(−i,1)(0, 1)(0, 1)(0, 1)(0, 1)(0, 1)(epsilon1, 1)(epsilon1, 1)(epsilon1, 1)(epsilon1, 1)(epsilon1, 1)(1epsilon1√2, 1)(1epsilon1√2, 1)(1epsilon1√2, 1)(i, 1)(i, 1)(−i,1)(1, 1)timeFIG. 11: Sequence of gates at the physical level required to perform a Hadamard rotation at the logical level, H.Seethecaption of Fig. 5 for the meaning of the pair of numbers and the color associatedtoeachgate.Gemma here there are newcolors Gemma time is inversed!Hadamard gateBQP-completeness resultsIIExample of part of a circuit:Note distribution of physical and auxiliary qubits12Do you want to include this paragraph? From thepoint of view of the complexity results, to have a discreteparameter regime of the Potts model for which its com-putation is BQP–complete is a stronger result than withacontinuousparameterregime.However,fromthepointof view of a quantum algorithm, the larger the param e-ter regime, the stronger the result, because it can includemore Potts model for which we propose a quantum al-gorithm. Note, however, that both param eter regimesare complex, and thus the quantum algorithms cannotbe used to compute Potts model with real, i.e. physical,parameters. This problem was already encountered inRef. [4–6].Third, in the constructions presented above we needaconstantsupplyofauxiliaryqutrits. Thereforeween-visage two possible setups. One possibility is to haveauxiliary qutrits in the middle of a 2D square lattice incontact with the nodes, but this requires to set bound-ary conditions also at the middle of the lattice. Thisdrawback is circumvented in the second setup, in whichphysical qubits are in contact with four auxiliary qubits:one in |0〉,onein|1〉,anotheronein|2〉 and the fourthauxiliary in any of these values (it is four instead of threebecause of symmetry reasons), thus forming a triangularlattice (see Fig. 7a). Gates in the direction of time corre-spond to a single qutrit gates, whereas gates perpendic-ular to this direction correspond to two–qutrit gates (seeFig. 7b). All single–qutrit gates for auxiliary particlesare single–qutrit identity gates. Note that the auxiliaryparticles are left unchanged after any gate.Fourth, we see with our construction that the Pottsmodel in a 1D array is not BQP–complete, whereas thismodel on a 2D setup (and with complex parameters) isBQP–complete. This is in agreement with the fact thatthe Potts model in 1D array or a tree–like structure isefficiently simulatable classically [14].Finally, this result can be generalized to Potts modelwith any q.Inthiscase,theencodedstatesarestilgiven by Eq. (51), and all gates are performed with thesame procedure except for the Hadamard. For this gate,one adds filters for the |3〉 ... |q − 1〉 components on theupper and the lower qudit right after the filters for the |2〉and the |0〉 component of Fig. 11.Thatis,thenumberof filters scales linearly with q (since one requires q − 2filters for each qudit). Moreover, each physical qudit hasto be connected to 2ceilingleftq/2ceilingright auxiliary particles, each fixedin a different state, namely |0〉,..., |q −1〉.Thisamountsto a similar construction to that of Fig. 7 but where eachphysical qudit is connected to ceilingleftq/2ceilingright auxiliary qudits tothe left and to the right. Gemma do we need some extrafigure on that? I wouldn’t add one, otherwise it’ll be toolongD. Z2Lattice gauge theoryNow we turn to a different class of models, namelyLGTs. Using the same tools (presented in Sec. IV C), we|0〉|0〉|0〉|1〉|1〉|1〉|2〉|2〉|2〉|2〉|2〉|2〉|0〉|0〉|0〉|1〉|1〉|1〉aux.aux.aux.phys.phys.phys.aux.aux.aux.time|ψt1〉|ψt2〉|ψt+11〉|ψt+12〉|ψt1〉|ψt2〉(1, 1)(1, 0)==(a)(b)FIG. 7: Setup for a 2D Potts model with the physical (phys.)qutrits surrounded by auxiliary (aux.) qutrits, i.e. by qutritswhose value is fixed. Single–qutrit gates are applied in thetime direction, and two–qutrit gates are applied in a fixed timeslice. (a) A time slice of the lattice at time t,whereonecanseethe triangular structure with two auxiliary qutrits connectedto each physical qutrit. Each logical qutrit is composed of twophysical qutrits. (b) Two time slices of the lattice, at times tand t +1. Thefigureshowsanexampleofacircuit,whereaphase gate P is applied to |ψt1〉 and the gate CZ is appliedto |ψt+11〉|ψt+12〉.will prove that computing the partition function of the3D Z2LGT (in a specific, complex parameter regime) isBQP–complete. Gemma check this Here we will make useof the gauge symmetry to fix the value of some spins, in-stead of fixing them boundary conditions as in Sec. VB,VC.Inparticular,wewillfixthespinsinthetimedi-rection of edges that connect logical qubits (see below)at different time slices, and some other spins (not in thetime direction), as will be specified below.Our goal is to construct, at the logical level, the uni-versal gate setRz(ξ)= |0〉〈0| + eiξ|1〉〈1|H =summationtext1i,j=0,1(−1)ij|j〉〈i|σz⊗ σz=summationtext1i,j=0(−1)i⊕j|ij〉〈ij| .(60)18|0〉|0〉|0〉|0〉|0〉|1〉|1〉|1〉|1〉|1〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|2〉|0〉|0〉|0〉|0〉|0〉|1〉|1〉|1〉|1〉|1〉(−i,1)(0, 1)(0, 1)(0, 1)(0, 1)(0, 1)(epsilon1, 1)(epsilon1, 1)(epsilon1, 1)(epsilon1, 1)(epsilon1, 1)(1epsilon1√2, 1)(1epsilon1√2, 1)(1epsilon1√2, 1)(i, 1)(i, 1)(−i,1)(1, 1)timeFIG. 11: Sequence of gates at the physical level required to perform a Hadamard rotation at the logical level, H.Seethecaption of Fig. 5 for the meaning of the pair of numbers and the color associatedtoeachgate.Gemma here there are newcolors Gemma time is inversed!Hadamard gateApproximating the partition function of a 2D 3-level Potts with auxiliary qubits on a certain complex parameter regime is BQP-completeBQP-completeness resultsIIExample of part of a circuit:Note distribution of physical and auxiliary qubitsEncoding:|0〉 =|0〉|0〉|0〉|0〉|1〉 =|1〉|1〉|1〉|1〉Trivial preparation of |0〉...|0〉 from|R〉 = |0〉...|0〉 3D LGTZ2Each LGT-type gate is characterized by the pair (eβJii,eβJinegationslash=j)Z213No te that this is a continuous universal gate set Wo lf-gan g, is this a prob lem or an ad vantage ?.Notethatthisset includes the single–qubit identity I1,andthetwo–qu bit identity I2.Moreprecisely,wewilusethefol-lowing encoding of four physical qubits into one logicalqu bit:|0〉 = |0〉|0〉|0〉|0〉|1〉 = |1〉|1〉|1〉|1〉 .(61)Th e single–qubit identity I1is achieved by (c, d)=(1 , 0) (see Fig. 8a) .Ga tes Rz(ξ)areobtainedbylettingthelogicalqubitinteract with a neighboring, auxilia ry plaquette whichha s all remaining qubi ts fix ed to |0〉,andsetting(c, d)=(1 ,eiξ)(seeFig.8b). This acts effect ively as a single–pa rticle interaction for the logical pa rticle.|0〉|0〉|0〉(1 , 0)(1 ,eiξ)|ψ〉|ψ〉(1 ,i)|ψ1〉|ψ2〉|0〉 |0〉(a)(b )(c)FI G. 8: The physica l qubits co mposing the logica l qubit arema rked with thick, black lines, and qubits fixed by the gaugesy mmetry are depicted in gray. The pair of numbers asso ci-at ed to each gat e ar e (c, d), which determine it. (a) The logicalsingle–qubit identity I1is obtained by setting (c, d)= (1, 0) inth e plaquette formed by th e four physical qubits th at composeth e logical qubit. (b ) The logical rotation around th e z–ax is,Rz(ξ)isobtainedbylettingthelogicalqubitinteractwithanau xiliar y plaq uette whose spins ar e all fixed to |0〉,andset-ting (c, d)= (1,eiξ)inthisauxiliary plaquette. (c)Theonlyno n– local pa rt of CZ ,diag(1,i,i,1) , is implemented by let-ting th e two logical qubits interact via an auxiliary plaquettewi th (c, d)= (1,i).Th e implementation of the logical Hadamard gate H(see Fig. 9)isinspiredin theideaofteleportation. Inpa rticular, we want to appl y H to the logical qubit onthe left of Fig. 9.Tothisend,wepreparethetwologicalqu bits on its right in the state |0+ 〉 + |1−〉,where|±〉 = |0〉 ±|1〉 , (62)by analogy of the conv ent ional definitions with phy sicalqu bits |±〉 = |0〉 ±|1〉.ThenweapplyaprojectionontoaBellstate|00〉 + |11〉 between the qubit we want toteleport and the first of these two logical qubits. Moreprecisely, the three logical qubi ts are initially in the state|ψ〉|0〉|0〉, and they are transformed wi th the followi nggat es (depicted in Fig. 9):1. Single qubit gat es with (c, d)= (1, 1) to all physicalqu bits of the two logical qu bits on the right, whichyields the state |ψ〉| ++++ 〉⊗2,2. The fou r–q ubit gat e (c, d)= (1, 0) on the secon dan d third logi cal qubits, an d the fou r–q ubit gat es(c, d)= (1, 1) to all their surrou nding plaq uettes,wh ich results in the state |ψ〉|e4〉⊗2,where|e4〉 isan equal superp osition of all even states of 4 qubits,|e4〉≡ |0000 〉 + |0011 〉 + ... + |1100 〉 + |1111 〉.3. The fou r–q ubit gat es with (c, d)= (1, 0) to the sur-rou ndings of the two logi cal qubits on the right,wh ich results in the state |ψ〉(|0000 〉 + |0011 〉 +|1100 〉 + |1111 〉)⊗2.4. The fou r–q ubit gat es with (c, d)= (1, 0) betweenthe second and third physical qubits of the last twological qubits, which results in the state |ψ〉|+〉⊗25. The gat e CZ on the last two logi cal qubits, whichyields the state |ψ〉(|0+ 〉 + |1−〉).6. A fou r–q ubit gat e with (c, d)= (1, 0) betweenthe first and the second logical qubit (w hich cor-respon ds to the Bell measurement), an d an otherfour–qubit gate with (c, d)= (1, 0) between the firstan d the secon d logi cal qubit, which yields the stateH |ψ〉 on the third logi cal qubit, as desired.Th is shows that we can now perform a general singlequ bit unitary U ,sincethiscanbeexpressedinitsEulerde compositionU (α, β, γ)= Rz(α)HRz(β)HRz(γ) . (63)To generate the logical controlled phase gate CZ wede compose it into Rzrot ation s an d a non –local gat e:CZ = R(1 )z(−pi2)R(2 )z(−pi2)diag(1,i,i,1) . (64)Th e last gate is implemented by letting the last twological qubits interact via an auxilia ry plaquette with(c, d)= (1,i)(seeFig.8c).Finally, we distribute the logical qubits in the 3D lat-tice as sketched in Fig. 10.Weconsiderthatthever-tical and the horizontal directions are the spatial ones,an d that time increases in the direction goi ng from pap erto the reader. Then the logical qubits are initially dis-tributed in a 1D vertical array, situated on the left, rearpa rt of the circuit. Sing le qubi t gates move the logicalqu bits in the time direction, while Hadamard gates movethem to the right. At the end of the circuit, the logicalqu bits are situated in a 1D array at the right, front partof the circuit.We would like to m ake som e com m ents concerning ofthis construction. First, the realization of I1requires firstarescalingoftheenergyto(cprime,dprime)= 1,e−2βJ.Then,oneha s to let J →∞ .Co mment on this.13No te th at th is is a continuous universal gate set Wo lf-gan g, is this a prob lem or an ad van tage ?.Notethatthisset includes the single–qubit identity I1,andthetwo–qu bit identity I2.Moreprecisely,wewilusethefol-lowing encoding of four physical qubits into one logicalqu bit:|0〉 = |0〉|0〉|0〉|0〉|1〉 = |1〉|1〉|1〉|1〉 .(6 1)Th e single–qubit identity I1is achieved by (c, d)=(1 , 0) (see Fig. 8a) .Ga tes Rz(ξ)areobtainedby letting elogicalqubitinteract with a neighboring, auxilia ry plaquette whichha s all remaining qubi ts fix ed to |0〉,andsetting(c, d)=(1 ,eiξ)(seeFig.8b) . This acts effect ively as a single–pa rticle interaction for the logical pa rticle.|0〉|0〉|0〉(1 , 0)(1 ,eiξ)|ψ 〉|ψ 〉(1 ,i)|ψ1〉|ψ2〉|0〉 |0〉(a )(b )(c)FI G. 8: The physica l qubits co mposing the logica l qubit arema rked with thick, black lines, and qubits fixed by th gaugesy m m etry are depicted in gray. The pair of numbers asso ci-at ed to each gat e ar e (c, d), which determine it. (a ) The logicalsingle–qubit identity I1is obtain ed by settin g (c, d)= (1, 0) inth e plaquette formed by th e four physical qubits th at composeth e logical qubit. (b ) The logical rota tion around th e z–ax is,Rz(ξ)isobtained bylet ingthelogicalqubitinteractwith anau xiliar y plaq uette whos e spins ar e all fixed to |0〉,andset-ting (c, d)= (1,eiξ)in thisauxiliary plaquette. (c)Theonlyno n– local pa rt of CZ ,d ag(1,i,i,1) , is im plem ented by let-ting th e two logical qubits interact via an auxiliary plaquettewi th (c, d)= (1,i).Th e implementation of the logical Hadamard gate H(see Fig. 9)isinspired in theideaofteleportation. Inpa rticular, we want to appl y H to th e logical qubit onth e left of Fig. 9.Tothisend,wepreparethetwologicalqu bits on its right in the state |0+ 〉 + |1−〉,where|±〉 = |0〉 ±|1〉 , (6 2)by analogy of the conv ent ional definitions with phy sicalqu bits |±〉 = |0〉 ±|1〉.ThenweapplyaprojetionontoaBellstate|00〉 + |11〉 be tween the qubit we want toteleport and th e first of th ese two logical qubits. M orepr ecisely, the thr ee logical qubi ts are initially in the state|ψ〉|0〉|0〉, and they are transformed wi th he followi nggat s (depicted in Fig. 9):1. Single qubit gat es with (c, d)= (1, 1) to all physicalqu bits of the two logical qu bits on the right, whichyields the state |ψ〉| ++++ 〉⊗2,2. The fou r–q ubit gat e (c, d)= (1, 0) on the secon dan d third logi cal qubits, an d the fou r–q ubit gat es(c, d)= (1, 1) to all their surrou nding plaq uettes,wh ich results in the state |ψ〉|e4〉⊗2,where|e4〉 isan equal superp osition of all even states of 4 qubits,|e4〉≡ |0000 〉 + |0011 〉 + ... + |1100 〉 + |1111 〉.3. The fou r–q ubit gat es with (c, d)= (1, 0) to the sur-rou ndings of the two logi cal qubits on the righ t,wh ich results in the state |ψ〉(|0000 〉 + |0011 〉 +|1100 〉 + |1111 〉)⊗2.4. The fou r–q ubit gat es with (c, d)= (1, 0) betweenth e second and th ird physical qubits of th e last twological qubits, which results in the state |ψ〉|+〉⊗25. The gat e CZ on the last two logi cal qubits, whichyields the state |ψ〉(|0+ 〉 + |1−〉).6. A fou r–q ubit gat e with (c, d)= (1, 0) betweenth e first and th e second logical qubit (w hich cor-respon ds to the Bell measurement), an d an otherfour–qubit gate with (c, d)= (1, 0) between the firstan d the secon d logi cal qubit, which yields the stateH |ψ〉 on the third logi cal qubit, as desired.Th is shows that we can now perform a general singlequ bit unitary U ,sincethiscan beexpressedin itsEulerde compositionU (α, β, γ)= Rz(α)HRz(β)HRz(γ) . (6 3)To generate the logical controlled phase gate CZ wede compose it into Rzrot ation s an d a non –local gat e:CZ = R(1 )z(−pi2)R(2 )z(−pi2)diag(1,i,i,1) . (6 4)Th e last gate is implemented by letting the last twological qubits interact via an auxilia ry plaquette with(c, d)= (1,i)(seeFig.8c).Fi nally, we distribute the logical qubits in the 3D lat-tice s sketched in Fig. 10 .Weconsiderthatthever-tical and th e horizonta l directions are th e spatial ones,an d that time increases in the direction goi ng from pap erto th e reader. Then th e logical qubits are initially dis-tributed in a 1D vertical array, situ ated on th e left, rearpa rt of the circuit. Sing le qubi t gates move the logicalqu bits in the time direction, while Hadamard gates moveth em to right. At th e end of th e circuit, th e logicalqu bits are situated in a 1D array at the right, front partof the circuit.We would like to m ake som e com m ents concerning ofth is construction. First, th e realization of I1requires firstarescalingofthe nergyto(cprime,dprime)= 1,e−2βJ.Then,oneha s to let J →∞ .Co mment on this.13Note that this is a continuous universal gate set Wo lf-gan g, is this a prob lem or an advantage ?.Notethatthisset includes the single–qubit identity I1,andthetwo–qubit identity I2.Moreprecisely,wewilusethefol-lowing encoding of four physical qubits into one logicalqubit:|0〉 = |0〉|0〉|0〉|0〉|1〉 = |1〉|1〉|1〉|1〉.(61)The single–qubit identity I1is achieved by (c, d)=(1, 0) (see Fig. 8a) .Gates Rz(ξ)areobtainedbylettingthelogicalqubitinteract with a neighboring, auxiliary plaquette whichhas all remaining qubi ts fixed to |0〉,andsetting(c, d)=(1,eiξ)(seeFig.8b). This acts effectively as a single–particle interaction for the logical particle.|0〉|0〉|0〉(1, 0)(1,eiξ)|ψ〉|ψ〉(1,i)|ψ1〉|ψ2〉|0〉 |0〉(a)(b)(c)FIG. 8: The physical qubits composing the logical qubit arema rked with thick, black lines, and qubits fixed by the gaugesymmetry are depicted in gray. The pair of numbers asso ci-ated to each gat e are (c, d), which determine it. (a) The logicalsingle–qubit identity I1is obtained by setting (c, d)= (1, 0) inthe plaquette formed by the four physical qubits that composethe logical qubit. (b) The logical rotation around the z–ax is,Rz(ξ)isobtainedbylettingthelogicalqubitinteractwithanauxiliary plaquette whose spins are all fixed to |0〉,andset-ting (c, d)= (1,eiξ)inthisauxiliaryplaquette. (c)Theonlynon–local part of CZ ,diag(1,i,i,1), is implemented by let-ting the two logical qubits interact via an auxiliary plaquettewith (c, d)= (1,i).The implementation of the logical Hadamard gate H(see Fig. 9)isinspiredintheideaofteleportation. Inparticular, we want to appl y H to the logical qubit onthe left of Fig. 9.Tothisend,wepreparethetwologicalqubits on its right in the state |0+〉 + |1−〉,where|±〉 = |0〉 ±|1〉, (62)by analogy of the conventional definitions with physicalqubits |±〉 = |0〉 ±|1〉.ThenweapplyaprojectionontoaBellstate|00〉 + |11〉 between the qubit we want toteleport and the first of these two logical qubits. Moreprecisely, the three logical qubi ts are initially in the state|ψ〉|0〉|0〉, and they are transformed with the followinggates (depicted in Fig. 9):1. Single qubit gates with (c, d)= (1, 1) to all physicalqubits of the two logical qubits on the right, whichyields the state |ψ〉| ++++ 〉⊗2,2. The four–q ubit gate (c, d)= (1, 0) on the secondand third logical qubits, and the four–q ubit gates(c, d)= (1, 1) to all their surrou nding plaquettes,which results in the state |ψ〉|e4〉⊗2,where|e4〉 isan equal superposition of all even states of 4 qubits,|e4〉≡|0000 〉+ |0011 〉+ ... + |1100 〉+ |1111 〉.3. The four–q ubit gates with (c, d)= (1, 0) to the sur-rou ndings of the two logical qubits on the right,which results in the state |ψ〉(|0000 〉 + |0011 〉 +|1100 〉+ |1111 〉)⊗2.4. The four–q ubit gates with (c, d)= (1, 0) betweenthe second and third physical qubits of the last twological qubits, which results in the state |ψ〉|+〉⊗25. The gate CZ on the last two logical qubits, whichyields the state |ψ〉(|0+〉 + |1−〉).6. A four–q ubit gate with (c, d)= (1, 0) betweenthe first and the second logical qubit (which cor-responds to the Bell measurement), and anotherfour–qubit gate with (c, d)= (1, 0) between the firstand the second logical qubit, which yields the stateH|ψ〉 on the third logical qubit, as desired.This shows that we can now perform a general singlequbit unitary U ,sincethiscanbeexpressedinitsEulerdecompositionU(α, β, γ)=Rz(α)HRz(β)HRz(γ) . (63)To generate the logical controlled phase gate CZ wedecompose it into Rzrotations and a non–local gate:CZ = R(1)z(−pi2)R(2)z(−pi2)diag(1,i,i,1) . (64)The last gate is implemented by letting the last twological qubits interact via an auxiliary plaquette with(c, d)= (1,i)(seeFig.8c).Finally, we distribute the logical qubits in the 3D lat-tice as sketched in Fig. 10.Weconsiderthatthever-tical and the horizontal directions are the spatial ones,and that time increases in the direction going from paperto the reader. Then the logical qubits are initially dis-tributed in a 1D vertical array, situated on the left, rearpart of the circuit. Single qubi t gates move the logicalqubits in the time direction, while Hadamard gates movethem to the right. At the end of the circuit, the logicalqubits are situated in a 1D array at the right, front partof the circuit.We would like to make some comments concerning ofthis construction. First, the realization of I1requires firstarescalingoftheenergyto(cprime,dprime)= 1,e−2βJ.Then,onehas to let J →∞.Comment on this.Single qubit identityZ-RotationControlled phase gateBQP-completeness resultsIIConstruct an (encoded) universal gate set:143334456(1,i)(1,ei(α+pi/2))|ψ〉|0〉|0〉(1, 1)(1, 1)(1, 0)(1, 0)(1, 0)(1, 0)(1, 0)(1, 0)(1,i)Rz(α)H |ψ〉timeFIG. 9: Teleportation–based logical Hadamard gate H:thestateofthefirstlogicalqubit|ψ〉 is transformed to H |ψ〉 on thethird logical qubit after the last step. See the main text for an explanation of every step. See the caption of Fig. 8 for anexplanation of the color and the pair of numbers associated toeachgate. Green faces mean (c, d)= (1, 1). Gray edges andcolored edges indicate edges fixed by the gauge, and the colored numbers indicated the time steps at which they are fixed, inaccordance with Fig. 10.Second, we remark that we most of these gates corre-spond require to fix complex parameters; more precisely,βJ = iξ for Rz(ξ)(65)βJ =0,∞ for H (66)βJ = −ipi/4forσz⊗ σz(67)Also need -IAlso (c,d)=(0,1)Ha damard gate requires complex parameters (becauseof the CZLgat e). Note also that the logi cal qubit isprocessed ahead in time and moves in space. This turnsout to be convenient in ord er to avoid the form ation ofloops.Th ird, constraints in the parameter regime and in thedistribut ion of the coupl ings (due to the encoding).Ge mma write this paragraph Thus, this shows thatcomputing the partition function of the 3D Z2LG T is anon–trivial problem (??). Because the 2D Z2LG T canbe mapped to a 1D Ising model via a duality transfor-ma tion [3], its complexity is also in P ??.The3DZ2LG T can be mapped via a duality transformation to the3D Ising model [3], do es that imply something for thecomplexity of the latter?(inaveryspecificparameterregime). On the other hand, recently it was found thatthe computing the partition function of the 4D Z2LG Tin a real parameter regime is NP–com plete [15, 16].VI. FURTHER RESULTSA. One clean qubit and periodic boundaryconditionsHere we mention a connection between the results ob-tained on the Ising model in Sec. VB and a schemefor quantum computation called the ‘one clean qubitmo del’. In the latter, one considers a quantum comp uta-tion where all qubits but the first one are initialized in thetotally mixed state (and the first qubit is, say, in the state|0〉). To this initial state, an arbitrary poly–size quantumcircuit may be applied, followed by a single–qubit mea-surement in the final stage of the computation. Th is one-clean-qubit model comprises a schem e that is believedto be weaker than the full power of quantum computersbut stronger than classical comput ation (although theseare unproved assertions). The corre sponding com plexityclass of decision problem s that can be solved efficientlywith the one-clean-qubit scheme is called DQC1 .Astandardproblemthatcanbesolvedusingonecleanqubit is the problem of estimating normalized tracesof unitary qantum circuits. Let U denote a poly–sizen–qubit quantum circuit com posed of, say, two–q ubitgat es. Then there exists an efficient quantum algorithmwithin the one-clean-qubit scheme wh ich returns a num-ber c that provides (with exponentially small probabilityof failure) an epsilon1-approximation of the normalized trace2−nTr (U )inpoly(n)time,foreveryepsilon1 that scales at mostHadamard gate:Note: many spins fixed by the gaugeBQP-completeness resultsII 3D LGTZ2Verify that there are no loops of spins fixed by the gauge:1512345678910111213123 34456 78334 459 10111213112334 45678 334 459 101112131333Rz(α +pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Tw o–qubit gateTw o–qubit gate Sing le–qubi t gateall time stepseiϕσz⊗σzeiϕσz⊗σzFI G. 10: A project ion of the circu it of the 3D Z2LG T into its spatial dime nsion. The figure shows the part of thecircuitwi th a two–qubit gate, a totally general single qubit rotation , an d an ot her two–q ubit gat e. Logi cal qubits ar e indicat edwitha thick black line. All edges in the time direction (going out of the pap er) which ar e bou ndar y to a logi cal qubit ar e fixed byth e gauge (p ink dots). Edges in th e spatial direction are eithe r no t fix ed by the gaug e (black, thin line s), or are fix ed by thegau ge in differen t tim e step s 1,. . . , 13, indicat ed with a color for each time step. Hence, a loop of edges fixed by the gaugeco rresponds in this figure to a loop of co lored ed ges.inverse polynomially with n.Thetechniqueisasimpleva riant of the Hadam ard test and we refer to the liter-ature. More over, the prob lem of estimating norm alizedtraces of unitary quantu m circuits is known to be DQC1–ha rd. In othe r words , this pr oblem captur es all pr oblemsth at can be solved efficiently within the one-clea n-qubitpa radigm. It thus plays a similar role as the uni tary ma-trix element problem for BQ P.Ou r results obtained in Sec. VB im mediately lead toacompleteproblem forDQC1involvingIsingpartitionfunctions defined on graphs with pe riod ic boundary con-dit ion s.Welimitourselvestoasketchoftheargument.It follows from the discussion in Sec. VB th at, for everypo ly–size quantum circuit U th ere exists an Ising modelde fine d on a plana r circuit graph G (w hich can be foundefficiently), with co uplings and tem perature as in Theo -rem 4 an d with free bou ndary con dition s, such that Z /γpr ovide s a 1/poly appr oximation of the matrix element〈+|⊗nU |+〉⊗n.Now,insteadof|+〉⊗nwe consider thema trix eleme nt 〈s|U |s〉 wh ere |s〉 = |s1...sn〉 representsan arb itrary com putation al basis state. This matrix el-em ent now co incides with Zs/γ,whereZsde no tes thepa rtition func tion of the same mode l (i.e. same graph,co uplings and tem perature), however co nsidering bound-ary con dition s where the left an d right bou ndary spinsare fixed in the sam e con figu rat ion s.Suchasituationis equivalent to considering a graph Gprimewh ere each leftbo undary spin at the k-th ‘row’ in the graph is ide ntifi edwi th its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Onethusarri ves at an Ising model on a new grap h Gprimewh ich isob tained from G by enforcing pe riod ic boundary condi-tions,andwhereoneverticalsliceofspinsisfixedintheco nfiguration s.Finally,considerthenormalizedtraceofth e matrix element U ,givenby2−nsummationtexts〈s|U |s〉.Duetoth e above discussion, th is normalized trace may hence beap proximated with 1/p oly accurac y by12nγsummationdisplaysZs. (68)Bu t as Zsis the partition function on Gprimewi th one ver-tical slice of spins fixed in th e configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewh ere these spins are now fully summed out. Th equ antity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with cou plings an d tempera-tu re as before, and with out any fixed spins or boundaryco nditions.We thus arrive at the follow ing result: consider anyplana r circuit graph G.Lett de no te the num ber of ho ri-zo ntal ed ges in G an d let n be its vertical dimension. LetGprimebe the graph obtained by enforcing pe riodic bo undaryco nditions on G (as above). Consider a classical Isingmo del at inverse temp erature β de fine d on G,whereon each site a con stant (com plex) magn etic field haispr esent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.1512345678910111213123 34 456 78334 459 10111213112334 45678 334 459 101112131333Rz(α+pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Two–qubit gateTwo–qubit gate Single–qubit gateall time stepseiϕσz⊗σzeiϕσz⊗σzFIG. 10: A projection of the circuit of the 3D Z2LGT into its spatial dimension. The figure shows the part of thecircuitwith a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicatedwitha thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed bythe gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by thegauge in different time steps 1,..., 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gaugecorresponds in this figure to a loop of colored edges.inverse polynomially with n.Thetechniqueisasimplevariant of the Hadamard test and we refer to the liter-ature. Moreover, the problem of estimating normalizedtraces of unitary quantum circuits is known to be DQC1–hard. In other words, this problem captures all problemsthat can be solved efficiently within the one-clean-qubitparadigm. It thus plays a similar role as the unitary ma-trix element problem for BQP.Our results obtained in Sec. VB immediately lead toacompleteproblemforDQC1involvingIsingpartitionfunctions defined on graphs with periodic boundary con-ditions.Welimitourselvestoasketchoftheargument.It follows from the discussion in Sec. VBthat, for everypoly–size quantum circuit U there exists an Ising modeldefined on a planar circuit graph G (which can be foundefficiently), with couplings and temperature as in Theo-rem 4 and with free boundary conditions, such that Z/γprovides a 1/poly approximation of the matrix element〈+|⊗nU|+〉⊗n.Now,insteadof|+〉⊗nwe consider thematrix element 〈s|U|s〉 where |s〉 = |s1...sn〉 representsan arbitrary computational basis state. This matrix el-ement now coincides with Zs/γ,whereZsdenotes thepartition function of the same model (i.e. same graph,couplings and temperature), however considering bound-ary conditions where the left and right boundary spinsare fixed in the same configuration s.Suchasituationis equivalent to considering a graph Gprimewhere each leftboundary spin at the k-th ‘row’ in the graph is identifiedwith its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Onethusarrives at an Ising model on a new graph Gprimewhich isobtained from G by enforcing periodic boundary condi-tions,andwhereoneverticalsliceofspinsisfixedintheconfiguration s.Finally,considerthenormalizedtraceofthe matrix element U,givenby2−nsummationtexts〈s|U|s〉.Duetothe above discussion, this normalized trace may hence beapproximated with 1/poly accuracy by12nγsummationdisplaysZs. (68)But as Zsis the partition function on Gprimewith one ver-tical slice of spins fixed in the configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewhere these spins are now fully summed out. Thequantity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with couplings and tempera-ture as before, and without any fixed spins or boundaryconditions.We thus arrive at the following result: consider anyplanar circuit graph G.Lett denote the number of hori-zontal edges in G and let n be its vertical dimension. LetGprimebe the graph obtained by enforcing periodic boundaryconditions on G (as above). Consider a classical Isingmodel at inverse temperature β defined on G,whereon each site a constant (complex) magnetic field haispresent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.1512345678910111213123 3456 7833459 10111213112334 45678 334 459 101112131333Rz(α+pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Two–qubit gateTwo–qubit gate Single–qubit gateall time stepseiϕσz⊗σzeiϕσz⊗σzFIG. 10: A projectio of the circuit of the 3D Z2LGT into its spatial dimension. The figure shows the part of thecircuitwith a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicatedwitha thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed bythe gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin l nes), or r fixed by thegauge in different time steps 1,..., 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gaugecorresponds in this figure to a loop of colored edges.inverse polynomially with n.Thetechniqueisasimplevariant of the Hadamard test and we refer to the liter-ature. Moreover, the problem of estimating normalizedtraces of unitary quantum circuits is known to be DQC1–hard. In other words, this problem captures all problemsthat can be solved efficiently within the one-clean-qubitparadigm. It thus plays a similar role as the unitary ma-trix element problem for BQP.Our results obtained in Sec. VB immediately lead toacompleteproblemforDQC1involvingIsingpartitionfunctions defined on graphs with periodic boundary con-ditions.Weli itourselvestoasketchoftheargument.It follows from the discussion in Sec. VBthat, for everypoly–size quantum circuit U there exists an Ising modeldefined on a planar circuit graph G (which can be foundefficiently), with couplings and temperature as in Theo-rem 4 and with free boundary conditions, such that Z/γprovides a 1/poly approximation of the matrix element〈+|⊗nU|+〉⊗n.Now,isteadof|+〉⊗nwe consider thematrix element 〈s|U|s〉 where |s〉 = |s1...sn〉 representsan arbitrary computational basis state. This matrix el-ement now coincides with Zs/γ,whereZsdenotes thepartition function of the same model (i.e. same graph,couplings and temperature), however considering bound-ary conditions where the left and right boundary spinsare fixed in the same configuration s.Suchasituationis equivalent to considering a graph Gprimewhere each leftboundary spin at the k-th ‘row’ in the graph is identifiedwith its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Onethusarrives at an Ising model on a new graph Gprimewhich isobtained from G by enforcing periodic boundary condi-tions,andwhereoneverticalsliceofspinsisfixedintheconfiguration s.Finally,considerthenormalizedtraceofthe matrix element U,givenby2−nsummationtexts〈s|U|s〉.Duetothe above discussion, this normalized trace may hence beapproximated with 1/poly accuracy by12nγsummationdisplaysZs. (68)But as Zsis the partition function on Gprimewith one ver-tical slice of spins fixed in the configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewhere these spins are now fully summed out. Thequantity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with couplings and tempera-ture as before, and without any fixed spins or boundaryconditions.We thus arrive at the following result: consider anyplanar circuit graph G.Lett denote the number of hori-zontal edges in G and let n be its vertical dimension. LetGprimebe the graph obtained by enforcing periodic boundaryconditions on G (as above). Consider a classical Isingmodel at inverse temperature β defined on G,whereon each site a constant (complex) magnetic field haispresent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.1512345678910111213123 34 456 78334 459 10111213112334 45678 334 459 101112131333Rz(α+pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Two–qubit gateTwo–qubit gate Single–qubit gateall time stepseiϕσz⊗σzeiϕσz⊗σzFIG. 10: A projecti of the circuit of the 3D Z2LGT into its spatial dimension. The figure shows the part of thecircuitwith a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicatedwitha thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed bythe gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by thegauge in different time steps 1,..., 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gaugecorresponds in this figure to a loop of colored edges.inverse polynomially with n.Thtechniqueisasimplevariant of the Hadamard tes a d we r fer to the liter-ature. Moreover, the problem of estimating normalizedtraces of unitary quantum circuits is known to be DQC1–hard. In other words, this problem captures all problemsthat can be solved efficiently within the one-clean-qubitparadigm. It thus plays a similar role as the unitary ma-trix element problem for BQP.Our results obtained in Sec. VB immediately lead toacompleteproblemforDQC1involvingIsingpartitionfunctions defined on graphs with periodic boundary con-ditions.Welimitourselvsoasketchoftheargument.It follows from the discussion in Sec. VBthat, for everypoly–size quantum circuit U there exists an Ising modeldefined on a planar circuit graph G (which can be foundefficiently), with couplings and temperature as in Theo-rem 4 and with free boundary conditions, such that Z/γprovides a 1/poly approximation of the matrix element〈+|⊗nU|+〉⊗n.Now,insteadof|+〉⊗we consider thematrix element 〈s|U|s〉 where |s〉 = |s1...sn〉 representsan arbitrary computational basis state. This matrix el-ement now coincides with Zs/γ,whereZsdenotes thepartition function of the same model (i.e. same graph,couplings and temperature), however considering bound-ary conditions where the left and right boundary spinsare fixed in the same configuration s.Suchasituationis equivalent to considering a graph Gprimewhere each leftboundary spin at the k-th ‘row’ in the graph is identifiedwith its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Oethuarrives at an Ising model on a new graph Gprimewhich isobtained from G by enforcing periodic boundary condi-tions,andwher oneverticalsliceofspinsisfixedintheconfiguratio s.Finally,considerthenormaliz traceofthe matrix el ment U,givenby2−nsummationtexts〈s|U|s〉.Dueothe bove discussion, this normalized trace may hence beapproximated with 1/poly accuracy by12nγsummationdisplaysZs. (68)But as Zsis the partition function on Gprimewith one ver-tical slice of spins fixed in the configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewhere these spins are now fully summed out. Thequantity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with couplings and tempera-ture as before, and without any fixed spins or boundaryconditions.We thus arrive at the following result: consider anyplanar circuit graph G.Lett denote the number of hori-zontal edges in G and let n be its vertical dimension. LetGprimebe the graph obtained by enforcing periodic boundaryconditions on G (as above). Consider a classical Isingmodel at inverse temperature β defined on G,whereon each site a constant (complex) magnetic field haispresent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.BQP-completeness resultsII 3D LGTZ2Verify that there are no loops of spins fixed by the gauge:Approximating the partition function of a 3D LGT on a certain complex parameter regime is BQP-completeZ21512345678910111213123 34456 78334 459 10111213112334 45678 334 459 101112131333Rz(α +pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Tw o–qubit gateTw o–qubit gate Sing le–qubi t gateall time stepseiϕσz⊗σzeiϕσz⊗σzFI G. 10: A project ion of the circu it of the 3D Z2LG T into its spatial dime nsion. The figure shows the part of thecircuitwi th a two–qubit gate, a totally general single qubit rotation , an d an ot her two–q ubit gat e. Logi cal qubits ar e indicat edwitha thick black line. All edges in the time direction (going out of the pap er) which ar e bou ndar y to a logi cal qubit ar e fixed byth e gauge (p ink dots). Edges in th e spatial direction are eithe r no t fix ed by the gaug e (black, thin line s), or are fix ed by thegau ge in differen t tim e step s 1,. . . , 13, indicat ed with a color for each time step. Hence, a loop of edges fixed by the gaugeco rresponds in this figure to a loop of co lored ed ges.inverse polynomially with n.Thetechniqueisasimpleva riant of the Hadam ard test and we refer to the liter-ature. More over, the prob lem of estimating norm alizedtraces of unitary quantu m circuits is known to be DQC1–ha rd. In othe r words , this pr oblem captur es all pr oblemsth at can be solved efficiently within the one-clea n-qubitpa radigm. It thus plays a similar role as the uni tary ma-trix element problem for BQ P.Ou r results obtained in Sec. VB im mediately lead toacompleteproblem forDQC1involvingIsingpartitionfunctions defined on graphs with pe riod ic boundary con-dit ion s.Welimitourselvestoasketchoftheargument.It follows from the discussion in Sec. VB th at, for everypo ly–size quantum circuit U th ere exists an Ising modelde fine d on a plana r circuit graph G (w hich can be foundefficiently), with co uplings and tem perature as in Theo -rem 4 an d with free bou ndary con dition s, such that Z /γpr ovide s a 1/poly appr oximation of the matrix element〈+|⊗nU |+〉⊗n.Now,insteadof|+〉⊗nwe consider thema trix eleme nt 〈s|U |s〉 wh ere |s〉 = |s1...sn〉 representsan arb itrary com putation al basis state. This matrix el-em ent now co incides with Zs/γ,whereZsde no tes thepa rtition func tion of the same mode l (i.e. same graph,co uplings and tem perature), however co nsidering bound-ary con dition s where the left an d right bou ndary spinsare fixed in the sam e con figu rat ion s.Suchasituationis equivalent to considering a graph Gprimewh ere each leftbo undary spin at the k-th ‘row’ in the graph is ide ntifi edwi th its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Onethusarri ves at an Ising model on a new grap h Gprimewh ich isob tained from G by enforcing pe riod ic boundary condi-tions,andwhereoneverticalsliceofspinsisfixedintheco nfiguration s.Finally,considerthenormalizedtraceofth e matrix element U ,givenby2−nsummationtexts〈s|U |s〉.Duetoth e above discussion, th is normalized trace may hence beap proximated with 1/p oly accurac y by12nγsummationdisplaysZs. (68)Bu t as Zsis the partition function on Gprimewi th one ver-tical slice of spins fixed in th e configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewh ere these spins are now fully summed out. Th equ antity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with cou plings an d tempera-tu re as before, and with out any fixed spins or boundaryco nditions.We thus arrive at the follow ing result: consider anyplana r circuit graph G.Lett de no te the num ber of ho ri-zo ntal ed ges in G an d let n be its vertical dimension. LetGprimebe the graph obtained by enforcing pe riodic bo undaryco nditions on G (as above). Consider a classical Isingmo del at inverse temp erature β de fine d on G,whereon each site a con stant (com plex) magn etic field haispr esent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.1512345678910111213123 34 456 78334 459 10111213112334 45678 334 459 101112131333Rz(α+pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Two–qubit gateTwo–qubit gate Single–qubit gateall time stepseiϕσz⊗σzeiϕσz⊗σzFIG. 10: A projection of the circuit of the 3D Z2LGT into its spatial dimension. The figure shows the part of thecircuitwith a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicatedwitha thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed bythe gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by thegauge in different time steps 1,..., 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gaugecorresponds in this figure to a loop of colored edges.inverse polynomially with n.Thetechniqueisasimplevariant of the Hadamard test and we refer to the liter-ature. Moreover, the problem of estimating normalizedtraces of unitary quantum circuits is known to be DQC1–hard. In other words, this problem captures all problemsthat can be solved efficiently within the one-clean-qubitparadigm. It thus plays a similar role as the unitary ma-trix element problem for BQP.Our results obtained in Sec. VB immediately lead toacompleteproblemforDQC1involvingIsingpartitionfunctions defined on graphs with periodic boundary con-ditions.Welimitourselvestoasketchoftheargument.It follows from the discussion in Sec. VBthat, for everypoly–size quantum circuit U there exists an Ising modeldefined on a planar circuit graph G (which can be foundefficiently), with couplings and temperature as in Theo-rem 4 and with free boundary conditions, such that Z/γprovides a 1/poly approximation of the matrix element〈+|⊗nU|+〉⊗n.Now,insteadof|+〉⊗nwe consider thematrix element 〈s|U|s〉 where |s〉 = |s1...sn〉 representsan arbitrary computational basis state. This matrix el-ement now coincides with Zs/γ,whereZsdenotes thepartition function of the same model (i.e. same graph,couplings and temperature), however considering bound-ary conditions where the left and right boundary spinsare fixed in the same configuration s.Suchasituationis equivalent to considering a graph Gprimewhere each leftboundary spin at the k-th ‘row’ in the graph is identifiedwith its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Onethusarrives at an Ising model on a new graph Gprimewhich isobtained from G by enforcing periodic boundary condi-tions,andwhereoneverticalsliceofspinsisfixedintheconfiguration s.Finally,considerthenormalizedtraceofthe matrix element U,givenby2−nsummationtexts〈s|U|s〉.Duetothe above discussion, this normalized trace may hence beapproximated with 1/poly accuracy by12nγsummationdisplaysZs. (68)But as Zsis the partition function on Gprimewith one ver-tical slice of spins fixed in the configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewhere these spins are now fully summed out. Thequantity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with couplings and tempera-ture as before, and without any fixed spins or boundaryconditions.We thus arrive at the following result: consider anyplanar circuit graph G.Lett denote the number of hori-zontal edges in G and let n be its vertical dimension. LetGprimebe the graph obtained by enforcing periodic boundaryconditions on G (as above). Consider a classical Isingmodel at inverse temperature β defined on G,whereon each site a constant (complex) magnetic field haispresent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.1512345678910111213123 3456 7833459 10111213112334 45678 334 459 101112131333Rz(α+pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Two–qubit gateTwo–qubit gate Single–qubit gateall time stepseiϕσz⊗σzeiϕσz⊗σzFIG. 10: A projectio of the circuit of the 3D Z2LGT into its spatial dimension. The figure shows the part of thecircuitwith a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicatedwitha thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed bythe gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin l nes), or r fixed by thegauge in different time steps 1,..., 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gaugecorresponds in this figure to a loop of colored edges.inverse polynomially with n.Thetechniqueisasimplevariant of the Hadamard test and we refer to the liter-ature. Moreover, the problem of estimating normalizedtraces of unitary quantum circuits is known to be DQC1–hard. In other words, this problem captures all problemsthat can be solved efficiently within the one-clean-qubitparadigm. It thus plays a similar role as the unitary ma-trix element problem for BQP.Our results obtained in Sec. VB immediately lead toacompleteproblemforDQC1involvingIsingpartitionfunctions defined on graphs with periodic boundary con-ditions.Weli itourselvestoasketchoftheargument.It follows from the discussion in Sec. VBthat, for everypoly–size quantum circuit U there exists an Ising modeldefined on a planar circuit graph G (which can be foundefficiently), with couplings and temperature as in Theo-rem 4 and with free boundary conditions, such that Z/γprovides a 1/poly approximation of the matrix element〈+|⊗nU|+〉⊗n.Now,isteadof|+〉⊗nwe consider thematrix element 〈s|U|s〉 where |s〉 = |s1...sn〉 representsan arbitrary computational basis state. This matrix el-ement now coincides with Zs/γ,whereZsdenotes thepartition function of the same model (i.e. same graph,couplings and temperature), however considering bound-ary conditions where the left and right boundary spinsare fixed in the same configuration s.Suchasituationis equivalent to considering a graph Gprimewhere each leftboundary spin at the k-th ‘row’ in the graph is identifiedwith its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Onethusarrives at an Ising model on a new graph Gprimewhich isobtained from G by enforcing periodic boundary condi-tions,andwhereoneverticalsliceofspinsisfixedintheconfiguration s.Finally,considerthenormalizedtraceofthe matrix element U,givenby2−nsummationtexts〈s|U|s〉.Duetothe above discussion, this normalized trace may hence beapproximated with 1/poly accuracy by12nγsummationdisplaysZs. (68)But as Zsis the partition function on Gprimewith one ver-tical slice of spins fixed in the configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewhere these spins are now fully summed out. Thequantity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with couplings and tempera-ture as before, and without any fixed spins or boundaryconditions.We thus arrive at the following result: consider anyplanar circuit graph G.Lett denote the number of hori-zontal edges in G and let n be its vertical dimension. LetGprimebe the graph obtained by enforcing periodic boundaryconditions on G (as above). Consider a classical Isingmodel at inverse temperature β defined on G,whereon each site a constant (complex) magnetic field haispresent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.1512345678910111213123 34 456 78334 459 10111213112334 45678 334 459 101112131333Rz(α+pi2)Rz(−pi2)HRz(−pi2)H Rz(β +pi2) Rz(γ)Two–qubit gateTwo–qubit gate Single–qubit gateall time stepseiϕσz⊗σzeiϕσz⊗σzFIG. 10: A projecti of the circuit of the 3D Z2LGT into its spatial dimension. The figure shows the part of thecircuitwith a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicatedwitha thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed bythe gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by thegauge in different time steps 1,..., 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gaugecorresponds in this figure to a loop of colored edges.inverse polynomially with n.Thtechniqueisasimplevariant of the Hadamard tes a d we r fer to the liter-ature. Moreover, the problem of estimating normalizedtraces of unitary quantum circuits is known to be DQC1–hard. In other words, this problem captures all problemsthat can be solved efficiently within the one-clean-qubitparadigm. It thus plays a similar role as the unitary ma-trix element problem for BQP.Our results obtained in Sec. VB immediately lead toacompleteproblemforDQC1involvingIsingpartitionfunctions defined on graphs with periodic boundary con-ditions.Welimitourselvsoasketchoftheargument.It follows from the discussion in Sec. VBthat, for everypoly–size quantum circuit U there exists an Ising modeldefined on a planar circuit graph G (which can be foundefficiently), with couplings and temperature as in Theo-rem 4 and with free boundary conditions, such that Z/γprovides a 1/poly approximation of the matrix element〈+|⊗nU|+〉⊗n.Now,insteadof|+〉⊗we consider thematrix element 〈s|U|s〉 where |s〉 = |s1...sn〉 representsan arbitrary computational basis state. This matrix el-ement now coincides with Zs/γ,whereZsdenotes thepartition function of the same model (i.e. same graph,couplings and temperature), however considering bound-ary conditions where the left and right boundary spinsare fixed in the same configuration s.Suchasituationis equivalent to considering a graph Gprimewhere each leftboundary spin at the k-th ‘row’ in the graph is identifiedwith its corresponding right boundary spin, and the re-sulting spin is fixed in the state sk,forallk.Oethuarrives at an Ising model on a new graph Gprimewhich isobtained from G by enforcing periodic boundary condi-tions,andwher oneverticalsliceofspinsisfixedintheconfiguratio s.Finally,considerthenormaliz traceofthe matrix el ment U,givenby2−nsummationtexts〈s|U|s〉.Dueothe bove discussion, this normalized trace may hence beapproximated with 1/poly accuracy by12nγsummationdisplaysZs. (68)But as Zsis the partition function on Gprimewith one ver-tical slice of spins fixed in the configuration x,thesumsummationtextsZs≡ Zprimesimply represents the partition function onGprimewhere these spins are now fully summed out. Thequantity Zprimeis hence the full-fledged partition functionon Gprimeof the Ising model with couplings and tempera-ture as before, and without any fixed spins or boundaryconditions.We thus arrive at the following result: consider anyplanar circuit graph G.Lett denote the number of hori-zontal edges in G and let n be its vertical dimension. LetGprimebe the graph obtained by enforcing periodic boundaryconditions on G (as above). Consider a classical Isingmodel at inverse temperature β defined on G,whereon each site a constant (complex) magnetic field haispresent satisfying eβha= i,andoneachedgeaconstant(complex) coupling Jeis present satisfying eβJe= eipi4.BQP-completeness resultsII 3D LGTZ2SummarySummary CompletenessZ=〈α|ψ〉 ComplexityZ=〈L|C|R〉✓ any dimensions✓ q-level systems, any q✓ any many-body int.realAbelian discreteZ4DZ2LGT(J,Jprime)= Zany classical spin model(J)Six vertex modelPotts model3D LGTZ2Approximating Z of is BQP-completein a certain complex parameter regimeThank you for your attention!GDlC, M. Van den Nest, W. Dür, H. J. Briegel, M.A. Martin-Delgado, Computational complexity of classical lattice models (in preparation)GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009)GDlC, W. Dür, H. J. Briegel, M. A. Martin-Delgado, Phys. Rev. Lett. 102, 230502 (2009)GDlC, W. Dür, H. J. Briegel, M. A. Martin-Delgado, New J. Phys. 12, 043014 (2010)M. Van den Nest, W. Dür, H. J. Briegel, Phys. Rev. Lett. 100, 110501(2008)M. Van den Nest, W. Dür, R. Raussendorf, H. J. Briegel, Phys. Rev. A 80, 052334 (2009)Y. Xu, GDlC, W. Dür, H. J. Briegel, M.A. Martin-Delgado, Completeness of a U(1) lattice gauge theory (in preparation)CompletenessComplexity********
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Unifying Classical Spin Models Using A Quantum Formalism
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Unifying Classical Spin Models Using A Quantum Formalism de las Cuevas, Gemma 2010-07-23
Page Metadata
Item Metadata
Title | Unifying Classical Spin Models Using A Quantum Formalism |
Creator |
de las Cuevas, Gemma |
Contributor | University of British Columbia. Department of Physics and Astronomy Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics Pacific Institute for the Mathematical Sciences |
Date Issued | 2010-07-23 |
Description | We have recently shown that the partition function of any classical spin model, including all discrete standard statistical models and all Abelian discrete lattice gauge theories, can be expressed as the specific instance of the partition function of a four dimensional Ising lattice gauge theory. This unifies models with apparently very different features (global vs. local symmetries, many body interactions, different dimensions, etc) in a single complete model. The proof of the result uses techniques from quantum information. In this talk we review these mappings and discuss recent developments, including quantum algorithms to approximate the partition function. |
Type |
Moving Image Other |
Language | eng |
Date Available | 2016-11-22 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0103171 |
URI | http://hdl.handle.net/2429/30936 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 59370-De_las_Cuevas_Vancouver-workshop.pdf [ 9.76MB ]
- 59370-WS Jul 23 de las Cuevas.mp4 [ 4MB ]
- Metadata
- JSON: 59370-1.0103171.json
- JSON-LD: 59370-1.0103171-ld.json
- RDF/XML (Pretty): 59370-1.0103171-rdf.xml
- RDF/JSON: 59370-1.0103171-rdf.json
- Turtle: 59370-1.0103171-turtle.txt
- N-Triples: 59370-1.0103171-rdf-ntriples.txt
- Original Record: 59370-1.0103171-source.json
- Full Text
- 59370-1.0103171-fulltext.txt
- Citation
- 59370-1.0103171.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103171/manifest