Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics

Unifying Classical Spin Models Using A Quantum Formalism de las Cuevas, Gemma 2010-07-23

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
De_las_Cuevas_Vancouver-workshop.pdf [ 9.76MB ]
[if-you-see-this-DO-NOT-CLICK]
[if-you-see-this-DO-NOT-CLICK]
WS Jul 23 de las Cuevas.mp4 [ 4MB ]
Metadata
JSON: 1.0103171.json
JSON-LD: 1.0103171+ld.json
RDF/XML (Pretty): 1.0103171.xml
RDF/JSON: 1.0103171+rdf.json
Turtle: 1.0103171+rdf-turtle.txt
N-Triples: 1.0103171+rdf-ntriples.txt
Original Record: 1.0103171 +original-record.json
Full Text
1.0103171.txt
Citation
1.0103171.ris

Full Text

Unifying classical spin models using a quantum formalism * Gemma De las Cuevas Ying Xu Wolfgang Dür Hans J. Briegel  @ Innsbruck  Maarten Van den Nest  @ MPQ Garching  Miguel Angel Martin-Delgado @ Madrid Vancouver, 23rd July 2010  Outline Motivation Completeness Complexity Summary  The 4D Z2 lattice gauge theory is complete  Approximating the partition function of some models is BQP-complete  Motivation  Motivation Classical spin models: Classical magnetism Spin glasses Neural networks Econophysics ...  Motivation Classical spin models:  Toy models to tackle complex systems  Classical magnetism Spin glasses Neural networks Econophysics ...  Make a simple microscopic model & study the macroscopic behavior  Motivation Many different kinds of classical spin models Different dimensions, defined on complicated graphs... Many-body interactions...=  Motivation Many different kinds of classical spin models Different dimensions, defined on complicated graphs... Many-body interactions...= Symmetries: Global: Ising, Potts ... H(s) = −J  si sj  Local: lattice gauge theories H(s) = −J (i,j,k,l)∈∂f  (i,j)∈E  global flip H(s)  =  si sj sk sl  v  local flip  v  H(s )  H(s)  =  H(s )  Motivation Can one relate all these models? By studying one model, can one learn something of other models?  Motivation Can one relate all these models? By studying one model, can one learn something of other models? Yes!  Completeness results:  Models with different features can be mapped onto a single model Use Quantum Information tools to relate them In equilibrium the crucial quantity: partition function Z =  e−βH(s) s  Completeness  Completeness A model is ‘complete’  Its partition function can specialize (by tuning its coupling strengths) to the partition function of any other classical spin model  M. Van den Nest, W. Dür, H. J. Briegel, Phys. Rev. Lett. 100, 110501(2008)  Completeness of the 2D Ising Result: Z2D Ising with h (J, J )  =  Zany classical spin model (J)  Completeness of classical spin models and universal quantum computation  Ising, Potts, ...  J  larger  J. Stat. Mech.  Figure 6. 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 by measuring all edge qubits VE (denoted by red dots) in the Y basis. Black dots denote vertex qubits.  re |0Y VE is a tensor product of the (+1)-eigenstate of Y on all edge qubits, and Σ the local Pauli operators appropriate for the corresponding measurement outcomes. To summarize, |C can be generated from |ϕ2D via equation (20), which shows that the universality of the cluster |ϕ2D is a universal resource state. Given M. Van den Nest, W. Dür,state, H. itJ.follows Briegel, t any state |ψ (in particular any |ϕG ) can be generated from |C via equation (19). ether, this implies that any state |ϕG can be generated from |ϕ2D by means of local surements (see figure 6).  ✓ on an arbitrary graph ✓ q-level systems, any q ✓ any many-body int.  Phys. Rev. Lett. 100, 110501(2008)  Completeness of the 2D Ising Result: Z2D Ising with h (J, J )  =  Zany classical spin model (J)  Completeness of classical spin models and universal quantum computation  Ising, Potts, ...  J complex larger  J. Stat. Mech.  Figure 6. 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 by measuring all edge qubits VE (denoted by red dots) in the Y basis. Black dots denote vertex qubits.  re |0Y VE is a tensor product of the (+1)-eigenstate of Y on all edge qubits, and Σ the local Pauli operators appropriate for the corresponding measurement outcomes. To summarize, |C can be generated from |ϕ2D via equation (20), which shows that the universality of the cluster |ϕ2D is a universal resource state. Given M. Van den Nest, W. Dür,state, H. itJ.follows Briegel, t any state |ψ (in particular any |ϕG ) can be generated from |C via equation (19). ether, this implies that any state |ϕG can be generated from |ϕ2D by means of local surements (see figure 6).  ✓ on an arbitrary graph ✓ q-level systems, any q ✓ any many-body int.  Phys. Rev. Lett. 100, 110501(2008)  Completeness with real coupl. Completeness of classical spin models and universal quantum computation  al rs ive qu an tu m m co pu ta n tio  . at St J.  M  01 70 P0 9) 00 (2 h. ec  GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009)  un  Analogous for q-level systems  d  23  an  J. Stat. M  We will first obtain a decorated 2D square lattice with crossings from a D square lattice. This procedure involves complex parameters. From ttice, we will obtain a decorated 3D square lattice, in a procedure ves only real parameters.  doi:10.1088/1742-5468/2009/07/P07001  23  larger  els  Figure 13. Measurement pattern for obtaining a plaquette with a decorated crossing starting from a 2D square lattice. It involves Y measurements, and hence it corresponds to complex parameters. The figure shows explicitly how the underlying graph changes with the measurements applied.  od  J real ✓  ZIsing, any G (J)  m  =  d te ra n d co a e de ts, th a en ow th em y h wi ur itl e as ic tt e pl ue m ex aq Y s pl es ow a lv sh . g vo re in in u ied in t fig pl ta I e ap ob ce. Th ts n i . r fo tt ers me a l n et ure er e tt ar ram as pa squ pa me t e en D lex h m a 2 p ht re om it su m c w ea fro to es M ng ds ang n h i . t o 1 13 ar sp h c t 00 e s rr rap re 07 g o gu in c g /P Fi oss e it ing 07 9/ cr nc rly 00 he de /2 un 68 54 274 /1 88 10 0. i:1 do  Z3D Ising (J, J )  Completeness of classical spin models and universal quantum computation  in sp  Ising model:  l ex ica rt ss ve d. cla n of ai ge s es rt er en ce m et pl er be m ov o Co e et lin av ay y h gr the ick t th tha A s . ize les ol ru mb ge sy er ) m een of w n et io b at in en ts at bi nc qu Co ge . ed 12 d re (an gu s Fi bit qu  Figure 12. Concatenation of merge rules. A thick gray line over certain vertex qubits (and edge qubits in between) symbolizes that they have to be merged.  J. Stat. Mech. (2009) P07001  Result:  Completeness with real coupl. Completeness of classical spin models and universal quantum computation  qu an tu m m co pu ta n tio  . at St J.  M  01 70 P0 9) 00 (2 h. ec  GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009)  al rs ive  Analogous for q-level systems  un  23  d  J. Stat. M  We will first obtain a decorated 2D square lattice with crossings from a D square lattice. This procedure involves complex parameters. From ttice, we will obtain a decorated 3D square lattice, in a procedure ves only real parameters.  doi:10.1088/1742-5468/2009/07/P07001  23  larger  an  Figure 13. Measurement pattern for obtaining a plaquette with a decorated crossing starting from a 2D square lattice. It involves Y measurements, and hence it corresponds to complex parameters. The figure shows explicitly how the underlying graph changes with the measurements applied.  els  J real ✓  ZIsing, any G (J)  od  =  d te ra n d co a e de ts, th a en ow th em y h wi ur itl e as ic tt e pl ue m ex aq Y s pl es ow a lv sh . g vo re in in u ied in t fig pl ta I e ap ob ce. Th ts n i . r fo tt ers me a l n et ure er e tt ar ram as pa squ pa me t e en D lex h m a 2 p ht re om it su m c w ea fro to es M ng ds ang n h i . t o 1 13 ar sp h c t 00 e s rr rap re 07 g o gu in c g /P Fi oss e it ing 07 9/ cr nc rly 00 he de /2 un 68 54 274 /1 88 10 0. i:1 do  Z3D Ising (J, J )  Completeness of classical spin models and universal quantum computation  m  same kind of interactions  in sp  Ising model:  l ex ica rt ss ve d. cla n of ai ge s es rt er en ce m et pl er be m ov o Co e et lin av ay y h gr the ick t th tha A s . ize les ol ru mb ge sy er ) m een of w n et io b at in en ts at bi nc qu Co ge . ed 12 d re (an gu s Fi bit qu  Figure 12. Concatenation of merge rules. A thick gray line over certain vertex qubits (and edge qubits in between) symbolizes that they have to be merged.  J. Stat. Mech. (2009) P07001  Result:  Completeness with real coupl. Completeness of classical spin models and universal quantum computation  qu  an  tu  m  m co  pu  ta  n tio  . at St J.  M  01 70 P0 9) 00 (2 h. ec  GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009)  al rs ive  Analogous for q-level systems  un  23  d  J. Stat. M  We will first obtain a decorated 2D square lattice with crossings from a D square lattice. This procedure involves complex parameters. From ttice, we will obtain a decorated 3D square lattice, in a procedure ves only real parameters.  doi:10.1088/1742-5468/2009/07/P07001  23  larger  an  Figure 13. Measurement pattern for obtaining a plaquette with a decorated crossing starting from a 2D square lattice. It involves Y measurements, and hence it corresponds to complex parameters. The figure shows explicitly how the underlying graph changes with the measurements applied.  els  J real ✓  ZIsing, any G (J)  od  =  d te ra n d co a e de ts, th a en ow th em y h wi ur itl e as ic tt e pl ue m ex aq Y s pl es ow a lv sh . g vo re in in u ied in t fig pl ta I e ap ob ce. Th ts n i . r fo tt ers me a l n et ure er e tt ar ram as pa squ pa me t e en D lex h m a 2 p ht re om it su m c w ea fro to es M ng ds ang n h i . t o 1 13 ar sp h c t 00 e s rr rap re 07 g o gu in c g /P Fi oss e it ing 07 9/ cr nc rly 00 he de /2 un 68 54 274 /1 88 10 0. i:1 do  Z3D Ising (J, J )  Completeness of classical spin models and universal quantum computation  m  same kind of interactions  in sp  Ising model:  l ex ica rt ss ve d. cla n of ai ge s es rt er en ce m et pl er be m ov o Co e et lin av ay y h gr the ick t th tha A s . ize les ol ru mb ge sy er ) m een of w n et io b at in en ts at bi nc qu Co ge . ed 12 d re (an gu s Fi bit qu  tradeoff between ‘completeness power’ and real parameters?  Figure 12. Concatenation of merge rules. A thick gray line over certain vertex qubits (and edge qubits in between) symbolizes that they have to be merged.  J. Stat. Mech. (2009) P07001  Result:  lattice gauge theory  Completeness of the 4D Z2 LGT Main result: constructive  Z4DZ2 LGT (J, J ) = Zany classical spin model (J) real  larger  Abelian discrete  ✓ any dimensions ✓ q-level systems, any q ✓ any many-body int.  global & local symmetries  GDlC, W. Dür, H. J. Briegel, M. A. Martin-Delgado, Phys. Rev. Lett. 102, 230502 (2009); New J. Phys. 12, 043014 (2010)  lattice gauge theory  Completeness of the 4D Z2 LGT Idea of the proof:  4D Z2 LGT real couplings J = 0, ∞  all k-cliques for k=1,...,n with Ising-type int.  Superclique  lattice gauge theory  Completeness of the 4D Z2 LGT Idea of the proof:  4D Z2 LGT real couplings J = 0, ∞  all k-cliques for k=1,...,n with Ising-type int.  Superclique  lattice gauge theory  Completeness of the 4D Z2 LGT Idea of the proof:  4D Z2 LGT real couplings J = 0, ∞  all k-cliques for k=1,...,n with Ising-type int.  Superclique  lattice gauge theory  Completeness of the 4D Z2 LGT Idea of the proof: J1 J14  J12 J1234  J123 J4  J2 J34  J124  J134 J23  J3  4D Z2 LGT real couplings J = 0, ∞  Superclique  lattice gauge theory  Completeness of the 4D Z2 LGT Idea of the proof: J1 J14  J12 J1234  J123 J4  J2 J34  J124  J134 J23  J3  4D Z2 LGT real couplings J = 0, ∞  Superclique  Any Abelian discrete classical spin model Hamiltonian!  lattice gauge theory  Completeness of the 4D Z2 LGT Idea of the proof:  non planar  } 4  23  ..  J1  ,. 1  Completeness of classical spin models and universal quantum computation  {J J12 } J1234 {J1, ..., J1234  J14  J123 J4  J2  Figure 14. We will first obtain a decorated 2D square lattice with crossings from a decorated 2D square lattice. This procedure involves complex parameters. From the latter lattice, we will obtain a decorated 3D square lattice, in a procedure 1 which involves only real parameters.  J124  J134  real couplings J = 0, ∞  {J  , ...,  J12  = 34 }  ...  J23  J3  4D Z2 LGT  q q q  Superclique  Potts... on high dim. any many-body int....  J. Stat. Mech. (2009) P07001  J34  1 ,J  Any Abelian discrete classical spin model  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 the boundaries so that only one decoration remains at each side.  Hamiltonian!  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 a 2D decorated square lattice. This involves creation of crossings, which correspond to complex parameters. Then, we generate a decorated 3D square lattice from the decorated 2D square lattice with crossings. This involves only merge and deletion rules, which correspond to real parameters (see figure 14). In order to generate a decorated 2D square lattice with crossings from a decorated 2D square lattice, we need to generate plaquettes with decorated crossings, and plaquettes without crossings. To obtain a plaquette with a crossing we proceed as in figure 13. To  Completeness of the 4D Z2 LGT Quantum formulation of Abelian discrete LGTs Hamiltonian  H(s) = −  Jf cos f ∈F  Partition function: ZG (J) =  2π (s1 + . . . + sk )modq q  e−βH(s)  |s  s  1  := |(sa + sb + sc + sd )mod q  1  a  d  1 c 4  b  2  v  3  FIG. 1: The state |ψLGT places one quantum parti dots, labeled with numbers) at each face, thereby cha ing the interaction of classical spins (black dots, labe  Completeness of the 4D Z2 LGT Quantum formulation of Abelian discrete LGTs Hamiltonian  H(s) = −  Jf cos f ∈F  Partition function: ZG (J) =  2π (s1 + . . . + sk )modq q  e−βH(s)  |s  s  1  := |(sa + sb + sc + sd )mod q  1  a  State defined on the faces: |ψG =  |(s1 + · · · + sk )modq s  d  f  1  f ∈F  Product state with coefficients: |α(J) =  |αf (Jf ) f  βJf cos[ 2π q (s1 +...+sk )]  |αf (Jf ) =  e  |s1 + ... + sk  c 4  b  2  v  3  f  se ∈∂f  FIG. 1: The state |ψLGT places one quantum parti dots, labeled with numbers) at each face, thereby cha ing the interaction of classical spins (black dots, labe  Completeness of the 4D Z2 LGT Quantum formulation of Abelian discrete LGTs Hamiltonian  H(s) = −  Jf cos f ∈F  Partition function: ZG (J) =  2π (s1 + . . . + sk )modq q  e−βH(s)  |s  s  1  := |(sa + sb + sc + sd )mod q  1  a  State defined on the faces: |ψG =  |(s1 + · · · + sk )modq s  d  f  1  f ∈F  Product state with coefficients: |α(J) =  |αf (Jf ) f  βJf cos[ 2π q (s1 +...+sk )]  |αf (Jf ) =  e  |s1 + ... + sk  c 4  b  2  v  3  f  se ∈∂f  1: The state |ψLGT places one quantum parti ZG (J) = α(J)|ψGFIG. dots, labeled with numbers) at each face, thereby cha  ing the interaction of classical spins (black dots, labe  a  oses the condition ( e∈∂f se )mod2 = 0 erms. Due to this condition, one of is not free anymore, but equals the k − 1 spins (since it is mod 2), say Fig. ??. This condition is substituted re sb participates, e.g. in Fig. ??, the h + sg + se + sb becomes sh + sg + se + this effectively enlarges the face, that ype interaction has become a 6–body on by means of the merge rule. Note g 6–body interaction has a coupling he face which has been enlarged (see  d  Jf = ∞  a b  d  2  b  2  Completeness of the 4D Z2 LGT =  c  j  Jcf ij  f  c  j  3  f  Jdabf ij  3  i  i  FIG. 4: Once set J = ∞ it is arbitrary to choose in what Tools to ‘transform’ thewemodel:  a d  g =  direction this face is merged. Here, sc is chosen to be the sa + fscis+merged sd dependent variable,sand downwards. b = thus h a a h  h  Merge rule: b  Jadcegh  c 4  f  g  d  e f  Deletion brule. This grule= is obtained by setting Jf = g0, d b Jbegh the interaction at face Jfadcegh Jf = is, ∞ by deleting that (Fig. ??). Note that this corresponds to projecting the face f onto c 0) = |+ e. c the state |+ =e|0 + |1 , i.e. |αf (Jf =  Deletion rule:  d  Jf = 0  b  Jbegh  h  a  h  a  3  g  = d  b  Jbegh  g  Setting Jf = ∞ sets the condition sa + nd thus, one of the variables becomes c e e c sa + sc + sd . This is substituted in the depends on sh +sg +se +sa +sc +sd , i.e. a FIG. 5: Deletion rule. Setting Jf = 0 deletes the interaction teraction, with the coupling strength of that face. egh (now Jabcegh ). Fixing the spinsinusing the gauge symmetry:  n of merge rules and the gauge fixing low us to achieve k–body Ising interFor example, in order to generate a  C.  Method to obtain general n−body interactions  No loops!  A three-body isofpropagation obtained byofbringing three Thispath includes all classical spin tive aaspin through a certain (the turntiveinteraction propagation a spin through certain path (the turnThisweproves tha This proves that can mo gen spins s1 , s2 , s3ings close to path each other and then merging the ings ofbe thedone pathsimilarly). can be done similarly). of the can arbitraryn-body dimensions d, between arbitrary g n-body interaction interaction n pa three-body interaction obtained by bringing three three-bodyinA interaction obtained byisbringing large blue face asAindicated Fig. 2(c). isThe interaction in three This includes all Thispattern. includesMoreover, all classical interaction byspin enc s1 ,tos2each , s3 close to other andticle thenin merging spins s1 , s2 , to sspins close other andeach then merging the arbitrary arbitrary dimensions d, dimensio arbitrar the blue face corresponds three-body Ising-type inter3 a dlogqe two-level particl mq ¼ the large blue face as indicated in Fig. 2(c). The interaction in large blue face as indicated in Fig. 2(c). The interaction in interaction interaction pattern. Moreover, by 0 action between s1 , s2 and s3 (since r1 and r2 are summed q-leve general interactions between n pattern face corresponds three-body interthe blue facetocorresponds toIsing-type a three-body Ising-type pa ticle interin mq ¼ dlogqe ticle intwo-level mq ¼ dlogq twice) and withtheanblue interaction strength Ja123 . n=m . This proves that the 4D Z LG 0 q2n action between s1 , s2between andcializes s3 (since rand r(since action s1to , sa2 general s3 n–body rinteraction. summed model (which we w Note that interactions here general 1 and 2 are summed 1 and r2q are general between interaction The generalization to k-body interactions with k ! 4 dependence on r1 .and r2 alsoAbelian since the large classical accordingspin to Eq. mo (?? discrete twice) and with an interaction strength J123 twice) and the with an interaction strength Jcancels, 123 . n=m This proves that the 4D Z n=m . This proves q . sum 2 q can be done in aThe similar way as in Fig. 2(c). The spins s Thus, we have sh blue face depends on each of them twice (and the is jinteractions generalization to k-body interactions k Abelian ! 4 with The generalization to k-bodywith k ! 4 discrete LGTs and discrete S discrete spin Abelian discrete typeclassical interactions, fo mod 2, thus r1 + r1 = 0,adand similarly for rAbelian 2 ). taking place incan thebefinal are never donek-body incan a similar as in Fig. 2(c). The spins s be interaction doneway in a similar way as in Fig. 2(c). The spins s j 2.5. Approximate completeness for j each spindiscrete participat 4–body interactions can be generated Abelian similarly. discrete In Abelian LGTs and discre L jacent, and each of them part a this face at front, back taking placeisin the of final k-body interaction areinteraction neverLGTs adtaking place incase, thethe final k-body never adthe four logical particles areare distributed close in (??). However, and continuous SSMs.—We canw 2.5. Approximate completeness 2.5. Approximat each other asisshapes). shown in ??, all cover faces as in Fig. ??, and th jacent, and each of is partofof a face at theof front, back or side with three spins fixed bythem the gauge (red u jacent, andto each them part aFig. face at and the back Construction of the superclique LGTs and continuous SSMs.—We that thefront, 4D Z is also approxi LGTs and continuo 2 LGT (called an “end”) th are merged to give rise to the Ising–type interaction or side with three spins fixed by the gauge (red u shapes). or side withare three spins fixed by the gauge (red u shapes). All but one of the remaining faces merged, and the that the 4D LGT is4D also the LG 2that Abelian continuous that t tion. There itZisis, clea J1234 (−1)s +s +s +s . The procedure for the 5–body in- Zmodels, 2app All but oneinof thebut remaining faces are k-body merged, and the All one of the remaining faces are merged, and the interaction strength J that face determines the Abelian models, that 1...k twocan interactions, cor teraction analogous; in this case, of oneaadds one more continuous logAbelian continuou Construction of many-body Ising-type int.: continuous model be expre interaction strength J in that face determines the k-body interaction strength J in that face determines the k-body 1...k generally, ical spin and1...k merges the overall cover face of (seea ??). continuous model can betheex Ising-type interaction. ofMore a continuous m accuracy, as a specific instance of of the Ising-type interaction. 10 coded particle) d Ising-type interaction. accuracy, as a specific instance of accuracy, asjust a−spec 1-body s2 s4 LGT. To see r3-body 2-body d has are 2(d d ). 2 this, we ne the 4D Z 2 4D Z LGT. To see this, we eju the the 4D Zalone, 2 2 LGT. agated butTo a r1 (which we will refer model to as the “target” model), cializes to a general n–body interaction. Note that here lattice spacing remaining discrete) J1234 lattice spacing remaining discre of an adjacent face lattice spacing rem the dependence on r1 and r2 also cancels, since the large according to Eq. (??). approximation can Ising– beapproximation obtained (see s1 we haver3shown how propagated), hence approximation can be obtained (sb Thus, k−body blue face depends on each of them twice (and the sum is s3 to obtain can d = results.—The particle type interactions, for any k =2.6. 1, . . . ,Efficiency n. 2.6. Now Efficiency we must let mod 2, thus r1 + r1 = 0, and similarly for r2 ). results.—The con 2.6.3tothe Efficiency n−1 need resort to a each spin participate in 2 interactions, pointed out 4–body interactions can be generated similarly. In aboveasenables onegenerate, toenables generate above enables one to fro above on ends (see Fig. ?? fo this case, the four logical particles are distributed close in (??). However, we have seen that a spin propagates Hamilton functions thatinto contain Hamilton functions that contain Hamilton function one spin fiveM oth to each other as shown in Fig. ??, and all cover faces as in Fig. ??, and this propagation ends in a certain face k-body interactions with an overh cedure be multip (called an “end”) that participates in a k–body interacare merged to give rise to the Ising–type interaction k-body interaction k-body with ancan overhead s1 +s2interactions +s between spins s1FIG. +s29: 4–body Ising–type interaction 3 s1 , s2 , s3 +ss +s konly ends, that is, one en J (−1) tion. There it is clear that spin s can participate in J1234 (−1)Js1 +s . The procedure forJthe 5–body ink (−1) (−1) ) for q ¼ 2. In the case of 2 123 k the1 caption of Fig. ?? 2 ) for q ¼ 2.q-stat 12 Inproc th and fixed s4 withbycoupling strength J See 1234 . 2 )infor qmarked ¼ 2. In the case of q-state m FIG. 2 (color online). Spins the gauge are marked this replication FIG. 2 (color online). Spins fixed by the gauge are in two interactions, corresponding to the left and right ends. teraction analogous; in this case, one adds one more log0 FIG. 2 (color online). Spins fixed by the gauge are marked in for an explanation of the symbols. 0 k -body interaction terms, at mo red. A cover single-body, two-body More and agenerally, three-body Ising-type ken-body interaction gauge formed. the ends that an object (orterms, ical spin and merges the overall face (seeAa??). red. single-body, a two-body andnumber a three-body Ising-type k0of-body interaction at most 2p 0 m are red. A single-body, a two-body and a three-body Ising-type two-level actions between k 4-body , J , and J are shown q interaction withinteraction coupling strengths J coded particle) of dimension d in a lattice of dimension actions between k 1 12 123 ande J123 between are shown k0 m two-level parti with coupling strengths 5-body J1 , J12 ,actions , J , and J are shown q interaction with coupling strengths J s2 in s r 4 has123 are s2(d − de ). rHere the logical spinterm. prop1 12 2 and (c), respectively. each Therefore, the overhead (a), (b), 2 s4 ris4 never each term. Therefo in (a), (b), and (c),drespectively. 2 agated alone, but always “carries” the other three spins each term. Therefore, the overhead in in (a), r1 (b), and (c), respectively. r1 J  Completeness of the 4D Z2 LGT 1  1  2  31  2  3  4  4  230502-3 of anJ12345 adjacent face fixed (i.e. the shape of Fig. ??(a) is s5 230502-3 s1 propagated), hence we essentially have de = 2. So, for 230502-3 s3 r3 s1 s3 r3 d = 3 the particle is blocked to have only 2 ends. We need to resort to a 4D lattice to obtain 2(d − de ) > 2 ends (see Fig. ?? for a replication in four dimensions of one spin into five other ends). Then, this replication pros1 +sapplied s1 +s2 +s3 +s4 2 +s3 +s 4 +s 5 particle has 2n−1 can be multiply until the J12345 (−1) J1234 (−1) interaction between spins s1 , s2 , s3 cedure FIG. 9: 4–body Ising–type FIG. ends, 10: that is, 5–body interaction one end forIsing–type each interaction. Note that in s1 +s2 +s3 +s4 +s5 and s4 with coupling strength J1234 . See the caption of Fig.J?? (−1) . See the caption of Fig. ?? by the 12345 this replication procedure no loops of spins fixed for an explanation of the symbols. 1234  ...  for an explanation of the symbols.  s  9 ermore, 4–body notice that by setting = ∞ as well, one In 12 generated each spin participate in 2n−1 interactions, as pointed out interactions can Jbe similarly. ces s1 this + s2case, = 0, s1logical = s2 .particles This can seen as close thei.e. four are be distributed in (??). However, we have seen that a spin propagates which are not fixed, that is on s + s + r + r = in s1 Fig. + s2??, and this propagation ends in a certain face nteraction to each other as shown in Fig. ??, and all cover faces as opagation” of the value of s1 into s2 . A concate1 2 (called an “end”) that participates in a k–body interacare merged to 2–body give sum riseinteraction to performed the Ising–type (since the is modinteraction edapplication many– of this results in2). an This corresponds s1 +s2 +s3 +s4 tion. There J (−1) . The procedure for the 5–body into the Ising–type interaction s2 it is clear that spin s1 can only participate in ction of1234 a ive propagation of a 2–body spin through a certain path inbetween s1 and two interactions, corresponding to the left and right ends. teraction analogous; in this case, one adds one more strength by thelogonly face which but with attice (see Fig.with ??).coupling The direction ofdetermined this propagaMore generally, the number of ends that an object (or enical spin and merges the overall cover face (see ??). s1 +s2 hasbynot been merged (the upper face), . This mapan be changed merging all “covering” faces be- viz. J12 (−1) coded particle) of dimension de in a lattice of dimension that one formulathe incomingFurthermore, and the outgoing as setting indicated s2 notice spin, s4 J12 = ∞ asdwell, r2 by has are 2(d − de ). Here the logical spin is never propenforces s1 + s2 =in0, the i.e. construction s1 = s2 . This can be seenalone, as but always “carries” the other three spins group g.on??. This will agated r1 be important J1234 a “propagation” of the value of s into s . A concate1 2 of an adjacent face fixed (i.e. the shape of Fig. ??(a) is e superclique, where one needs to propagate logical nated application of this 2–body interaction results in an hence we essentially have de = 2. So, for s1 to bring propagated), cles in the 4D lattice where the s3 r3 to the place in particle is blocked to have only 2 ends. We d =path 3 the action occurs. effective propagation of a spin through a certain to resort to a 4D lattice to obtain 2(d − de ) > 2 the lattice (see Fig. ??). The direction of thisneed propagalique ends (see of dimension tion can be changed by merging all “covering” faces be-Fig. ?? for a replication in four dimensions 4th spin into five other ends). Then, this replication pros1 s3 and the outgoing spin, as one tween thes2incoming indicated ruct a sucedure can be multiply applied until the particle has 2n−1required to inr1Fig.Ising–type ??.r2 This will bebetween important the FIG. 9: 4–body interaction spins s1in , s24D , s3 construction Transportation in the lattice: Z2 LGT. ends, that is, one end for each interaction. Note that inavoid loops! and s4 with strength J1234 . See the Fig. ?? of coupling the superclique, where onecaption needsofto propagate this logical replication procedure no loops of spins fixed by the his means for an explanation of the symbols. particles in the 4D lattice to bring to the place gauge whereare theformed. sing–type Replication interaction occurs. Propagation specialize s4 r4 7: Propagation of a s1s2to s3 by rconcatenating 2–body 2 model. s8 s7 s9 ctions with J = ∞. Particle s has two ends (i.e. faces s1 1 s2 from the r112 J12345 s3 r7 r8 an participate in a k–body interaction): itself, s5 r1 r2 and the merge and  Completeness of the 4D Z2 LGT  s1 face where s3 is.  sing–type GT. Then d to repliicipatesFIG. in  Construction of the superclique  r3  s3  r6  s3 s2 s1 FIG. 7: Propagation of a s1 to s3 by concatenating 2–body r r 2 1 interactions with J12 =Ising–type ∞. Particle sinteraction 10: 5–body 1 has two ends (i.e. faces 2 s1 +s2 +s3 +s4 +s5 J12345 (−1) . Seein the captioninteraction): of Fig. ?? itself, and the that can participate a k–body the symbols. on offors1an explanation right faceofwhere s3 is. s1 obtained r r3 The generalization to k–body Ising–type interactions, r nd a face fors1arbitrary k, is straightforward. First, one propagates s4 s5 s6 each of the “logical spins”s2s1 , . . . , sk in the lattice unr r5 4 til they are as close to each other as possible, forming s3a “rectangular” shapes2without their red u–shapes touching each other (as is the case for the 2–, 3–, 4– and 5– (b) One can imagine this sas body(a) interaction rshown above). 1 adding more logical particles on the right of rthe 5–body FIG. 11: Replication of spins in a 4D lattice: s1 is replicated sa1 left–to–right 8: (a) Turn in the of path propagation interaction Fig.from ??, thereby enlarging the “rectangle” into s3 , s5 , s6 , s8 , s9 . Yellow faces have the same meaning as ming”inspin s ) to a down–to–up propagation (“outgos length, until one has k logical particles, analogously  Turns  ion in the y direction (precisely, A(2) idle sites, e explained below), s1 and s3 are propagated ace w = 1, where they will generate a 2–body on among them. This goes on for all 2–body ins, then for all 3–body interactions, 4–body, and to the n–body interaction. For example, the 4– eraction between s1 , s2 , s3 , s4 and then between s5 are shown in Figs. ??, ??.  FIG. 13: A 4–body interaction in the superclique. The four particles s1 , s2 , s3 and s4 are propagated into the space with w = 1, shown here. Here they interact in a 4–body Ising– type interaction as the one presented in Fig. ?? with coupling strength Jijkl . Black arrows indicate propagation of the spin (as in Figs. ??, ??; the corresponding merged faces are not depicted to avoid overloading).  Completeness of the 4D Z2 LGT Construction of the superclique .  ..  ...  1  s2 s1  s2 s1  ...  Layout superclique: s3 s3 ofsthe s3 s3 3  ...  s5 s4  J1235  s3 s2  s2 s2 Superclique: complicated interaction pattern s1 withs1simple interactions s2  z x  s3  s1  s2 s1 J1234  w y  1  a differe the 4 pa which o  A(4)  In the seco ... sFIG. s...n sn of the w =s1n space. sn ... of part sn n whether 14: View First, parti- the m 1 . . . . . . . . . . . . . . . . . . 3D space with w = 0. are they are ... diss2 cles ss12, s...2 , s3 , ss42are propagateds2into this space, and s...2 Logical particles s try isblack also en 2 long the x direction and they are propagated along brought close to each other (propagations indicated in ... s1 s...arrows) s1... s1 sin ction. Hamilton 1 interact 4–body interaction with in- func 1 order to s 1 s1 in a 2n teraction strength J1234 . After A(4) idle particles in the y that the comp z w into ... direction, particles s1 , s2 , s3 , s5 are propagated this space A(2)  s1 , s2  si  hat the idle space one has to leave in... the y direc... ` ´ `n´ n ng each propagation to the w = 1 space depends A(n) n A(3) 3 his is because, when the k particles are propathe w = 1 space, they are distributed in a line. ne has to rearrange the rectangular form FIG.them 15: in3D space with w  ... y other to interact `n´they are brought close to each and, again, x • Models 1 with strength J1235 . in A(2) the 4–body interaction 2  discrete = 0. Logical particles are dis-  Completeness of the 4D Z2 LGT Hamiltonian of superclique Hamiltonian of any classical spin model 1. General Hamiltonian on n 2-level systems: different E(s) for each s 2. Show that one can invert the system of equations  2n different energies n    0  0+0+...+0  1 (−1) . . . (−1)  1 (−1)0 . . . (−1)0+0+...+1   ..  . 1 1 (−1) . . . (−1)1+1+...+1        J J1 .. . J12...n      E(s = (0, 0, . . . , 0))   E(s = (0, 0, . . . , 1))   = ..   . E(s = (1, 1, . . . , 1))        k=0  n k  = 2ncouplings  C  3. All rows are linearly independent, thus the determinant is non zero 4. q-level models: encode each q-level system into log2 q 2-level sys. q.e.d.  si,j interacts with spin si,j+1 via a 2–body Ising–type interaction with coupling strength Ji,j;i,j+1 . Arrows indicate propagation of the spin according to Fig. ??, and the cubes marked in blue indicate a 2–body interaction according to Fig. ??(b).  Our main result implies, i tion function of the 2D Ising can be expressed as a speci function of the 4D Z2 LGT. tition function of the 2D Isin to construct the 1D array of Fig. ??, we make use of is a #P–complete problem [ the fourth dimension in order to link them as shown in means that it is computation Fig. ??. The yellow cubes have the same meaning as conclude that computing the the blue cubes in Fig. ??, that is, they correspond to 2– Z2 LGT in the real paramete body Ising–type interactions. In this manner, spin s1,1 leastmodels as hard as the other Note: efficient for, and specific target interacts withconstructions s2,1 with strength J1,1;2,1 so on. This proven that one can map all completes the construction of the 2D Ising model. hard to solve. Example: 2D Ising model: linear overhead ✓ The construction present into the complexity of the 3 s3,4 in Sec. ?? we saw that a 3D J2,4;3,4 s3,3 els with k–body Ising–type 1, . . . , n, as long as as every s3,2 most two interactions (this w s2,4 ends of Fig. ?? that made s3,1 J1,4;2,4 This implies, in particular, s2,3 be as hard as any vertex mo Ising–type interactions. s2,2 J2,1;3,1 s1,4 On the other hand, using ], one can show that approx s2,1 s1,3 tion of the 3D Z2 LGT in a regime with polynomial accu s1,2 w z J1,1;2,1 arbitrary quantum Note: 2D Ising can computa y ]. but LGT cannot s1,1 x magnetize,  Completeness of the 4D Z2 LGT  B.  Mean–F  Completeness of the 4D Z2 LGT We have proven that: constructive  global & local symmetries  Z4DZ2 LGT (J, J ) = Zany classical spin model (J) real  larger  Abelian discrete  ✓ any dimensions ✓ q-level systems, any q ✓ any many-body int.  Target hamiltonian with M terms and k-body int: scaling poly(M, 2k ) Result holds approx for continuous models: let q → ∞  Applications of completeness Symmetries of the states  symmetries of the partition function  ZG (J) = α(J)|S|ϕG = ZG (J )  α(J )|  Mapping models with poly overhead: infer comput. complexity e.g. 2D Ising with fields #P-hard  poly larger  4D Z2 LGT #P-hard  Many different universality classes are mapped to a single model They should be reproducible in the phase diagram of the complete model  this includes ‘unexplored’ models  Computational complexity  I  Mapping partition functions to quantum circuits Classical spin model Boltzmann weight of each int. a  Quantum gate, e.g. a = W(12)(12)  −βha (s1 ,s2 )  w =e  Product of interactions w  Quantum circuit a  e−βh  (s1 ,s2 )  |s1 , s2 s1 , s2 |  Contraction of quantum gates = Circuit C  a  a  Left & Right bound. cond.  Output & Input of circuit  L L = (sL 1 , . . . , sn )  L |L = |sL 1 . . . |sn  R R = (sR 1 , . . . , sn )  R |R = |sR 1 . . . |sn  Z L,R = L|C|R  ✓PBC Z = Tr C ✓other geometries  M. Van den Nest, W. Dür, R. Raussendorf, H. J. Briegel, Phys. Rev. A 80, 052334 (2009)  Mapping partition functions to quantum circuits Mapping for vertex models Particles at the edges Interaction at vertex a  sL n  e  wa (si , sj , sk , sl ) i j  k l  sR 1 R s2  sL 1| sL 2|  sn  sL n|  L,R Zvm = L|C|R  a W(ij)(kl)  i k j l  a  e−βh  (si sj sk sl )  |sR 1 |sR 2 ...  sL 1 L s2  a W(ij)(kl) =  −βha (si sj sk sl )  ...  w (s) =  Two-qudit gate  ...  a  ...  I  |si , sj sk sl |  Gemma pu model is: Th such that q– sa = 0, 1, . . . to  |sR n time  where the ed sb ) = 1 if si  Mapping partition functions to quantum circuits Mapping for edge models Particles at the vertices Int. at edge in time dir.  Single qudit gate  wij = e−βh(si ,sj )  Two qudit diagonal gate  sL 3  j v wjk k  sR 2  sR 3  sL 1| sL 2|  |sR 1 i  ...  i  ...  sL 2  sR 1 h wij  e−βh(sj ,sk ) |sj sk sj sk |  w(jk)(jk) =  Wijh  j v Wjk k  sL n|  L,R Zem = L|C|R  |sR 2 ...  wjk = e−βh(sj ,sk ) sL 1  e−βh(si ,sj ) |si sj |  w(i)(j) =  Int. at edge in space dir.  ...  I  |sR n time  horizontal and v Wev , respectively Fig. 3 for an exa graph is n then C similar to (19), o conditions, is eas as well (both wit sL 1  I  Mapping partition functions to quantum circuits Mapping for lattice gauge theories Particles at the edges  &  Fixing the temporal gauge  Int. at face in time dir.  Single qudit gate  wij = e−βh(si ,sj )  w(i)(j) =  Int. at face in space dir.  Four qudit diagonal gate  wjk = e−βh(sj ,sk ) wa,b,c,d sL 1 sL 2  e−βh(si ,sj ) |si sj |  w(jk)(jk) = Wfs  wa,b sR 1 sR 2  e−βh(sj ,sk ) |sj sk sj sk | Wft  sL 1| |sR 1 sL 2|  |sR 2  time  L,R = L|C|R Z LGT (Left) In a 3D LGT, particles (black and gray dots) sit at the edges and interactions (pale red and blue ellipses) t  FIG. 4: place on the faces. Gray dots indicate particles whose state has been fixed by the gauge. (Right) This model is mapped t  II  BQP-completeness results  Main idea: Model  Gates corresp. to that model  Show that they form a universal gate set  Z = L|C|R  Approximating that partition function is as hard as simulating arbitrary quantum computation  II  BQP-completeness results  Main idea: Model  Gates corresp. to that model  Show that they form a universal gate set  Z = L|C|R  Approximating that partition function is as hard as simulating arbitrary quantum computation  II  BQP-completeness results  Main idea: Model  Gates corresp. to that model  Show that they form a universal gate set  Z = L|C|R  Approximating that partition function is as hard as simulating arbitrary quantum computation  Prove BQP-completeness of computing Z Provide a quantum algorithm  II  BQP-completeness results  Six vertex model (Encoded) universal interaction U = eitHex with Hex = σx ⊗ σx + σy ⊗ σy + σz ⊗ σz Encoding |0 =  1 (|01 − |10 )⊗2 2  Preparation of |0 |0 . . . |0 from |R = |0 |1 |0 |1 . . . possible The exchange int. is achieved with the six-vertex model-type gate:    W(ij)(jk) =   ei2t    cos(2t) i sin(2t) i sin(2t) cos(2t) ei2t     II  BQP-completeness results  Six vertex model (Encoded) universal interaction U = eitHex with Hex = σx ⊗ σx + σy ⊗ σy + σz ⊗ σz Encoding |0 =  1 (|01 − |10 )⊗2 2  Preparation of |0 |0 . . . |0 from |R = |0 |1 |0 |1 . . . possible The exchange int. is achieved with the six-vertex model-type gate:    W(ij)(jk) =   ei2t    cos(2t) i sin(2t) i sin(2t) cos(2t) ei2t     Approximating the partition function of the six vertex model on a certain complex parameter regime is BQP-complete  (1, 1) (1, 1) involved and we is refer themore reader to a bit involved and we refer the reader to (1, 1) is a bit more involved and we refer the reader to or the details. is a bit more and we refer the(−1, reader (−1, 1)involved |ψ1 |ψ1|ψ1 Appendix B for the details. 1)|ψ1to Appendix B for the details. 11 |ψ1 I2 |ψ1 |ψ2 CZ|ψ Appendix B for the details. I21|ψ|ψ |ψ2 CZ|ψ1 |ψ2 11 1 2 I2 |ψ1 |ψ2 t identity gate • The two–qubit identity gate • The two–qubit identity gate • The two–qubit (1, 1) gate is a bit more involved and we refer the reader to |ψ2 (1, 1) |ψidentity 2 is a bit more involved and we refer the reader to 1 Appendix B for thethe details. 1 Appendix B for details. = |ij ij| , I2 (56) = |ij ij| , (1, 1) (56) I2I|ψ|ψ 1 |ψ I2 = |ij ,2 2 2 ij| 1 |ψ i,j=0 • The two–qubit identity gate i,j=0 gate • The two–qubit identity i,j=0 1  II  |ψ2  BQP-completeness results |ψ |ψ11  1  1 |ψ 2 (1, 1) |2(56)CZ|ψ 1 |ψ2ij| , I2 = CZ|ψ|ij (−1, 1)  i,j=0  (−1, 1) 1)|ψ1 (−1, |ψ1  CZ|I  |ψ2 |ψ2  (1, 1) |2(56) (−1, 1)  |ψ |ψ22 |ψ22 1 |ψ ained by applyingis atrivially two qutrit–gate obtained by 1applying a two qutrit–gate time time time time is, trivially obtained two qutrit–gate I |ij|ijij|ij| (56) 2 I= time wo physical qutritsbetween of the first logical = (56) by applyingis atrivially (1, 2physical the two qutrits ,of the first logical (1,1) 1) obtained by applying a two qutrit–gate |2 |2 (a) (b) between the two physical qutrits of the first logical i,j=0 (a)two physical qutrits of the first i,j=0 (b) ν) = (1, 1), and qubit doing with the same between the (µ, ν)for = (1, 1), and doing the same for (−1, 1) 1) (a) logical (−1, qubit with (µ, ν) = (1, 1), and doing the same for 6a). al qubit (see Fig.the qubit with (µ, ν) = (1, 1), and doing the same for other logical qubit (see Fig. is trivially obtained by by applying a6a). two qutrit–gate is trivially obtained applying aother two qutrit–gate time time FIG. 6: the (a) Logical two–qubit I26a). .(a) (b)Logical Logical contime logical qubit identity (see Fig. FIG. 6: two–qubit I26a). . time (b) Logical conthe other logical qubit identity (see Fig. between the two physical qutrits of the first logical FIG. 6: (a) Logical two–qubit identi between the two physical qutrits of the first logical trolled phase gate CZ. See the caption of Fig. 5 for the hase gate between logical qubits FIG trolled phase gate CZ. See the caption of (b) Fig. 5 for the (a) • Finally, the phase gate between logical qubits (a) (b) qubit with (µ, ν) = (1, 1), and doing the same for qubit with (µ, ν) = (1, 1), •and the same for trolled phase gate CZ. See thetrol cap Finally, the phase gate between logical qubits meaning ofdoing the pair of numbers and the color associated to • Finally, the phase gate between logical qubits to meaning of the pair of numbers and the color associated  Potts model  1  the the other logical qubit (see Fig. 6a). other logical qubit (see Fig. each 1 |0 =gate. |06a). |1 Encoding:  meaning of the pair of numbers and mea each  each FIG. (a)Logical Logicaltwo–qubit two–qubit identity identity I22. (b) Logical FIG. 6:6:gate. (a) coneach gate.Logical conij 1 = (−1) |ij •ij|Finally, (57) CZ = (−1) |ij ij| (57) trolled phase gate CZ. See the caption of Fig. 5 for trolled for the the ij phase gate CZ. See the caption • Finally, phase gate between logical qubits thethe phase gate between logical qubits ij CZ = (−1) |ij ij| (57) CZ = (−1) |ij ij| (57) i,j=0 meaningofofthe thepair pairofof numbers numbers and and the the color associated |1 = |1 |2 meaning associated to to i,j=0 i,j=0 1 1 each gate. the use of I instead of I results ingate. ause prefactor in theofobeach i,j=0 the of I instead I results in a prefactor in the obij  1  ij ij |ij ij| the use of II instead of I resultsthe in y applying a two qutrit–gate be= (−1) (57) CZCZ =preparation (−1) |ij ij| (57) tained partition function, Z = 3I Z, where I .is. .namely is achieved by applying a two qutrit–gate be-namely |0 . . . |0 |R = |0 |1 |0 |1 Trivial of from tained partition function, Z = 3 Z, where I is is achieved by applying a two qutrit–gate betained partition function, namely i,j=0 the number of times I has been applied. r–qutrit of the first logical and is achieved applying a two qutrit–gate bei,j=0 Thus, the by comtween the qubit lower–qutrit of the first logical qubit and tainZ the number of times I has been applied. Thus, the comtween the lower–qutrit of the first logical qubit and theuse useofoftween instead ofII results results in inof a prefactor prefactor in obI I instead of athe inofthe the obnumber times I has ap rit of the secondthe logical qudit with lower–qutrit the first logical qubit andbeenthe of computing is thethe same aspartition that ofthe computing upper qutrit ofapplying theplexity second logical quditZbewith I that of computing is achieved by atwo two qutrit–gate beplexity of computing Z is the same as βJ βJ I ii i=j is achieved by applying a qutrit–gate tained function, namely Z = 3 Z, where I is the upper qutrit of the second logical qudit with tained partition function, namely where Iqudit is Zwith oflogical computing is the same (e , of e theZplexity )= 3 Z, Each isfirst characterized by the 1). We also need(µ, to ν) apply thePotts same thepair upper qutrit second Z.of =the (−1, 1). We gate also need to applyqubit the and same plex tween the lower–qutrit the logical qubit and Z. the number of times I has been applied. Thus, the comtween lower–qutrit of the first logical (µ, ν) = (−1, 1). We also need to apply the same the number ofν) times I has been applied. Thus, the comZ. the lower qudit ofgate thethe second logical (µ, = (−1, 1). We also need to apply the same even I qudit maylogical scale the system size? upper qutrit second logical with with the lower qudit ofthough the second Z. plexity of computing is the the same as the thatsystem of computing even though I may scale with size? the between upper qutrit of of thethe second logical qudit with gate between the lowerplexity qudit the between second logical ofof computing ZZ is same as that of the computing even though I may scale with th uxiliary particle in the state |2 (see gate the lower qudit of second logical ν) (−1, = also need apply the same Second, note that the implementation ofnote the that gatesthe H,implementation of the gates H, qubit and an(−1, auxiliary particle in the state |2 (see e Z. gate (µ, (µ, ν) = 1). 1). WeWe also need to to apply the same Second, Z. Construct an (encoded) universal set: qubit and an auxiliary particle in the state |2 (see Second, note that the implement qubit and an auxiliary particle in the state |2 (see gate between the lower qudit of the second logical andofCZ ofthough the energy Jiiscale ,complex more Fig. though may scale withvalues the system system gate6b). between the lower P qudit therequire second complex logical values Peven and CZ require of thesize? energy Jii , more even IImay with the size? 11 valuesSo Fig. 6b). Controlled P and CZ require complex qubit and an auxiliary particle in the state |2 (see Fig. 6b). Second, note that the implementation of the gates H, precisely: Pa qubit and an auxiliary particle in the state |2 (see precisely: Second, note that the implementation of the gates H, 11 Fig. 6b). precisely: P and CZ require complex values of the energy J , more phase gate ii Fig. 6b). prec Two qubit and CZ require complex (1,identity 1) values of the energy Jii , more Phase gate is a bit more involved and weβJ refer the reader to P± precisely: = −iπ/2, 0, −∞, ln , π/2 for H ii βJ = −iπ/2, 0, −∞, ± ln , π/2 for H ii (1, 1) precisely: qubit identity P |ψSingle |ψ βJii = −iπ/2, 0,1−∞, ± ln P |ψrefer the reader |ψ Appendix B for the details. (−1, 1)|ψ is a bit more involved and we to |ψ1 |ψ P |ψ βJ = iπ/8 for P (58) |ψ |ψ I1 |ψ ii βJ = iπ/8 for P (58) βJii|ψ= , π/2P |ψ|ψ for H ii −iπ/2, 0, −∞, ± ln CZ|ψ I2βJ |ψ |ψ |ψ|ψ 2 iiH Appendix B for the details. I1P = iπ/8 for P (−1, 1)|ψ1 |ψ −∞, for 1|ψ ± ln , π/2 1 βJ |ψ I1 |ψ1ii = 2−iπ/2, 0, |ψ • The gate for CZ , P |ψ βJii = iπ |ψ I1 |ψ two–qubit identity |ψ βJ = iπ/8 for P (58) I |ψ |ψ βJ = iπ for CZ , ii CZ|ψ |ψ 2 1 2 1 2 |ψ I1 |ψ βJii =iiiπ/8 for P (58) for CZ , βJii = iπ • The two–qubit|2identity gate |2 |ψ |ψ2 βJ = iπ for CZ , 2 ii 1 which is outside the usual (real) parameter |2 range where (1, 1) |2 βJ = iπ for CZ , iioutside which is the usual (real) parameter range where |2 iπ/8 |ψ2 |ψ2usual (real) pa (1,iπ/8 1) which is outside the (e (1, , 1)1)I2 = 1 these |ij spin ij| , models (56) (1, 1) |2 (e are , 1) defined. which whi (1, 1) defined. iπ/8 outside the usual (real) parameter range where theseisspin models iπ/8 (e ,are 1) |2 iπ/8 (1, 1) I2 = i,j=0|ij ij| , these spin models are defined. (56) which is outside the usual (real) parameter range where (e , 1) (e , 1) (1, 1)enables We remark(eiπ/8 that the schemethese presented above spin models are defined. thes We remark that the scheme presented above enables , 1) (−1,|2 1) spin models are defined. We remark that the scheme pre i,j=0one to perform x-rotations R these We remark that the scheme presented above enables with an arbitrary angle Rx (θ) with an arbitrary time W x (θ) one to perform x-rotations angle time time (−1, 1) is trivially obtained by applying a two qutrit–gate Weto remark that the scheme presented above enables one to perform x-rotations R (θ) w time time time time perform x-rotations R (θ) with an arbitrary angle x time by setting one time x θ. This is achieved the first single-qutrit gate one time gate time by setting the first single-qutrit θ.toThis is achieved isbetween trivially obtained by applying two qutrit–gate the two physical qutritsa of the first logical one perform x-rotations Rx (θ) with an arbitrary angle time time time time θ. This is achieved by setting the fi θ. This is (−i achieved by setting the first single-qutrit gate (b) acting on the upper qutrit to (µ, ν) = cot θ, 1), and θ. T (a) qutrit to (µ, ν) = (−i cot θ,(b) (a) acting on the upper 1), and between the(a) twoν)physical qutrits of the (a) first logical qubit with (µ, = (1, 1), and doing the(b) same for θ. This is achieved by setting the first single-qutrit gate (b) acting on = the upper qutrit to (µ, ν) = (−ion cotthe θ, 1), and qutrit to (µ, ν acting upper (b) the two last single-qutrit gates tothe (µ,two ν) (iupper sin (a) θ, (b) 1). The (b) acti GDlC, Van den Nest, W. J. Briegel, M.A. Martin-Delgado preparation) qubit with (µ, ν)M.= (1, 1), and doing theDür, sameH.for last single-qutrit toν) ν) = θ, (i1). sin θ, 1). The (a)logical (b) acting on the qutrit togates (µ, ν)(in =(µ, (−i cot θ, 1), and 6a). the other qubit (see Fig. the two last single-qutrit gates to (µ, = (i sin The  From the a discrete h its comthan with the point e paramean include antum alr regimes ms cannot physical, ntered in  e we need re we ens to have lattice in et boundce. This in which ry qubits: he fourth d of three triangular me correerpendicgates (see particles auxiliary  the Potts ereas this meters) is fact that ructure is  tts model  II |0  BQP-completeness results 12  aux.  phys.  aux.  18  |ψ1t  |2 |2  |1  |0 |1  |ψ2t  |2  =  |1  (1, 0)  |2  Example (a) of part of a circuit: aux.  |0  |ψ1t  phys.  aux.  |0  phys.  (  1 √  2  |1  (0, 1)  |1 |2 ( , 1)  Note distribution of physical and auxiliary qubits  |1  |2 |ψ2t+1 time  (0, 1) |0 |0  aux.  |0 |1  |2 ( , 1) , 1)  |2 (0, 1) (i, 1) |0 |0  |1 1 |1 ( √ , 1) 2 |2 ( , 1)  ( ( , 1) |2  |2 (0, 1) |0  1 √  2  , 1) |1  FIG. 11: Sequence of gates at the physical level required to perform a Hadamard rotation at the logical level, H . See the caption of|2Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. Gemma here there are new |ψ1t+1 colors Gemma time is inversed!  |1 |ψ2t  ( , 1)  |1 |1  time  |2  |0  |1 (1, 1)  |2  aux.  |0 |0  (−i, 1)  (1, 1) |1  =  |2  |0 (−i, 1) |0  (i, 1)  Hadamard gate  (0, 1)  |0  |1  |2  (b) FIG. 7: Setup for a 2D Potts model with the physical (phys.) qutrits surrounded by auxiliary (aux.) qutrits, i.e. by qutrits whose value is fixed. Single–qutrit gates are applied in the time direction, and two–qutrit gates are applied in a fixed time slice. (a) A time slice of the lattice at time t, where one can see the triangular structure with two auxiliary qutrits connected to each physical qutrit. Each logical qutrit is composed of two physical qutrits. (b) Two time slices of the lattice, at times t  From the a discrete h its comthan with the point e paramean include antum alr regimes ms cannot physical, ntered in  e we need re we ens to have lattice in et boundce. This in which ry qubits: he fourth d of three triangular me correerpendicgates (see particles auxiliary  the Potts ereas this meters) is fact that ructure is  tts model  II |0  BQP-completeness results 12  aux.  phys.  aux.  18  |ψ1t  |2 |2  |1  |0 |1  |ψ2t  |2  =  |1  (1, 0)  |2  Example (a) of part of a circuit: aux.  |0  |ψ1t  phys.  aux.  |0  phys.  ( , 1)  |2 (0, 1) |0 |0  |1 |1  (  1 √  2  |1  (0, 1) time  |2  |0  |1 (1, 1)  |2  aux.  |0 |0  (−i, 1)  (1, 1) |1  =  |2  |0 (−i, 1) |0  (i, 1)  Hadamard gate  (0, 1)  |0  |1 |2 ( , 1)  aux.  ( , 1) , 1)  |2 (0, 1) (i, 1) |0 |0  |1 1 |1 ( √ , 1) 2 |2 ( , 1)  ( ( , 1) |2  |2 (0, 1) |0  1 √  2  , 1) |1  FIG. 11: Sequence of gates at the physical level required to perform a Hadamard rotation at the logical level, H . See the caption of|2Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. Gemma here there are new |ψ1t+1 colors Gemma time is inversed!  Note distribution of physical and auxiliary qubits  |1  |0 |ψ2t  |1  |1  |2 |ψ2t+1 time  |1  |2  (b) FIG. 7: Setup for a 2D Potts model with the physical (phys.) qutrits surrounded by auxiliary (aux.) qutrits, i.e. by qutrits whose value is fixed. Single–qutrit gates are applied in the time direction, and two–qutrit gates are applied in a fixed time slice. (a) A time slice of the lattice at time t, where one can see the triangular structure with two auxiliary qutrits connected to each physical qutrit. Each logical qutrit is composed of two physical qutrits. (b) Two time slices of the lattice, at times t  Approximating the partition function of a 2D 3-level Potts with auxiliary qubits on a certain complex parameter regime is BQP-complete  II  BQP-completeness results  Note that this is a continuous universal gate set Wolf1. Single qubit gates with (c, d gang, is this a problem or an advantage?. Note that this qubits of the two logical qu set includes the single–qubit identity I1 , and the two– yields the state |ψ | + + + qubit identity I2 . More precisely, we will use the folthat qubits this is ainto continuous universal gate set WolfSingle 2. The four–qubit 1.gate (c,qub d) lowing encoding of four Note physical one logical 2 gang, is this a problem or an advantage?. Noteand thatthird this logical 13 qubits of t qubits, an qubit: set includes the single–qubit identity I1 , and(c, thed)two– yields the = (1, 1) to all their qubit identity I . More precisely, we will use the fol2 |0 = |0 |0 |0 |0 Encoding: |0 Wolf= |0 |0 |0 |0 which results in2.the Note that this is a continuous universal gate set 1. Single qubit gates with (c, d) = (1, 1) to all physical Thestate four– (61) lowing encoding of four physical qubits into one logical |1 = |1 |1 |1 |1 . gang, is this a problem or an advantage?. Note that this qubits of the two logical qubits on the right, which an equal superposition of al and third qubit: ⊗2 |1 = |1 |1 |1 |1 set includes the single–qubit identity I1 , and the two– yields the state |ψ | + + + + |e,4 ≡ |0000 + |0011 (c, d)+=. .(. The we single–qubit identity |0 =by|0 (c, |0 d) |0 |0= qubit identity I2 . More precisely, will use the fol- I1 is achieved which resu (61) 8a) . (1, 0) (see Fig. 2. The four–qubit gate (c, d) = (1, 0) on the second |1 = |1 |1 |1 |1 . 3. The four–qubit gates with s( an equal lowing encoding of four physical qubits into one logical |R = |0 . . . |0 |0 . . . |0 Trivial preparation of from Gates R (ξ) are obtained by letting the logical qubit and third logical qubits, and the four–qubit gates |e |00 z roundings of the two logic qubit: 4 ≡ The single–qubit identity I is achieved by (c, d) = 1 interact with a neighboring, auxiliary which (c, d)plaquette = (1, 1) to all their surrounding plaquettes, which results in the state 8a) setting . results (c, 0) (see Fig. ⊗2 The ⊗2is |0 = |0 |0 has |0 |0all remaining qubits (1, fixed to |0 , and d) = which in the state |ψ |e , where |e )3. . four– 4 i=j + |1111 4 βJii |1100 βJ (61) Gates Rz (ξ) by are obtained by letting the logical qubit (e , e ) Each 2 |1LGT-type gate is characterized the pair iξ roundings = |1 |1 (1, |1 |1 e ). (see Fig. 8b). This acts effectively a single– of all even states of 4 qubits, an equal as superposition interact with a neighboring, auxiliary plaquette which whichwith res |e4 ≡ |0000fixed + |0011 + . . .setting + += |1111 . gates 4.|1100 The four–qubit particle interaction for the logical particle. has all remaining qubits to |0 , and (c, d) |1100 + |1 The single–qubit an identity I1 is achieved by (c, d) = gate the second and third physic Construct (encoded) universal set: iξ (1, e ) (see Fig. 8b). This acts effectively as a single– (1, 0) (1, 0) (see Fig. 8a) . 3. The four–qubit gatesControlled with (c, d)logical = (1, 0) to thewhich surqubits, 4. Theresult four– particle interaction for the logical particle. Gates Rz (ξ) are obtained by letting the logical qubit roundings of the two logical qubits on the right, |ψ phase gate the second |ψ1 interact with a neighboring, auxiliary plaquette which (1, 0)which results in the state |ψ (|0000 |0011 5. The gate+CZ on + the lastqutw logical ⊗2 has all remaining qubits fixed to |0 , and setting (c, d) = |1100 + |1111 ) . yields the state |ψ (|0+ + |ψ Single qubit |ψ1 (1, i) (1, eiξ ) (see Fig. 8b). This acts effectivelyZ-Rotation as a single– 5. The gate (a) 4. The four–qubit gates with (c, d) = (1, 0) between particle interaction for the logical particle. 6. A four–qubit gateyields withthe( |0 identity |0 (1, i) the second and third physical qubits of the last two iξ the first and the second lo (1, e ) |0 (a) (1, 0) |0 state |ψ |+ 6.⊗2A four–qu logical qubits, which|0results in responds the to the Bell meas iξ the first a |0 (1, e ) |ψ |ψ four–qubit gate with (c, d) = |ψ2 |0|ψ1 responds 5. The gate CZ on the last two logical qubits, which and the second logical qubi |0 yields the|ψstate |ψ (|0+ |ψ +2|1−H|ψ ). on the thirdfour–qubi logical and the seq |0(1, i)  3D Z LGT  Z  (a) (1, eiξ ) |0  H|ψ on |0 (c) 6. A four–qubit gate with (c, d) = (1, 0) between This shows that we can now p the first(b)and the second qubit logical qubit (which cor(c) unitary This shows U , since this can th b to qubit the Bell FIG. 8: The physical qubits composingresponds the logical are measurement), and another qubit unitary U |0  |0  (b)  II  BQP-completeness results  3D Z2 LGT Note: many spins fixed by the gauge  Hadamard gate: |0  (1, 1)  14  (1, 0)  3  (1, 0)  |0  3 |ψ  (1, 1)  (1, 0) (1, 0)  3 (1, ei(α+π/2) )  4  (1, i)  5 4  (1, i) (1, 0)  6 Rz (α)H |ψ time  (1, 0) FIG. 9: Teleportation–based logical Hadamard gate H : the state of the first logical qubit |ψ is transformed to H |ψ on the third logical qubit after the last step. See the main text for an explanation of every step. See the caption of Fig. 8 for an  BQP-completeness results  II  Two–qubit gate Rz (α +  eiϕσ z ⊗σ z Two–qubit gate1  3D Z2 LGT  Verify that there are no loops of spins fixed by the gauge: Two–qubit gate 1 Two–qubit gate eiϕσ z ⊗σ z  1  Rz (α +  π ) 2  Rz ( −π )H 2  3  3 6  2  5  3  4 3  2  Rz (β +  3  4 1  3 5  6  4  4 1 1 2 3 4 5  6 7 8 9 10  2π  11 12 13 all time steps  FIG. 10: A projection of the circuit of the 3D Z2  π ) 2  1  Rz (γ) eiϕσ z31⊗σ z 2  )  2 6  Rz ( −  3  Si 3  4 3  3  2 6  2π  Rz ( −π )H 2  2  15 31  ) Rz (α + gate z Two–qubit eiϕσ z ⊗σ 2  Single–qubit gate  3  Rz (α +  eiϕσ z ⊗σ z  π 2  Rz ( −π )H 2  3 1  3  65 6 1 44 7 4 2 3 13 8 11 3 3 1 31 3 8 9 43 9 12 5 7 10 10 5 5 2 6 6 11 1 4 4 4 of 12 2FIG. 10:4 A 7projection the 13 3with a two–qubit 8 gate, a tota 3 3 8 11 1 13 4a thick black9line. All all edges timei 10 dots). Edges 5the gauge (pink 6gauge in different 11 time steps 1 12 9 7 10 5 12 2FIG. 10: A 7projection correspondsofin this figureoftotha the circuit 13 3with a two–qubit 8 gate, a totally general sin 4 4 4a thick black9line. All edges in the time di all time steps 10 5the gauge (pink dots).polynomially Edges in the with spatian inverse 13 gauge in different time 1,. . . , 13, ind variant of steps the Hadamard t FIG. 10: A projection circuit oftothe 3D LGT correspondsofinthe this figure a loop color ature. Moreover, theZof2probl with a two–qubit gate, a totally single qubit rotc tracesgeneral of unitary quantum a thick black line. All edges in the time direction (going hard. In other words, this p the gauge (pink dots).polynomially Edges in the with spatialn.direction are inverse techn that can be indicated solvedThe efficientl gauge in different time steps 1,. . . , 13, with variant of the Hadamard test plays and we ar It thus corresponds in this figure toparadigm. a loop of colored edges. a si ature. Moreover, the problem of estima trix element problem for BQ traces of unitary quantum circuits is kno Our results obtained in S hard. In other words, this problem captu complete problem isfora DQ inverse polynomially witha n. The technique sim that can be solved efficiently within the variant of the Hadamardfunctions test and defined we referontographs the li LGT into its spatial dimension. The figure shows the part of theItcircuit paradigm. thus plays a similar role as ditions.of We limit ourselves ature. Moreover, the problem estimating normal trix element problem for BQP.  BQP-completeness results  II  Two–qubit gate Rz (α +  eiϕσ z ⊗σ z Two–qubit gate1  3D Z2 LGT  Verify that there are no loops of spins fixed by the gauge: Two–qubit gate 1 Two–qubit gate eiϕσ z ⊗σ z  1  Rz (α +  π ) 2  Rz ( −π )H 2  3  3 6  2  5  3 2  Rz (β +  3  4  4 1  3  3 5  6 4  4  1 1 2 3 4 5  2π  π ) 2  Rz (γ) eiϕσ z31⊗σ z 2 6  Rz ( −  3  Si 3  4 3  3  Rz ( −π )H 2  3 1  3  65 6 1 44 7 4 2 3 13 8 11 3 3 1 31 3 8 9 43 9 12 5 7 10 10 5 5 2 6 6 11 1 4 4 4 of 12 2FIG. 10:4 A 7projection the 13 3with a two–qubit 8 gate, a tota 3 3 8 11 1 13 4a thick black9line. All all edges timei 10 dots). Edges 5the gauge (pink 6gauge in different 11 time steps 1 12 9 7 10 5 12 2FIG. 10: A 7projection correspondsofin this figureoftotha the circuit 13 3with a two–qubit 8 gate, a totally general sin 4 4 4a thick black9line. All edges in the time di all time steps 10 5the gauge (pink dots).polynomially Edges in the with spatian inverse 13 gauge in different time 1,. . . , 13, ind variant of steps the Hadamard t FIG. 10: A projection circuit oftothe 3D LGT correspondsofinthe this figure a loop color ature. Moreover, theZof2probl with a two–qubit gate, a totally single qubit rotc tracesgeneral of unitary quantum a thick black line. All edges in the time direction (going hard. In other words, this p the gauge (pink dots).polynomially Edges in the with spatialn.direction are inverse techn that can be indicated solvedThe efficientl gauge in different time steps 1,. . . , 13, with variant of the Hadamard test plays and we ar It thus 2 corresponds in this figure toparadigm. a loop of colored edges. a si ature. Moreover, the problem of estima trix element problem for BQ traces of unitary quantum circuits is kno Our results obtained in S hard. In other words, this problem captu complete problem isfora DQ inverse polynomially witha n. The technique sim that can be solved efficiently within the variant of the Hadamardfunctions test and defined we referontographs the li LGT into its spatial dimension. The figure shows the part of theItcircuit paradigm. thus plays a similar role as ditions.of We limit ourselves ature. Moreover, the problem estimating normal trix element problem for BQP.  6 11 7 12 13 8 Approximating the partition function of 9 all time steps on a 10certain complex parameter regime is  FIG. 10: A projection of the circuit of the 3D Z2  1  2  )  2 6  2π  Rz ( −π )H 2  2  15 31  ) Rz (α + gate z Two–qubit eiϕσ z ⊗σ 2  Single–qubit gate  3  Rz (α +  eiϕσ z ⊗σ z  π 2  a 3D Z LGT BQP-complete  Summary  Summary Completeness Z = α|ψ  Z4DZ2 LGT (J, J ) = Zany classical spin model (J) real  Abelian discrete  ✓ any dimensions ✓ q-level systems, any q ✓ any many-body int.  Z = L|C|R  Complexity Approximating Z of Six vertex model Potts model 3D Z2 LGT  is BQP-complete in a certain complex parameter regime  Thank you for your attention! Completeness  M. Van den Nest, W. Dür, H. J. Briegel, Phys. Rev. Lett. 100, 110501(2008) 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)  Complexity  Y. Xu, GDlC, W. Dür, H. J. Briegel, M.A. Martin-Delgado, Completeness of a U(1) lattice gauge theory (in preparation)  **  M. Van den Nest, W. Dür, R. Raussendorf, H. J. Briegel, Phys. Rev. A 80, 052334 (2009)  **  GDlC, M. Van den Nest, W. Dür, H. J. Briegel, M.A. Martin-Delgado, Computational complexity of classical lattice models (in preparation)  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
China 24 21
United States 21 0
Japan 9 0
Canada 5 0
Morocco 2 0
Russia 2 0
Republic of Moldova 1 0
City Views Downloads
Beijing 20 0
Ashburn 13 0
Tokyo 8 0
Shenzhen 4 21
Unknown 4 0
Vancouver 4 0
Mountain View 4 0
Saint Petersburg 2 0
Wilmington 1 0
Chişinău 1 0
Ottawa 1 0
Seattle 1 0
Hanover 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

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>
                        
                    
IIIF logo 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.29986.1-0103171/manifest

Comment

Related Items