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

Unifying Classical Spin Models Using A Quantum Formalism 2011

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

Item Metadata

Download

Media
De_las_Cuevas_Vancouver-workshop.pdf
De_las_Cuevas_Vancouver-workshop.pdf [ 9.76MB ]
WS Jul 23 de las Cuevas.mp4
WS Jul 23 de las Cuevas.mp4
WS Jul 23 de las Cuevas.mp4 [ 4MB ]
WS Jul 23 de las Cuevas.mp4
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
Citation
1.0103171.ris

Full Text

* Gemma De las Cuevas Ying Xu Wolfgang Dür Hans J. Briegel Vancouver, 23rd July 2010 @ Innsbruck Maarten Van den Nest                @ MPQ Garching Miguel Angel Martin-Delgado  @ Madrid Unifying classical spin models using a quantum formalism Outline  Motivation  Completeness  Summary  Complexity The 4D      lattice gauge theory is completeZ2 Approximating the partition function of some models is BQP-complete Motivation Motivation  Classical spin models: Classical magnetism Spin glasses Econophysics Neural networks ... Motivation  Classical spin models: Classical magnetism Spin glasses Econophysics Neural networks ... Toy models to tackle complex systems 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... Local: lattice gauge theories H(s) = −J ∑ (i,j,k,l)∈∂f sisjsksl v local flip v H(s) H(s′)= Symmetries: Global: Ising, Potts ... H(s) = −J ∑ (i,j)∈E sisj global flip 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? Use Quantum Information tools to relate them Completeness results: Models with different features can be mapped onto a single model Yes! In equilibrium the crucial quantity: partition function Z = ∑ s e −βH(s) Completeness Completeness M. 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 model on an arbitrary graph M. 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 .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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. where |0Y 〉VE is a tensor product of the (+1)-eigenstate of Y on all edge qubits, and Σ′ are the local Pauli operators appropriate for the corresponding measurement outcomes. To summarize, |C〉 can be generated from |ϕ2D〉 via equation (20), which shows that also |ϕ2D〉 is a universal resource state. Given the universality of the cluster state, it follows that any state |ψ〉 (in particular any |ϕG〉) can be generated from |C〉 via equation (19). Together, this implies that any state |ϕG〉 can be generated from |ϕ2D〉 by means of local measurements (see figure 6). We are now ready to establish the connection between the evaluation of Ising partition functions and universal measurement-based quantum computation. To do so, consider the following procedure. First, the partition function of an Ising model on a graph G can be expressed in the form (6). The stabilizer state |ϕ2D〉 is obtained from the cluster state |C〉 after applying a certain measurement pattern |β〉 (i.e. we consider (19) with |ψ〉 = |ϕ2D〉). Finally the cluster state |C〉 is obtained from the state |ϕ2D〉 after measuring all edge qubits in the Y basis (see equation (20) and figure 6). This means that the partition function of the Ising model on the graph G can be written as ZG({Jab, ha}) = A 〈γ|ϕ2D〉, (21) where A = 2(|E|+|V |+M−n)/2 is a constant and |γ〉 is a product state, |γ〉 = Σ|α〉 ⊗ Σ′|β〉 ⊗ |0Y 〉VE . Now, by comparing the right hand side of (21) with (6) we see that it corresponds to the partition function of the Ising model on a 2D square lattice evaluated with a set of parameters {J ′ij, h′i} determined by |γ〉. This allows us to conclude that ZG can be written as follows: ZG({Jab, ha}) ∝ Z2D({J ′ij, h′i}). (22) In other words, the partition function of the Ising model on an arbitrary graph can be recovered as a special instance of the partition function of the Ising model on a 2D square lattice. This proves that the 2D Ising model is complete for Ising models on any other graph. In the above derivation, we have introduced an intermediate step to go from the resource |ϕ2D〉 to the 2D cluster state |C〉 in order to show the universality of the state doi:10.1088/1742-5468/2009/07/P07001 13 Z2D Ising with h(J, J ′) J ′ larger on an arbitrary graph M. 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 .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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. where |0Y 〉VE is a tensor product of the (+1)-eigenstate of Y on all edge qubits, and Σ′ are the local Pauli operators appropriate for the corresponding measurement outcomes. To summarize, |C〉 can be generated from |ϕ2D〉 via equation (20), which shows that also |ϕ2D〉 is a universal resource state. Given the universality of the cluster state, it follows that any state |ψ〉 (in particular any |ϕG〉) can be generated from |C〉 via equation (19). Together, this implies that any state |ϕG〉 can be generated from |ϕ2D〉 by means of local measurements (see figure 6). We are now ready to establish the connection between the evaluation of Ising partition functions and universal measurement-based quantum computation. To do so, consider the following procedure. First, the partition function of an Ising model on a graph G can be expressed in the form (6). The stabilizer state |ϕ2D〉 is obtained from the cluster state |C〉 after applying a certain measurement pattern |β〉 (i.e. we consider (19) with |ψ〉 = |ϕ2D〉). Finally the cluster state |C〉 is obtained from the state |ϕ2D〉 after measuring all edge qubits in the Y basis (see equation (20) and figure 6). This means that the partition function of the Ising model on the graph G can be written as ZG({Jab, ha}) = A 〈γ|ϕ2D〉, (21) where A = 2(|E|+|V |+M−n)/2 is a constant and |γ〉 is a product state, |γ〉 = Σ|α〉 ⊗ Σ′|β〉 ⊗ |0Y 〉VE . Now, by comparing the right hand side of (21) with (6) we see that it corresponds to the partition function of the Ising model on a 2D square lattice evaluated with a set of parameters {J ′ij, h′i} determined by |γ〉. This allows us to conclude that ZG can be written as follows: ZG({Jab, ha}) ∝ Z2D({J ′ij, h′i}). (22) In other words, the partition function of the Ising model on an arbitrary graph can be recovered as a special instance of the partition function of the Ising model on a 2D square lattice. This proves that the 2D Ising model is complete for Ising models on any other graph. In the above derivation, we have introduced an intermediate step to go from the resource |ϕ2D〉 to the 2D cluster state |C〉 in order to show the universality of the state doi:10.1088/1742-5468/2009/07/P07001 13 Z2D Ising with h(J, J ′) J ′ larger complex GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009) Completeness with real coupl. Analogous for q-level systems Ising model:  Result: J.Stat .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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. 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. doi:10.1088/1742-5468/2009/07/P07001 23 J.Stat .M ech .(2009)P07001 Com pleteness of classical spin m odels and universal quantum com putation 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. Figure 13. M easurement 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. doi:10.1088/1742-5468/2009/07/P07001 23 J.Stat .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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 which 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 the boundaries 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 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 obtain a plaquette without a crossing, we only need to select a square in the 2D square lattice of the same size as in figure 13, and delete all vertices inside. Then we merge the vertices 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 with crossings by means of the merge and deletion rule alone. To do so, we first embed the figure 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 made explicit later in figure 19). We do it by tilting every square to the left so that the former vertical lines of the squares now coincide with the diagonal lines (going from the upper left corner to the doi:10.1088/1742-5468/2009/07/P07001 25 = realJ ′ larger ZIsi g, any G(J)Z3D Ising(J, J ′) ✓ GDlC, W. Dür, M. Van den Nest, H. J. Briegel, JSTAT P07001 (2009) Completeness with real coupl. Analogous for q-level systems Ising model:  Result: J.Stat .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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. 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. doi:10.1088/1742-5468/2009/07/P07001 23 J.Stat .M ech .(2009)P07001 Com pleteness of classical spin m odels and universal quantum com putation 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. Figure 13. M easurement 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. doi:10.1088/1742-5468/2009/07/P07001 23 J.Stat .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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 which 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 the boundaries 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 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 obtain a plaquette without a crossing, we only need to select a square in the 2D square lattice of the same size as in figure 13, and delete all vertices inside. Then we merge the vertices 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 with crossings by means of the merge and deletion rule alone. To do so, we first embed the figure 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 made explicit later in figure 19). We do it by tilting every square to the left so that the former vertical lines of the squares now coincide with the diagonal lines (going from the upper left corner to the doi:10.1088/1742-5468/2009/07/P07001 25 = realJ ′ larger ZIsi g, any G(J)Z3D Ising(J, J ′) 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 systems Ising model:  Result: J.Stat .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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. 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. doi:10.1088/1742-5468/2009/07/P07001 23 J.Stat .M ech .(2009)P07001 Com pleteness of classical spin m odels and universal quantum com putation 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. Figure 13. M easurement 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. doi:10.1088/1742-5468/2009/07/P07001 23 J.Stat .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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 which 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 the boundaries 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 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 obtain a plaquette without a crossing, we only need to select a square in the 2D square lattice of the same size as in figure 13, and delete all vertices inside. Then we merge the vertices 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 with crossings by means of the merge and deletion rule alone. To do so, we first embed the figure 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 made explicit later in figure 19). We do it by tilting every square to the left so that the former vertical lines of the squares now coincide with the diagonal lines (going from the upper left corner to the doi:10.1088/1742-5468/2009/07/P07001 25 = realJ ′ larger ZIsi g, any G(J)Z3D Ising(J, J ′) same kind of interactions ✓ tradeoff between ‘compl teness power’ and real parameters? ✓ any dimensions ✓ q-level systems, any q ✓ any many-body int. real Abelian discrete Z4DZ2LGT(J, J ′) = Zany classical spin model(J) lattice gauge theory global & local symmetries Completeness of the 4D     LGTZ2 constructive larger GDlC, 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 theory Completeness of the 4D     LGTZ2 Superclique4D       LGTZ2 all k-cliques for k=1,...,n with Ising-type int. real couplings J = 0,∞  Idea of the proof: lattice gauge theory Completeness of the 4D     LGTZ2 Superclique4D       LGTZ2 all k-cliques for k=1,...,n with Ising-type int. real couplings J = 0,∞  Idea of the proof: lattice gauge theory Completeness of the 4D     LGTZ2 Superclique4D       LGTZ2 all k-cliques for k=1,...,n with Ising-type int. real couplings J = 0,∞  Idea of the proof: lattice gauge theory Superclique4D       LGTZ2 J12 J23 J34 J14 J1 J2 J3 J4 J123 J134 J124 J1234 Completeness of the 4D     LGTZ2 real couplings J = 0,∞  Idea of the proof: lattice gauge theory Superclique4D       LGTZ2 Any Abelian discrete classical spin model Hamiltonian! J12 J23 J34 J14 J1 J2 J3 J4 J123 J134 J124 J1234 Completeness of the 4D     LGTZ2 real couplings J = 0,∞  Idea of the proof: lattice gauge theory Superclique4D       LGTZ2 Any Abelian discrete classical spin model Hamiltonian! J12 J23 J34 J14 J1 J2 J3 J4 J123 J134 J124 J1234 Completeness of the 4D     LGTZ2 non planar any many-body int....= ... Potts... q q J.Stat .M ech .(2009)P07001 Completeness of classical spin models and universal quantum computation 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 which 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 the boundaries 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 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 obtain a plaquette without a crossing, we only need to select a square in the 2D square lattice of the same size as in figure 13, and delete all vertices inside. Then we merge the vertices 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 with crossings by means of the merge and deletion rule alone. To do so, we first embed the figure 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 made explicit later in figure 19). We do it by tilting every square to the left so that the former vertical lines of the squares now coincide with the diagonal lines (going from the upper left corner to the doi:10.1088/1742-5468/2009/07/P07001 25 q on high dim. {J 1 , . .., J 1 2 3 4 } {J1, ..., J1234 } {J 1 , ..., J 1234} real couplings J = 0,∞  Quantum formulation of Abelian discrete LGTs 6 a b c d v 1 2 34 |s〉1 := |(sa + sb + sc + sd)mod q〉1 FIG. 1: The state |ψLGT〉 places one quantum particle (blue dots, labeled with numbers) at each face, thereby characteriz- ing the interaction of classical spins (black dots, labeled with letters) around that face. The quantum spin at face f1, sf1 is obtained by summing modulo q the values of the spins at the boundary of the face. and each column (edge) contains 2(d− 1) ones, where d is the dimension of the lattice, and the rest are zeros. In the case of open boundary conditions, the edges in the boundary participate in only (d− 1) faces. There is a standard way to compute the stabilizers out of a matrix such as A (see, e.g. [? ]). We first note that the rank of the matrix A depends on the dimension of the lattice d. If A has full rank, then each column of A corresponds to one X stabilizer, and there are no Z stabilizers. If A does not have full rank, then a set of m linearly independent columns in A corresponds to the X stabilizers, and one has to find a set of |F | − m Z stabilizers which are orthogonal to each other and to all X stabilizers. Via this procedure, one can see that the state |ψLGT〉 defined on a 2D square lattice with open boundary con- ditions corresponds to the product state |+〉⊗|F |, where |+〉 is the eigenstate of the Pauli matrix X , with eigen- value +1, X |+〉 = |+〉. |ψLGT〉 defined on a 2D square lattice with periodic boundary conditions corresponds to the state |GHZ〉 = |0〉⊗|F | + |1〉⊗|F |. For higher dimen- sional lattices, e.g. 3D lattices, the state |ψLGT〉 is less trivial. Below, we will use the state |ψLGT〉 defined on some lattice as a resource for measurement–based quantum computation [? ] in order to prove the completeness of that LGT on that lattice. The fact that |ψLGT〉 de- fined on a 2D lattice contains either no entanglement at all (open boundary conditions) or a very small amount of them (periodic boundary conditions), and thus are use- less states from the point of view of measurement–based quantum computation, is in agreement with the fact that 2D Z2 LGTs are trivial [? ] and cannot be complete. As noticed in [? ], the fact that |ψLGT〉 is a stabilizer state reveals some symmetries in the partition function. That is, because |ψ〉 is left invariant under any opera- tor s ∈ S, s|ψ〉 = |ψ〉, this translates into the following invariance in the partition function Z = 〈α|ψ〉 = 〈α|s|ψ〉. (12) This implies that there is another set of couplings, de- termined by 〈α′| = 〈α|s that yields the same partition function as the original set 〈α|. B. Merge and deletion rules We now present two rules, the merge and deletion rule, which allow us to manipulate the partition function of a model and relate it to the partition function of an- other model. The intuitive picture is that the merge rule applied to a model with, say, 4 faces, transforms it to a model with 3 faces, one being larger, and con- taining a 6–body instead of a 4–body interaction (see Fig. ??(a)). And applying the deletion rule to a face amounts to mapping it to a model where there is no such face (see Fig. ??(b)). Although these rules can be gen- erally defined for Zq LGTs, we will henceforth focus on the case Z2, since this is what we require for the proof. (a) (b) FIG. 2: (a) The merge and (b) deletion rules are tools that allow us to map one interaction pattern to another. Blue lines indicate faces where there are interactions Merge rule. The rule works by setting the coupling strength of a face, say Jf , to infinity. In order to see its effect, we consider (??), and we divide each coefficient by a factor of eβJf , |α〉f = ∑ s1,...,sk eβJf (cos[pi( P e∈∂f se)mod 2]−1)|( ∑ e∈∂f se)mod 2〉f . (13) Since this is a rescaling of the energy, this does not modify the relevant physics that one can derive from the parti- tion function. In Eq. (??) it is clear that when Jf →∞, only the coeffcient with cos  2pi q ( ∑ e∈∂f se)mod2   = 1, (14) i.e. ( ∑ e∈∂f se)mod2 = 0 remains non-zero. That is, the overlap with |αf (Jf =∞)〉 becomes a projection onto the H(s) = − ∑ f∈F Jf cos [ 2pi q (s1 + . . .+ sk)modq ] Hamiltonian Partition function: Completeness of the 4D     LGTZ2 ZG(J) = ∑ s e −βH(s)  Quantum formulation of Abelian discrete LGTs 6 a b c d v 1 2 34 |s〉1 := |(sa + sb + sc + sd)mod q〉1 FIG. 1: The state |ψLGT〉 places one quantum particle (blue dots, labeled with numbers) at each face, thereby characteriz- ing the interaction of classical spins (black dots, labeled with letters) around that face. The quantum spin at face f1, sf1 is obtained by summing modulo q the values of the spins at the boundary of the face. and each column (edge) contains 2(d− 1) ones, where d is the dimension of the lattice, and the rest are zeros. In the case of open boundary conditions, the edges in the boundary participate in only (d− 1) faces. There is a standard way to compute the stabilizers out of a matrix such as A (see, e.g. [? ]). We first note that the rank of the matrix A depends on the dimension of the lattice d. If A has full rank, then each column of A corresponds to one X stabilizer, and there are no Z stabilizers. If A does not have full rank, then a set of m linearly independent columns in A corresponds to the X stabilizers, and one has to find a set of |F | − m Z stabilizers which are orthogonal to each other and to all X stabilizers. Via this procedure, one can see that the state |ψLGT〉 defined on a 2D square lattice with open boundary con- ditions corresponds to the product state |+〉⊗|F |, where |+〉 is the eigenstate of the Pauli matrix X , with eigen- value +1, X |+〉 = |+〉. |ψLGT〉 defined on a 2D square lattice with periodic boundary conditions corresponds to the state |GHZ〉 = |0〉⊗|F | + |1〉⊗|F |. For higher dimen- sional lattices, e.g. 3D lattices, the state |ψLGT〉 is less trivial. Below, we will use the state |ψLGT〉 defined on some lattice as a resource for measurement–based quantum computation [? ] in order to prove the completeness of that LGT on that lattice. The fact that |ψLGT〉 de- fined on a 2D lattice contains either no entanglement at all (open boundary conditions) or a very small amount of them (periodic boundary conditions), and thus are use- less states from the point of view of measurement–based quantum computation, is in agreement with the fact that 2D Z2 LGTs are trivial [? ] and cannot be complete. As noticed in [? ], the fact that |ψLGT〉 is a stabilizer state reveals some symmetries in the partition function. That is, because |ψ〉 is left invariant under any opera- tor s ∈ S, s|ψ〉 = |ψ〉, this translates into the following invariance in the partition function Z = 〈α|ψ〉 = 〈α|s|ψ〉. (12) This implies that there is another set of couplings, de- termined by 〈α′| = 〈α|s that yields the same partition function as the original set 〈α|. B. Merge and deletion rules We now present two rules, the merge and deletion rule, which allow us to manipulate the partition function of a model and relate it to the partition function of an- other model. The intuitive picture is that the merge rule applied to a model with, say, 4 faces, transforms it to a model with 3 faces, one being larger, and con- taining a 6–body instead of a 4–body interaction (see Fig. ??(a)). And applying the deletion rule to a face amounts to mapping it to a model where there is no such face (see Fig. ??(b)). Although these rules can be gen- erally defined for Zq LGTs, we will henceforth focus on the case Z2, since this is what we require for the proof. (a) (b) FIG. 2: (a) The merge and (b) deletion rules are tools that allow us to map one interaction pattern to another. Blue lines indicate faces where there are interactions Merge rule. The rule works by setting the coupling strength of a face, say Jf , to infinity. In order to see its effect, we consider (??), and we divide each coefficient by a factor of eβJf , |α〉f = ∑ s1,...,sk eβJf (cos[pi( P e∈∂f se)mod 2]−1)|( ∑ e∈∂f se)mod 2〉f . (13) Since this is a rescaling of the energy, this does not modify the relevant physics that one can derive from the parti- tion function. In Eq. (??) it is clear that when Jf →∞, only the coeffcient with cos  2pi q ( ∑ e∈∂f se)mod2   = 1, (14) i.e. ( ∑ e∈∂f se)mod2 = 0 remains non-zero. That is, the overlap with |αf (Jf =∞)〉 becomes a projection onto the H(s) = − ∑ f∈F Jf cos [ 2pi q (s1 + . . .+ sk)modq ] Hamiltonian Partition function: Completeness of the 4D     LGTZ2 State defined on the faces: Product state with coefficients: |ψG〉 = ∑ s ⊗ f∈F |(s1 + · · · + sk)modq〉f |α(J)〉 = ⊗ f |αf (Jf )〉 |αf (Jf )〉 = ∑ se∈∂f e βJf cos[ 2pi q (s1+...+sk)]|s1 + ...+ sk〉f ZG(J) = ∑ s e −βH(s)  Quantum formulation of Abelian discrete LGTs 6 a b c d v 1 2 34 |s〉1 := |(sa + sb + sc + sd)mod q〉1 FIG. 1: The state |ψLGT〉 places one quantum particle (blue dots, labeled with numbers) at each face, thereby characteriz- ing the interaction of classical spins (black dots, labeled with letters) around that face. The quantum spin at face f1, sf1 is obtained by summing modulo q the values of the spins at the boundary of the face. and each column (edge) contains 2(d− 1) ones, where d is the dimension of the lattice, and the rest are zeros. In the case of open boundary conditions, the edges in the boundary participate in only (d− 1) faces. There is a standard way to compute the stabilizers out of a matrix such as A (see, e.g. [? ]). We first note that the rank of the matrix A depends on the dimension of the lattice d. If A has full rank, then each column of A corresponds to one X stabilizer, and there are no Z stabilizers. If A does not have full rank, then a set of m linearly independent columns in A corresponds to the X stabilizers, and one has to find a set of |F | − m Z stabilizers which are orthogonal to each other and to all X stabilizers. Via this procedure, one can see that the state |ψLGT〉 defined on a 2D square lattice with open boundary con- ditions corresponds to the product state |+〉⊗|F |, where |+〉 is the eigenstate of the Pauli matrix X , with eigen- value +1, X |+〉 = |+〉. |ψLGT〉 defined on a 2D square lattice with periodic boundary conditions corresponds to the state |GHZ〉 = |0〉⊗|F | + |1〉⊗|F |. For higher dimen- sional lattices, e.g. 3D lattices, the state |ψLGT〉 is less trivial. Below, we will use the state |ψLGT〉 defined on some lattice as a resource for measurement–based quantum computation [? ] in order to prove the completeness of that LGT on that lattice. The fact that |ψLGT〉 de- fined on a 2D lattice contains either no entanglement at all (open boundary conditions) or a very small amount of them (periodic boundary conditions), and thus are use- less states from the point of view of measurement–based quantum computation, is in agreement with the fact that 2D Z2 LGTs are trivial [? ] and cannot be complete. As noticed in [? ], the fact that |ψLGT〉 is a stabilizer state reveals some symmetries in the partition function. That is, because |ψ〉 is left invariant under any opera- tor s ∈ S, s|ψ〉 = |ψ〉, this translates into the following invariance in the partition function Z = 〈α|ψ〉 = 〈α|s|ψ〉. (12) This implies that there is another set of couplings, de- termined by 〈α′| = 〈α|s that yields the same partition function as the original set 〈α|. B. Merge and deletion rules We now present two rules, the merge and deletion rule, which allow us to manipulate the partition function of a model and relate it to the partition function of an- other model. The intuitive picture is that the merge rule applied to a model with, say, 4 faces, transforms it to a model with 3 faces, one being larger, and con- taining a 6–body instead of a 4–body interaction (see Fig. ??(a)). And applying the deletion rule to a face amounts to mapping it to a model where there is no such face (see Fig. ??(b)). Although these rules can be gen- erally defined for Zq LGTs, we will henceforth focus on the case Z2, since this is what we require for the proof. (a) (b) FIG. 2: (a) The merge and (b) deletion rules are tools that allow us to map one interaction pattern to another. Blue lines indicate faces where there are interactions Merge rule. The rule works by setting the coupling strength of a face, say Jf , to infinity. In order to see its effect, we consider (??), and we divide each coefficient by a factor of eβJf , |α〉f = ∑ s1,...,sk eβJf (cos[pi( P e∈∂f se)mod 2]−1)|( ∑ e∈∂f se)mod 2〉f . (13) Since this is a rescaling of the energy, this does not modify the relevant physics that one can derive from the parti- tion function. In Eq. (??) it is clear that when Jf →∞, only the coeffcient with cos  2pi q ( ∑ e∈∂f se)mod2   = 1, (14) i.e. ( ∑ e∈∂f se)mod2 = 0 remains non-zero. That is, the overlap with |αf (Jf =∞)〉 becomes a projection onto the H(s) = − ∑ f∈F Jf cos [ 2pi q (s1 + . . .+ sk)modq ] Hamiltonian Partition function: Completeness of the 4D     LGTZ2 ZG(J) = 〈α(J)|ψG〉 State defined on the faces: Product state with coefficients: |ψG〉 = ∑ s ⊗ f∈F |(s1 + · · · + sk)modq〉f |α(J)〉 = ⊗ f |αf (Jf )〉 |αf (Jf )〉 = ∑ se∈∂f e βJf cos[ 2pi q (s1+...+sk)]|s1 + ...+ sk〉f ZG(J) = ∑ s e −βH(s)  Tools to ‘transform’ the model: 7 |0〉f state, and imposes the condition ( ∑ e∈∂f se)mod2 = 0 on the remaining terms. Due to this condition, one of the spins around f is not free anymore, but equals the sum of the other k − 1 spins (since it is mod 2), say sb = sa+sc+sd in Fig. ??. This condition is substituted in another face where sb participates, e.g. in Fig. ??, the face depending on sh+sg+se+sb becomes sh+sg+se+ sa+ sc+ sd. Thus, this effectively enlarges the face, that is, a 4–body Ising–type interaction has become a 6–body Ising–type interaction by means of the merge rule. Note that this remaining 6–body interaction has a coupling strength given by the face which has been enlarged (see Fig. ??). aa b b cc dd ee gg hh ff Jf =∞ Jbegh Jadcegh 33 44 = FIG. 3: Merge rule. Setting Jf = ∞ sets the condition sa + sb + sc + sd = 0, and thus, one of the variables becomes dependent, say sb = sa + sc + sd. This is substituted in the right face, which now depends on sh+sg+se+sa+sc+sd, i.e. a 6–body Ising–type interaction, with the coupling strength of the enlarged face, Jbegh (now Jabcegh). The concatenation of merge rules and the gauge fixing of some particles allow us to achieve k–body Ising inter- actions, for any k. For example, in order to generate a 5–body interaction, we would apply the same process as in Fig. ??, and we would gauge fix one of the spins at the boundary, say sa. Note that selecting what particle on the boundary of f is dependent on the others is an arbitrary choice. That is, the face f in Fig. ?? could have been merged with the lower or right face (sc, sb dependent, respectively; see Fig. ??), or with other faces if had more than 2 di- mensions. However, all choices yield equivalent partition functions. It is even possible to choose a different depen- dent variable for every neighboring face, that is, substi- tute the condition for sb on the right face, the condition for sa on the upper face, and so on. However, this does not lead to any known model. We also remark that using the merge rule to transform a k–body interaction to a k′–body interaction, with k′ > k, is only possible if k ≥ 3, since k′ = 2k − 2, (15) (In the case of k = 2 the spins would we sitting in the vertices and the interactions would be through the edges; however, the argument still holds true: applying the merge rule along an edge simply creates more 2–body interactions). aa b b cc dd ff ii jj Jf ′ =∞ 22 Jdabfij 33Jcfij = FIG. 4: Once we set Jf =∞ it is arbitrary to choose in what direction this face is merged. Here, sc is chosen to be the dependent variable, and thus f is merged downwards. Deletion rule. This rule is obtained by setting Jf = 0, that is, by deleting the interaction at face f (Fig. ??). Note that this corresponds to projecting the face f onto the state |+〉 = |0〉+ |1〉, i.e. |αf (Jf = 0)〉 = |+〉. aa bb cc dd ee gg hh Jf = 0 JbeghJbegh = FIG. 5: Deletion rule. Setting Jf = 0 deletes the interaction in that face. C. Method to obtain general n−body interactions Here we show that a totally general interaction be- tween n 2–level particles can be generated if all k– body Ising–type interactions between these n particles are available, for any subset of k particles, and all k = 0, 1, . . . , n. An interaction pattern between n par- ticles with all possible k–body interactions is called a k–clique. We coin the term superclique for an interaction pattern between n particles containing all k–cliques, for all k = 0, 1, 2, . . . , n [? ]. A “superclique of Ising–type in- teractions” is a superclique such that all its interactions are Ising–type; in this work, when we refer to a super- clique, we will mean this kind of superclique. Hence, we claim that a totally general interaction between n particles can be generated by preparing a superclique of Ising–type interactions among them, and tuning its cou- pling strengths appropriately. In order to prove the claim, first note that a general interaction between n spins corresponds to assigning a different energy λs to each spin configuration s. Let us indicate with a subindex on the coupling strength which particles participate in a given interaction of the super- clique; e.g. J123 is the coupling strength of the 3–body interaction between s1, s2 and s3. Hence, we need to show that the coupling strengths in the superclique can Fixing the spins using the gauge symmetry: No loops! Deletion rule: Merge rule: Jbegh Jadcegh a c d e = a b c d e b g h g h Jf =∞ sb = sa + sc + sd Co pleteness of the 4D     LGTZ2 10 cializes to a general n–body interaction. Note that here the dependence on r1 and r2 also cancels, since the large blue face depends on each of them twice (and the sum is mod 2, thus r1 + r1 = 0, and similarly for r2). 4–body interactions can be generated similarly. In this case, the four logical particles are distributed close to each other as shown in Fig. ??, and all cover faces are merged to give rise to the Ising–type interaction J1234(−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 ??). s1 s2 s3 s4 r1 r2 r3 J1234 FIG. 9: 4–body Ising–type interaction between spins s1, s2, s3 and s4 with coupling strength J1234 . See the caption of Fig. ?? for an explanation of the symbols. s1 s2 s3 s4 s5 r1 r2 r3 r4 J12345 FIG. 10: 5–body Ising–type interaction J12345(−1) s1+s2+s3+s4+s5 . See the caption of Fig. ?? for an explanation of the symbols. The generalization to k–body Ising–type interactions, for arbitrary k, is straightforward. First, one propagates each of the “logical spins” s1, . . . , sk in the lattice un- til they are as close to each other as possible, forming a “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 as adding more logical particles on the right of the 5–body interaction of Fig. ??, thereby enlarging the “rectangle” in length, until one has k logical particles, analogously to how particles have been “added” in the generation of the 5–body interaction when compared with a 3– or 4–body 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 , where the coupling J1...k is 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 merged face depends on them twice. The coupling strengths J1...k will be tuned so that the Hamilton function of the super- clique equals the Hamilton function of the specific final model (which we will refer to as the “target” model), according to Eq. (??). Thus, we have shown how to obtain k−body Ising– type interactions, for any k = 1, . . . , n. Now we must let each spin participate in 2n−1 interactions, as pointed out in (??). However, we have seen that a spin propagates as in Fig. ??, and this propagation ends in a certain face (called an “end”) that participates in a k–body interac- tion. There it is clear that spin s1 can only participate in two interactions, corresponding to the left and right ends. More generally, the number of ends that an object (or en- coded particle) of dimension de in a lattice of dimension d has are 2(d − de). Here the logical spin is never prop- agated alone, but always “carries” the other three spins of an adjacent face fixed (i.e. the shape of Fig. ??(a) is propagated), hence we essentially have de = 2. So, for 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 pro- cedure can be multiply applied until the particle has 2n−1 ends, that is, one end for each interaction. Note that in this replication procedure no loops of spins fixed by the gauge are formed. s3 s2 s1 s4s5 s6 s7 s9s8 r6 r3 r2 r1 r4 r5 r7 r8 FIG. 11: Replication of spins in a 4D lattice: s1 is replicated into s3, s5, s6, s8, s9. Yellow faces have the same meaning as blue faces, that is, s2 propagates into s3 by the same means as it propagates into s7. Note that no loops of red spins are formed. We remark that all faces which are not mentioned in this construction have to be deleted using the deletion rule. We also mention that we have tried several other procedures in order to obtain this result in 3D, but none of them could avoid the formation of loops of edges fixed by the gauge. The specific layout of interactions in the superclique is the following. The logical particles are distributed along 4-body 10 cializes to a general n–body interaction. Note that here the dependence on r1 and r2 also cancels, since the large blue face depends on each of them twice (and the sum is mod 2, thus r1 + r1 = 0, and similarly for r2). 4–body interactions can be generated similarly. In this case, the four logical particles are distributed close to each other as shown in Fig. ??, and all cover faces are merged to give rise to the Ising–type interaction J1234(−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 ??). s1 s2 s3 s4 r1 r2 r3 J1234 FIG. 9: 4–body Ising–type interaction between spins s1, s2, s3 and s4 with coupling strength J1234 . See the caption of Fig. ?? for an explanation of the symbols. s1 s2 s3 s4 s5 r1 r2 r3 r4 J12345 FIG. 10: 5–body Ising–type interaction J12345(−1) s1+s2+s3+s4+s5 . See the caption of Fig. ?? for an explanation of the symbols. The generalization to k–body Ising–type interactions, for arbitrary k, is straightforward. First, one propagates each of the “logical spins” s1, . . . , sk in the lattice un- til they are as close to each other as possible, forming a “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 as adding more logical particles on the right of the 5–body interaction of Fig. ??, thereby enlarging the “rectangle” in length, until one has k logical particles, analogously to how particles have been “added” in the generation of the 5–body interaction when compared with a 3– or 4–body 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 , where the coupling J1...k is 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 merged face depends on them twice. The coupling strengths J1...k will be tuned so that the Hamilton function of the super- clique equals the Hamilton functio of the specific final model (which we will refer to as the “target” model), according to Eq. (??). Thus, we have shown how to obtain k−body Ising– type interactions, for any k = 1, . . . , n. Now we must let each spin participate in 2n−1 interactions, as pointed out in (??). However, we have seen that a spin propagates as in Fig. ??, and this propagation ends in a certain face (called an “end”) that participates in a k–body interac- tion. There it is clear that spin s1 can only participate in two interactions, corresponding to the left and right ends. More generally, the number of ends that an object (or en- coded particle) of dimension de in a lattice of dimension d has are 2(d − de). Here the logical spin is never prop- agated alone, but always “carries” the other three spins of an adjacent face fixed (i.e. the shape of Fig. ??(a) is propagated), hence we essentially have de = 2. So, for 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 pro- cedure can be multiply applied until the particle has 2n−1 e ds, that is, one end for each interaction. Note that in this replication procedure no loops of spins fixed by the gauge are formed. s3 s2 s1 s4s5 s6 s7 s9s8 r6 r3 r2 r1 r4 r5 r7 r8 FIG. 11: Replication of spins in a 4D lattice: s1 is replicated into s3, s5, s6, s8, s9. Yellow faces have the same meaning as blue faces, that is, s2 propagates into s3 by the same means as it propagates into s7. Note that no loops of red spins are formed. We remark that all faces which are not mentioned in this construction have to be deleted using the deletion rule. We also mention that we have tried several other procedures in order to obtain this result in 3D, but none of them could avoid the formation of loops of edges fixed by the gauge. The specific layout of interactions in the superclique is the following. The logical particles are distributed along 5-body Construction of many-body Ising-type int.: ... 2-body Xn k¼0 n k ! " ¼ 2n J’s (columns), and 2n !s’s (rows). But by construction all rows are linearly independent; hence, it has a nonzero determinant, and thus it is invertible. 2.4. Explicit construction.—We now use the tools of Sect. 2.2 in order to show that we can obtain all interactions required in Sect. 2.3 in a 4DZ2 LGT. The proof will require fixing some spins using the gauge symmetry of the model (i.e., fixing them to zero while leaving the Hamilton func- tion invariant), a technique which can be applied as long as the edges whose spins are fixed form at most a maximal tree (i.e., do not form a closed loop) [11]. First, a ‘‘single-body interaction’’ of s1 (analogous to a magnetic field) is obtained by letting s1 interact with all other spins around a face fixed by the gauge [Fig. 2(a)]. A two-body interaction is obtained by merging the front, lower and back face and creating the face with blue boundaries of Fig. 2(b). By fixing with the gauge six of the spins at the boundary of the blue face, this face depends only on s1 þ s2 þ rþ r ¼ s1 þ s2 (since the sum is mod 2) [see Fig. 2(b)]. Thus, this effectively corresponds to a two-body Ising-type interaction between s1 and s2 with an interaction strength J12. Notice that by setting J12 ¼ 1 as well, we force s1 þ s2 ¼ 0, which can be seen as a propagation of s1 into s2 (since s1 ¼ s2). A concatenated application 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 three spins s1, s2, s3 close to each other and then merging the large blue face as indicated in Fig. 2(c). The interaction in the blue face corresponds to a three-body Ising-type inter- action between s1, s2 and s3 ( ince r1 and r2 are summed twice) and with an interaction strength J123. The generalization to k-body interactions with k # 4 can be done in a similar way as in Fig. 2(c). The spins sj taking place in the final k-body interaction are never ad- jacent, and each of them is part f a face at the front, back or side with three spins fixed by the gauge (red u shapes). All but one of the remaining faces are merged, and the interaction strength J1...k in that face determines the k-body Ising-type interaction. Thus we have shown how to obtain k-body Ising-type interactions between any group of k particles, for k ¼ 1; . . . ; n (the zero-body interaction required in 2.3 is a constant factor, so we obtain Z up to this factor). Since the total number of interactions is 2n, we only need to show that a given spin can participate in 2n=n interactions. This means that each spin must have this number of ‘‘end faces’’, i.e., faces at the end of a propagation that partici- pate in a (many-body) interaction. For example, if we use Fig. 2(b) to propagate s1 (i.e. we set J12 ¼ 1), then s1 has two end faces, the left and the right one, each of which can participate in, say, a three-body interaction like the one shown in Fig. 2(c). But, as can be seen from Fig. 2(b), the propagation of a particle (in 3D) essentially behaves as a ‘‘pipe’’ which has only two end faces. In fact, the number of ends that an encoded particle of dimension de in a lattice of dimension d can have are 2ðd% deÞ. Here we essentially have de ¼ 2, and thus for d ¼ 3 the particle is blocked to have only 2 ends. We need to resort to a 4D lattice in order to obtain 2ðd% deÞ> 2 ends, and then this replication in different directions can be multiply applied until the par- ticle has 2n=n ends (see Fig. 3 for a replication of one spin s1 into three other ‘‘end faces’’ s3, s5 and s6). We refer the reader to [12] for the detailed construction. We remark that all faces which are not mentioned in this construction have to be deleted using the deletion rule. We also mention that we have tried several other procedures to obtain this result in 3D, but none of them could avoid the formation of loops of edges fixed by the gauge. This proves that we can generate a totally general n-body interaction between n particles in a 4D Z2 LGT. This includes all classical spin models with q ¼ 2 in arbitrary dimensions d, arbitrary graphs, and arbitrary interaction pattern. Moreover, by encoding a q-level par- ticle in mq ¼ dlogqe two-level particles, this also includes general interactions bet een n0 q-level particles, with n0 ¼ n=mq. This proves that the 4D Z2 LGT is complete for all Abelian discrete classical spin models, including all Abelian discrete LGTs and discrete SSMs. 2.5. Approximate completeness for Abelian continuous LGTs and continuous SSMs.—We can go further and show that the 4D Z2 LGT is also approximately complete for Abelian c ntinuous models, that is, the partition function of a continuous model can be xpressed, up to certain accuracy, as a specific instance of the partition function of the 4D Z2 LGT. To see this, we just need to let q ! 1 (the lattice spacing remaining discrete) and determine what approximation can be obtained (see below). 2.6. Efficiency results.—The construction presented above enables one to generate, from a 4D Z2 LGT, Hamilton functions that contain M terms with at most k-body interactions with an overhead that scales poly(M, 2k) for q ¼ 2. In the case of q-state models withM general k0-body interaction terms, at most 2k0mq Ising-type inter- actions between k0mq two-level particles are required for each term. Therefore, the overhead in the system size of the FIG. 2 (color online). Spins fixed by the gauge are marked in red. A single-body, a two-body and a three-body Ising-type interaction with coupling strengths J1, J12, and J123 ar hown in (a), (b), and (c), respectively. PRL 102, 230502 (2009) P HY S I CA L R EV I EW LE T T E R S week ending 12 JUNE 2009 230502-3 3-body Xn k¼0 n k ! " ¼ 2n J’s (columns), and 2n !s’s (rows). But by construction all rows are linearly independent; hence, it has a nonzero determinant, and thus it is invertible. 2.4. Explicit construction.—We now use the tools of Sect. 2.2 in order to show that we can obtain all interactions required in Sect. 2.3 in a 4DZ2 LGT. The proof will require fixing some spins using the gauge symmetry of the model (i.e., fixing them to zero while leaving the Hamilton func- tion invariant), a technique which can be applied as long as the edges whose spins are fixed form at most a maximal tree (i.e., do not form a closed loop) [11]. First, a ‘‘single-body interaction’’ of s1 (analogous to a magnetic field) is obtained by letting s1 interact with all other spins around a face fixed by the gauge [Fig. 2(a)]. A two-body interaction is obtained by merging the front, lower and back face and creating the face with blue boundaries of Fig. 2(b). By fixing with the gauge six of the spins at the boundary of the blue face, this face depends only on s1 þ s2 rþ r ¼ s1 þ s2 (since the sum is mod 2) [see Fig. 2(b)]. Thus, this effectively corresponds to a two-body Ising-type interactio between s1 and s2 with an i teraction strengt J12. Notice that by setting J12 ¼ 1 as well, we force s1 þ s2 ¼ 0, which can be seen as a propagation of s1 into s2 (since s1 ¼ s2). A concatenated application of this two-body in eraction r sults in an effec- tive propaga ion of a spin throug a c rtai path (the turn- ings of the path can be done similarly). A hree-body interaction is obtained by bringing three spins s1, s2, s3 close to each oth a d n merging the large blue face as indicated in Fig. 2(c). The interaction i the blue face corresponds to a three-body Ising-type i ter- action between 1, s2 a d s3 (since r1 and r2 are summed wice) and w th an i teraction strength J123. The generalizatio to k-body interactions with k # 4 can be done in a imilar way as in Fig. 2(c). The spins sj taking pl ce in the final k-body int raction are never ad- jacent, and each of t m is part o a face at the front, back or side with three spins fixed by the g uge (red u shapes). All but one of the remaining faces are merged, and the i teraction strength J1...k in that face determines the k-body Ising-type interaction. Thus we have shown how to obtain k-body Ising-type interactions between any group of k particles, for k ¼ 1; . . . ; n (the zero-body interaction required in 2.3 is a constant factor, so we obtain Z up to this factor). Since the total number of i teractions is 2n, we only need to show that a given spin can participate in 2n=n interactions. This means that each spin must have this number of ‘‘end faces’’, i.e., faces at the end of a propagation that partici- pate in a (many-body) interaction. For example, if we use Fig. 2(b) to propagate s1 (i.e. we set J12 ¼ 1), then s1 has two end faces, the left and the right one, each of which can participate in, say, a three-body interaction like the one shown in Fig. 2(c). But, as can be seen from Fig. 2(b), the propagation of a particle (in 3D) essentially behaves as a ‘‘pipe’’ which has only two end faces. In fact, the number of ends that an encoded particle of dimension de in a lattice of dimension d can have are 2ðd% deÞ. Here we essentially have de ¼ 2, and thus for d ¼ 3 the particle is blocked to have only 2 ends. We need to resort to a 4D lattice in order to obtain 2ðd% deÞ> 2 ends, and then this replication in different directions can be multiply applied until the par- ticle has 2n=n ends (see Fig. 3 for a replication of one spin s1 into three other ‘‘end faces’’ s3, s5 and s6). We refer the reader to [12] for the detailed construction. We remark that all faces which are not mentioned in this construction have to be d leted using the d leti n rule. We lso mention that we h ve tried sev ral other procedures to obtain this result in 3D, but none of them could avoid the formation of loops of edges fix d by the gauge. This proves that w can generate a totally general n-body int raction between n particles in a 4D Z2 LGT. This includes all classical spin models with q ¼ 2 in arbitrary dimensions d, arbitrary graphs, and arbitrary interaction pattern. Moreover, by ncoding a q-level par- ticle in mq ¼ dlogqe two-level part cles, this also includes ge eral interactions b tween n0 q-level particles, with n0 ¼ n=mq. This proves that the 4D Z2 LGT is complete for all Abelia discrete classical spin m dels, including all Abelian discrete LGTs and discrete SSMs. 2.5. Ap roximate compl teness for Abelian continuous LGTs and continuous SSMs.—We can go further and show that the 4D Z2 LGT is also approximately complete for Abel an continuous m dels, hat is, the partition function of a continuous model can be expressed, up to a certain accuracy, as a specific instance of the partition function of the 4D Z2 LGT. To see this, we just need to let q ! 1 (the lattice sp cing r maining discrete) and determ ne what approximation can be obtained (see b low). 2.6. Efficiency results.—The construction presented above enables one to generate, from a 4D Z2 LGT, Hamilton functi ns that contain M terms with at most k-body interactions with an overhead that scales poly(M, 2k) for q ¼ 2. In the case of q-state models withM general k0-body interaction terms, at most 2k0mq Ising-type inter- actions between k0mq two-level particles are required for each term. Therefore, the overhead in the system size of the FIG. 2 (color online). Spins fixed by the gau e are marked in red. A single-body, a two-body and a three-body Ising-typ interaction with coupling strengths J1, J12, and J123 are shown in (a), (b), and (c), respectively. PRL 102, 230502 (2009) P HY S I CA L R EV I EW LE T T E R S week ending 12 JUNE 2009 230502-3 1-body Xn k¼0 n k ! " ¼ 2n J’s (columns), and 2n !s’s (rows). But by construction all rows are linearly independent; he ce, it has a nonzero determinant, and thus it is invertible. 2.4. Explicit construction.—We now use the tools of Sect. 2.2 in order to show that we can obtain all interactions required in Sect. 2.3 in a 4DZ2 LGT. The proof will require fixing some spins using th gauge symmetry of the model (i.e., fixing them to zero while leaving the Hamilton func- tion invariant), a technique which can be applied as long as the edges whose spins are fixed form at most a maximal tree (i.e., do not form a closed lo p) [11]. First, a ‘‘single-body interaction’’ of s1 (anal gous to a magnetic field) is obtained by letting s1 interact with all other spins around a face fix d by the gauge [Fig. 2(a)]. A two-body interaction is obtained by merging the front, lower and back face and creating the face with blue boundaries of Fig. 2(b). By fixing with the gauge six of the spins at the boundary of the blue face, this face depends only on s1 þ s2 þ rþ r ¼ s1 þ s2 (since the sum is mod 2) [see Fig. 2(b)]. Thus, this ffectively corresponds to a two-body Ising-type interact on betw en s1 nd s2 with an interaction strength J12. Notice that by setting J12 ¼ 1 as well, we force s1 þ s2 ¼ 0, which can be seen as a propagation of s1 into s2 (since s1 ¼ s2). A concatenated application 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 three spins s1, s2, s3 close to e ch other a d the merging the large blue face as indicated in Fig. 2(c). The int ract on in the blue face corresponds to a three-body Ising-type i ter- action between s1, s2 and s3 (since r1 and r2 are summed twice) and with an interaction strength J123. The generalization to k-body interactions with k # 4 can be done in a similar way as in Fig. 2(c). The spins sj taking place in the final k-body interaction are never ad- jacent, and each of them is part of face at the front, back or side with three spins fixed by the g uge (red u pes). All but one of the remaining faces are merged, and the interaction strength J1...k in that face determines the k-body Ising-type interaction. Thus we have shown how to obtain k-body Ising-type interactions between any group of k particles, for k ¼ 1; . . . ; n (the zero-body interaction required in 2.3 is a constant factor, so we obtain Z up to this factor). Since the total number of interactions is 2n, we only need to show that a given spin can participate in 2n=n i teractions. This means that each spi must hav this number of ‘‘end faces’’, i.e., faces at the end of a propagation that partici- pate in a (m y-body) interaction. For example, if we use Fig. 2(b) to propagate s1 (i. . we set J12 ¼ 1), th n s1 has tw end faces, the left and the right one, each of which can participate in, say, a three-body interaction like the one shown in Fig. 2(c). But, as can be seen from Fig. 2(b), the propagation of a particle in 3D) essentially behav s as a ‘‘pipe’’ which has only two end fac s. In fact, the number of ends that an encoded particle of dimension de in a lattice of dimen ion d can have are 2ðd% deÞ. Here we essentially have de ¼ 2, nd thus for d ¼ 3 the particle is lock d to have only 2 ends. We need to resort to a 4D lattice in order to obtain 2ðd% deÞ> 2 ends, and then this replication in different directions can be multiply applied until the par- ticle has 2n=n ends (see Fig. 3 for a replication of one spin s1 into three other ‘‘end faces’’ s3, s5 and s6). We refer the reader to [12] f r the etailed constructio . We remark that all faces which are not mentioned i thi construction have to be deleted using the deletion rule. We lso mention that we have tried several other procedures to obtain this result in 3D, but none of them could avoid the formation of loops of edges fixed by the gauge. This proves that we can generate a totally general n-body interaction between n particles in a 4D Z2 LGT. This includes all classical spin models with q ¼ 2 in arbitrary dimensions d, arbi rary g aph , and bitrary int raction pattern. Moreover, by encoding q-level par- ticle in mq ¼ dlogqe two-level particles, this also includes general interactions between n0 q-level particles, with n0 ¼ n=mq. This proves that the 4D Z2 LGT is complete for all Abelian discrete classical spin models, including all Abelian discrete LGTs and discrete SSMs. 2.5. Approximate completeness for Abelian continuous LGTs and continu us SSMs.—W c n g furth r and show that the 4D Z2 LGT is also approxim tely complete f r Ab lian continuous models, that is, the part tion function of a continuous model can be expressed, up to a certain accuracy, as a specific instance of the partition function of the 4D Z2 LGT. To see this, we just need to l t q ! 1 (the lattice spacing re aining discrete) and determine what approximation can be obtaine (see below). 2.6. Efficiency results.—The onstru tion pres ted above enables on t generate, from a 4D Z2 LGT, Hamilto functions that c tai M terms wi h at most k-body interactions with an overhead that scales poly(M, 2k) for q ¼ 2. In the case of q-state models withM general k0-bo interaction t rms, at most 2k0mq Ising-type inter- actions between k0mq two-level particles are required for e ch term. T erefore, the overhead in the system size of the FIG. 2 (color online). Spins fixed by the gauge are mark d in red. A single-body, a two-body and a three-body Ising-type interaction with coupling strengths J1, J12, and J123 are shown in (a), (b), and (c), respectively. PRL 102, 230502 (2009) P HY S I CA L R EV I EW LE T T E R S week ending 12 JUNE 2009 230502-3  Construction of the superclique J1(−1) 1 J12(−1) s1+s2 J123(−1) s1+s2+s3 J1234(−1) s1+s2+s3+s4 J12345(−1) s1+s2+s3+s4+s5 Compl te es  of h  4D     LGTZ2 9the Hamilton function of a totally general interaction of n 2–level particles (e.g. including complicated many– body interactions, etc) equals the Hamilton function of a complicated interaction pattern (a superclique), but with simple interactions (Ising–type interactions). This map- ping may have applications in the Hamiltonian formula- tion of LGTs [? ] and in their renormalization group analysis [? ]. D. Explicit construction of the superclique In the following we show that we can construct a su- perclique of Ising–type interactions from a 4D Z2 LGT. Because of the result of the previous section, this means that, by tuning the coupling strengths of the Ising–type interactions in the superclique, this model can specialize to any other (Abelian, discrete) classical spin model. In order to generate the superclique starting from the 4D Z2 LGT we will only make use of the merge and deletion rule, and of the gauge fixing. We will first show the generation of k–body Ising–type interactions, for any k = 1, . . . , n in a 3D Z2 LGT. Then we will argue that the fourth dimension is needed to repli- cate the spins, and thereby let each spin participate in all the interactions required in the superclique. First, a “single–body” Ising–type interaction of s1 (analogous to a magnetic field), i.e. J1(−1)s1 , is obtained by letting s1 interact with all other spins around a face fixed by the gauge (see Fig. ??(a)). s1 s1 s2 s1 s2 s3 r r1 r2 (a) (b) (c) J1 J12 J123 FIG. 6: “Logical” spins (i.e. the spins that will participate in the final superclique) are marked in bold black. Blue shaded faces indicate merged faces as in Fig. ??, and spins fixed by the gauge are marked in red. Figures (a), (b) and (c) show a single–body, a 2–body and a 3–body Ising–type interaction with coupling strengths J1, J12 and J123 respectively. Spin r does not participate in the interaction because the blue face depends on them twice, i.e. r+ r = 0, and the same holds for r1 and r2. A 2–body Ising–type interaction is obtained by con- catenating the merge rule on the front, lower and back face of a cube and creating the face with blue boundaries of Fig. ??(b). This face depends on all of the spins at its boundary (i.e. all spins which are attached to the thick, blue line in Fig. ??(b), e.g. the upper, right, and left spins on the front face, the lateral spins on the lower face, etc). However, six of these spins are fixed by the gauge (red spins in Fig. ??(b)), that is, their value is fixed to zero. Hence, the big blue face only depends on the spins which are not fixed, that is on s1 + s2 + r + r = s1 + s2 (since the sum is performed mod 2). This corresponds to the 2–body Ising–type interaction between s1 and s2 with coupling strength determined by the only face which has not been merged (the upper face), viz. J12(−1)s1+s2 . Furthermore, notice that by setting J12 =∞ as well, one enforces s1 + s2 = 0, i.e. s1 = s2. This can be seen as a “propagation” of the value of s1 into s2. A concate- nated application of this 2–body interaction results in an effective propagation of a spin through a certain path in the lattice (see Fig. ??). The direction of this propaga- tion can be changed by merging all “covering” faces be- tween the incoming and the outgoing spin, as indicated in Fig. ??. This will be important in the construction of the superclique, where one needs to propagate logical particles in the 4D lattice to bring to the place where the interaction occurs. s1 s2 s3 r1 r2 FIG. 7: Propagation of a s1 to s3 by concatenating 2–body interactions with J12 =∞. Particle s1 has two ends (i.e. faces that can participate in a k–body interaction): itself, and the right face where s3 is. s1 s1 s2 s2 r r (a) (b) FIG. 8: (a) Turn in the path from a left–to–right propagation (“incoming” spin s1) to a down–to–up propagation (“outgo- ing” spin s2). (b) Similar turn, but here s2 propagates from back to front. The dependence of each blue face on r cancels because it depends twice on it. In order to generate a 3–body Ising–type interaction, one propagates three “logical” spins in the lattice in order to bring as close to each other as possible, with the con- dition that their “red u–shapes” are not adjacent. Then ones merges all but one of the “cover” faces into a large blue face as indicated in Fig. ??(c). This blue face now contains the interaction J123(−1)s1+s2+s3 , that is, a 3– body Ising–type interaction between s1, s2 and s3 as re- quired. The interaction strength J123 is determined by the only face that has not been merged, and it is this parameter that will be tuned so that the superclique spe- Propagation 9 the Hamilton function of a totally general interaction of n 2–level particles (e.g. including complicated many– body interactions, etc) equals the Hamilton function of a complicated interaction pattern (a superclique), but with simple interactions (Ising–type interactions). This map- ping may have applications in the Hamiltonian formula- tion of LGTs [? ] and in their renormalization group analysis [? ]. D. Explicit construction of the superclique In the following we show that we can construct a su- perclique of Ising–type interactions from a 4D Z2 LGT. Because of the result of the previous section, this means that, by tuning the coupling strengths of the Ising–type interactions in the superclique, this model can specialize to any other (Abelian, discrete) classical spin model. In order to generate the superclique starting from the 4D Z2 LGT we will only make use of the merge and deletion rule, and of the gauge fixing. We will first show the generation of k–body Ising–type interactions, for any k = 1, . . . , n in a 3D Z2 LGT. Then we will argue that the fourth dimension is needed to repli- cate the spins, and thereby let each spin participate in all the interactions required in the superclique. First, a “single–body” Ising–type interaction of s1 (analogous to a magnetic field), i.e. J1(−1)s1 , is obtained by letting s1 interact with all other spins around a face fixed by the gauge (see Fig. ??(a)). s1 s1 s2 s1 s2 s3 r r1 r2 (a) (b) (c) J1 J12 J123 FIG. 6: “Logical” spins (i.e. the spins that will participate in the final superclique) are marked in bold black. Blue shaded faces indicate merged faces as in Fig. ??, and spins fixed by the gauge are marked in red. Figures (a), (b) and (c) show a single–body, a 2–body and a 3–body Ising–type interaction with coupling strengths J1, J12 and J123 respectively. Spin r does not participate in the interaction because the blue face depends on them twice, i.e. r+ r = 0, and the same holds for r1 and r2. A 2–body Ising–type interaction is obtained by con- catenating the merge rule on the fron , lower and back face of a cube and creating the fa e with blue boundaries of Fig. ??(b). This face depe ds on all of the spins at its boundary (i.e. all spins which are attached to the thick, blue line in Fig. ??(b), e.g. the upper, right, and left spins on the front face, the lateral pins on the lower face, etc). However, six of hese spins are fix d by the gauge (red spins in Fig. ??(b)), that is, their value is fixed to zero. Hence, the big blue face only depends on the spins which are not fixed, that is on s1 + s2 + r + r = s1 + s2 (since the sum is performed mod 2). This corresponds to the 2–body Ising–type interaction between s1 and s2 with coupling strength determined by the only face which has not been merged (the upper face), viz. J12(−1)s1+s2 . Furthermore, notice that by setting J12 =∞ as well, one enforces s1 + s2 = 0, i.e. s1 = s2. This can be seen as a “propagation” of the v lue f s1 into s2. A concate- nated application of this 2–body interaction results in an effective propagation of a spin through a certain path in the lattice (see Fig. ??). The direction of this propaga- tion can be changed by merging all “covering” faces be- tween the incoming and the outgoing spin, as indicated in Fig. ??. This will be important in the construction of the superclique, where one needs to propagate logical particles in the 4D lattice to bring to the place where the interaction occurs. s1 s2 s3 r1 r2 FIG. 7: Propagation of a s1 to s3 by concatenating 2–body interactions with J12 =∞. Particle s1 ha two ends (i.e. faces that can participate in a k–body interaction): itself, and the right face where s3 is. s1 s1 s2 s2 r r (a) (b) FIG. 8: (a) Turn in the path from a left–to–right propagation (“incoming” spin s1) to a down–to–up propagation (“outgo- ing” spin s2). (b) Similar turn, but here s2 propagates from back to front. The dependence of each blue face on r cancels because t d pends twice on it. In order to generate a 3–body Ising–type inter ction, one propagates three “l gical s s in the lattice in order to bring as close to each other as possible, with the con- dition that th ir “red u–shapes” are not adjacent. Then ones merges all but one of the “cover” faces into a large blue face as indicated in Fig. ??(c). This blue face now contains the interaction J123(−1)s1+s2+s3 , that is, a 3– body Ising–type interaction between s1, s2 and s3 a re- quired. The interaction strength J123 is de ermined by th only f ce that has not been me ged, and it is this parameter that will b tuned so that the superclique spe- Turns Transportation in the 4D latti e: 10 cializes to a general n–body interaction. Note that here the dependence on r1 and r2 also cancels, since the large blue face depends on each of them twice (and the sum is mod 2, thus r1 + r1 = 0, and similarly for r2). 4–body interactions can be generated similarly. In this case, the four logical particles re distributed close each ot er as shown in Fig. ??, and all cover faces are merged to give rise to the Ising–type interaction J1234(−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 ??). s1 s2 s3 s4 r1 r2 r3 J1234 FIG. 9: 4–body Ising–type interaction between spi s s1, s2, s3 and s4 with coupling st ength J1234 . Se the caption of Fig. ?? for an explanation of the symbols. s1 s2 s3 s4 s5 r1 r2 r3 r4 J12345 FIG. 10: 5–body Ising–type interaction J12345(−1) s1+s2+s3+s4+s5 . See the caption of Fig. ?? for an explanation of the symbols. The generalization to k–body Ising–type interactions, for arbitrary k, is straightforward. First, one propagates each of the “logical spins” s1, . . . , sk in the lattice un- til they are as close to each other as possible, forming a “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 as adding more logical particles on the right of the 5–body interaction of Fig. ??, thereby enlarging the “rectangle” in length, until ne has k logical p rticles, analogously to how particles have been “added” in th generation of the 5–body i teraction when compared with a 3– or 4–bo y 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 , where the coupling J1...k is deter- mined by the only cover face that has not been merged. The dependence on all auxiliary spins r1, r2, . . . will can- cel b caus , by const uction, the boundary of t e merged f ce depen s on them twice. The coupling strengths J1...k will be tuned so that th Hamilton function of the super- clique equals the Hamilton function of the specific final model (which we will refer to as the “target” model), according to Eq. (??). Thus, we have shown how to obtain k−body Ising– type interactions, for any k = 1, . . . , n. Now we must let each spin participate in 2n−1 interactions, as pointed out in (??). However, we have seen that a spin propagates as in Fig. ??, and this propagation ends in a certain face (called an “end”) that participates in a k–body interac- tion. There it is clear that spin s1 can only participate in two interactions, corresponding to the left and right ends. More generally, the number of ends that an object (or en- coded particle) of dimension de in a lattice of dimension d has are 2(d − de). Here the logical spin is never prop- agated alone, but always “carries” the other three spins of an adjacent face fixed (i.e. the shape of Fig. ??(a) is propagated), hence we essentially have de = 2. So, for 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 pro- cedure can be multiply applied until the particle has 2n−1 ends, that is, one end for each interaction. Note that in this replication procedure no loops of spins fixed by the gauge are formed. s3 s2 s1 s4s5 s6 s7 s9s8 r6 r3 r2 r1 r4 r5 r7 r8 FIG. 11: Replication of spins in a 4D lattice: s1 is replicated into s3, s5, s6, s8, s9. Yellow faces have the same meaning as blue faces, that is, s2 propagates into s3 by the same means as it propagates into s7. Note that no loops of red spins are formed. We remark that all faces which are not mentioned in this construction have to be deleted using the deletion rule. We also mention that we have tried several other procedures in order to obtain this result in 3D, but none of them could avoid the formation of loops of edges fixed by the gauge. The specific layout of interactions in the superclique is the following. The logical particles are distributed along Replication 4th dimension required to avoid loops!  Construction of the sup rcl que Complet ess of th  4D     LGTZ2 11 the x direction with one “idle” space among them (see Fig. ??). Then each of them is propagated in the y di- rection. The idea is to use this 3D space (i.e. the space with w = 0) to propagate the particles, and to use the 3D space defined by w = 1 to create the interactions required for the superclique. For example, in Fig. ?? we see 3 logical particles along the x direction which are propagated in the y direction. Then, at some sites, they are also propagated to the space defined by w = 1. In particular, in the first site, they are all propagated to w = 1, where the 1–body interaction of each of the particles will take place. In the following site, s1 and s2 are propagated to w = 1, in order to gener- ate the 2–body interaction among them. After some idle propagation in the y direction (precisely, A(2) idle sites, as will be explained below), s1 and s3 are propagated to the space w = 1, where they will generate a 2–body interaction among them. This goes on for all 2–body in- teractions, then for all 3–body interactions, 4–body, and so on, up to the n–body interaction. For example, the 4– body interaction between s1, s2, s3, s4 and then between s1, s2, s3, s5 are shown in Figs. ??, ??. ... ... ... ... ..... . s1 s1s1 s1s1 s2 s2 s2s2s2 s3 s3 s3s3 s3 x y z w sis1, s2s1, s3 A(2) FIG. 12: 3D space with w = 0. Logical particles are dis- tributed along the x direction and they are propagated along the y direction. Note that the idle space one has to leave in the y direc- tion among each propagation to the w = 1 space depends on k. This is because, when the k particles are propa- gated to the w = 1 space, they are distributed in a line. There, one has to rearrange them in the rectangular form explained in Figs. ??, ??. It follows from the construction that this rearrangement requires to leave space A(k) = 2!k/4"+ 2 ∼ k (26) between interactions. An overall layout of the propaga- tion of particles in the w = 0 space is shown in Fig. ??. Finally, note that, as indicated in Fig. ??, one requires a 4D lattice of size (x, y, z, w) = (2n, n∑ k=0 A(k) ( n k ) , 1, 1) ∼ 2n (27) s1 s1 s2 s3 s4 s4 J1234 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). s1 s1 s2 s2 s3 s3 s4 s5 J1234 J1235 A(4) FIG. 14: View of part of the w = 1 space. First, parti- cles s1, s2, s3, s4 are propagated into this space, and they are brought close to each other (propagations indicated in black arrows) in order to interact in a 4–body interaction with in- teraction strength J1234. After A(4) idle particles in the y direction, particles s1, s2, s3, s5 are propagated into this space and, again, they are brought close to each other to interact in the 4–body interaction with strength J1235 . to generate a superclique of n particles. There is an ex- ponential overhead in the system size since one has to generate an exponential number of interactions. We re- mark that efficient constructions can be found for specific target models, e.g. in Sec. ?? we show that the construc- tion of the 2D Ising model only requires a linear overhead. We also point out that the construction of the 4–clique (i.e. the part of the superclique with 4–body interactions) is the essential ingredient of the mean–field theory that we will construct in Sec. ??. 12 ... ... ... ... ... ... ... ...... ... ... ... ... ... ... ... .. . ... ... s1s1s1 s1s1 s1 s1 s2s2 s2s2 s22 snsn snsn snsn x y z w 2n 1A(2) ` n 2 ´ A(3) ` n 3 ´ A(n) ` n n ´ 1 1 FIG. 15: 3D space with w = 0. Logical particles are dis- tributed along the x direction and they are propagated along the y direction. E. Main result Now we can finally gather the results we have proven in the last sections in order to state our main result. In Sec. ?? we have shown that by setting some coupling strengths to infinity or zero (merge or deletion rule), the partition function of a 4D Z2 LGT can become the parti- tion function of a superclique. Then, in Sec. ??, we have shown that if one tunes the coupling strengths of a su- perclique appropriately, its Hamilton function specializes to a totally general Hamilton function between n 2–level particles, and thus the corresponding partition functions are also equal. Therefore, we have shown that the parti- tion function of an enlarged 4D Z2 LGT with appropriate inhomogeneous coupling strengths can specialize to the partition function of any Hamilton function of n 2–level particles. More specifically, we have seen that, for any classical spin system, there is a subsystem of the com- plete model (the superclique) that behaves like it (when the appropriate coupling strengths are set on it). Let us elaborate on the class of models that are em- braced by this result. First of all, the completeness result holds for models with an arbitrary interaction pattern be- tween these n 2–level particles, which includes • Models in regular lattices in arbitrary dimension; e.g. an 8D Z2 LGT can be mapped to an enlarged 4D Z2 LGT with appropriate inhomogeneous cou- plings; • Models on arbitrary graphs; e.g. a Z2 LGT defined on a complicated, irregular graph (note that usually Abelian discrete LGTs are only defined on hyper- cubic lattices and here a much more general class is considered); • Models with different number of particles partici- pating in the many–body interactions; e.g. models with 6–body interactions can be mapped to the 4D Z2 LGT, which has 4–body interactions. • Models with different types of many–body interac- tions; e.g. models containing more general 4–body interactions (the most general case being to assign a different energy to each of the 16 configurations of the 4 particles) can be mapped to the 4D Z2 LGT, which only contains Ising–type interactions. In the second place, notice that the information of whether the model possesses a global or a local symme- try is also encoded in the Hamilton function. Since all Hamilton functions are included in our result, this means that the completeness result is valid for • Models with local symmetries, i.e. other Abelian discrete LGTs; • Models with global symmetries, i.e. Abelian dis- crete SSMs; e.g. the Ising model or the Potts model can be mapped to a model with local symmetries, the 4D Z2 LGT. We will discuss how models with different types of sym- metries can be mapped to each other in Sec. ??. Furthermore, the completeness result also includes general Hamilton functions between q−level particles, since one just needs to encode each q–level particle in mq = "log q# 2–level particles. Then, a totally general in- teraction between n′ q−level particles is generated with a superclique of n 2–level particles, with n = n′mq. Thus, our result also holds for • Models whose particles have an arbitrary number of levels; e.g. Zq LGTs, which have q–level particles, can be mapped to the 4D Z2 LGT, which has 2– level particles. In conclusion, we have shown that the 4D Z2 LGT is complete for all Abelian discrete classical spin models, including all Abelian discrete LGTs and Abelian discrete SSMs. In symbols, the main result of this work can be summarized as ZAbelian discrete classical(J) = Z4D Z2 LGT(J, J ′) (28) where J is the set of couplings in the target model, and J ′ is the set of couplings in the additional particles of the complete model. F. Efficiency results We have emphasized that all completeness results re- quire a larger, inhomogeneous complete model when com- pared to the target model. Here we investigate how the number of particles in the complete model n′ scales with the number of particles of the target model n. That is, we study how the system size of the complete model increase when the system size of the target model increases. First, we focus on the number of particles participat- ing in interactions in the target Hamilton function. If the target Hamilton function contains at most k−body interactions (and q = 2), in general one needs to generate a superclique of k particles in the 4D Z2 LGT for each of these interactions (because the method of Sec. ?? could Superclique: complicated interaction pattern with simple interactions Layout of the superclique:  Construction of the superclique Comple n ss of the 4D     LGTZ2 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 different energies2n n∑ k=0 ( n k ) = 2 n couplings 3. All rows are linearly independent, thus the determinant is non zero   1 (−1)0 . . . (−1)0+0+...+0 1 (−1)0 . . . (−1)0+0+...+1 ... 1 (−1)1 . . . (−1)1+1+...+1   ︸ ︷︷ ︸ C   J J1 ... J12...n   =   E(s = (0, 0, . . . , 0)) E(s = (0, 0, . . . , 1)) ... E(s = (1, 1, . . . , 1))   !log2 q" 2-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 models 17 s1,1 s1,2 s1,3 s1,4 J1,1;1,2 J1,2;1,3 J1,3;1,4 FIG. 18: Generation of a 1D array of Ising–type interactions: si,j interacts with spin si,j+1 via a 2–body Ising–type interac- tion with coupling strength Ji,j;i,j+1. Arrows indicate propa- gation of the spin according to Fig. ??, and the cubes marked in blue indicate a 2–body interaction according to Fig. ??(b). to construct the 1D array of Fig. ??, we make use of the fourth dimension in order to link them as shown in Fig. ??. The yellow cubes have the same meaning as the blue cubes in Fig. ??, that is, they correspond to 2– body Ising–type interactions. In this manner, spin s1,1 interacts with s2,1 with strength J1,1;2,1, and so on. This completes the construction of the 2D Ising model. s1,1 s1,2 s1,3 s1,4 s2,1 s2,2 s2,3 s2,4 s3,1 s3,2 s3,3 s3,4 x y zw J2,4;3,4 J1,4;2,4 J2,1;3,1 J1,1;2,1 FIG. 19: Construction of the 2D Ising model. Each 1D array interacts with the next one via the fourth dimension, that is, si,j interacts with si+1,j via a yellow face, with interaction strength Ji,j;i+1,j . Every layer for different w corresponds to the 1D array of interactions of Fig. ?? (blue cubes are not shown to avoid overloading). As in Fig. ??, yellow cubes have the same meaning as blue cubes, i.e. 2–body Ising–type interactions. As can be observed in Fig. ??, the construction of a 2D Ising model of size n×m requires a 4D lattice of size (x, y, z, w) = (2n, 4, 1,m), i.e. the scaling is linear in the system size. VI. IMPLICATIONS OF THE MAIN RESULT In this section we will draw two implications of the main result. First, in Sec. ?? we will conclude that com- puting the partition function of 4D Z2 LGT is #P hard; that is, computationally difficult. Then, in Sec. ?? we will argue that our result provides a new method to com- pute the mean–field–theory of a Z2 LGT, which works for finite dimension. A. Computational complexity of 3D and 4D Z2 LGT Our main result implies, in particular, that the parti- tion function of the 2D Ising model with magnetic fields can be expressed as a specific instance of the partition function of the 4D Z2 LGT. The computation of the par- tition function of the 2D Ising model with magnetic fields is a #P–complete problem [? ] –roughly speaking, this means that it is computationally difficult [? ]. Thus, we conclude that computing the partition function of the 4D Z2 LGT in the real parameter regime is #P–hard, i.e. at l ast as hard as the other problem. That is, we have proven that one can map all models to a model which is hard to solve. The construction presented above also gives insight into the complexity of the 3D Z2 LGT. More precisely, in Sec. ?? we saw that a 3D Z2 LGT can prepare mod- els with k–body Ising–type interactions, for any k = 1, . . . , n, as long as as every particle participates in at most two interactions (this was the limitation of the two ends of Fig. ?? that made us move to the 4D lattice). This implies, in particular, that the 3D Z2 LGT must be as hard as any vertex model with q = 2 and k−body Ising–type interactions. On the other hand, using a method introduced in [? ], one can show that approximating the partition func- tion of the 3D Z2 LGT in a certain complex parameter regime with polynomial accuracy is as hard as simulating arbitrary quantum computations, i.e. BQP–complete [? ]. B. Mean–Field Theory The mean–field theory of a model is an approximation to that model where the interaction of a variable with its neighbors is replaced by an interaction of this variable with a mean field. In this manner, the theory is reduced to a 1–body problem, which is useful to gain insight into a theory that is difficult to solve exactly. Thus, there are as many ways to construct a mean–field theory of a model as ways to average over the influence of neighbor- ing variables over a given variable. In SSMs, mean–field theories of SSMs are generally easy to construct. For example, in the Ising model, the Example: 2D Ising model: linear overhead ✓ Comple eness f the 4D     LGTZ2 Note: 2D Ising can magnetize, but LGT cannot  We have proven that: ✓ any dimensions ✓ q-level systems, any q ✓ any many-body int. real Abelian discrete Z4DZ2LGT(J, J ′) = Zany classical spin model(J) constructive global & local symmetries Completeness of the 4D     LGTZ2 Target hamiltonian with M terms and k-body int: scaling  poly(M, 2k) larger Result holds approx for continuous models: let q →∞ Applications of completeness e.g.  2D Ising with fields poly larger #P-hard #P-hard 4D      LGTZ2 Mapping models with poly overhead: infer comput. complexity 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 Symmetries of the states            symmetries of the partition function ZG(J) = 〈α(J)|S|ϕG〉 〈α(J ′)| = ZG(J ′) Computational complexity M. Van den Nest, W. Dür, R. Raussendorf, H. J. Briegel, Phys. Rev. A 80, 052334 (2009) Mapping partition functions to  quantum circuits I Boltzmann weight of each int. Quantum gate, e.g. Contraction of quantum gates = Circuit∏ a w a C Product of interactions Output & Input of circuit R = (sR1 , . . . , s R n ) L = (sL1 , . . . , s L n) |L〉 = |s L 1 〉 . . . |s L n〉 |R〉 = |sR1 〉 . . . |s R n 〉 Left & Right bound. cond. other geometries✓ PBC Z = Tr C✓ Classical spin model Quantum circuit w a = e −βha(s1,s2) W a(12)(12) = ∑ e−βh a(s1,s2)|s1, s2〉〈s1, s2| Z L,R = 〈L|C|R〉 5.. . .. . .. . .. . sL1 sL2 sLn sR1 sR2 sn i j k l wa(si, sj , sk, sl) 〈sL1 | 〈sL2 | 〈sLn | W a(ij)(kl) i j k l |sR1 〉 |sR2 〉 |sRn 〉 time FIG. 1: (Left) In a vertex model, particles (black dots) sit at the edges and interactions (pale red dots) take place in the vertices. (Right) This model is mapped to a quantum circuit, where each interaction becomes a two–qubit gate. This concludes the mapping between matrix elements of quantum circuits and partition functions of classical spin models. In the following we make some remarks regarding this mapping. (i) Note that the quantum gates are specified by the parameters of the classical model, namely by the Boltzmann weights of local interactions. It follows that only in certain parameter regimes, the resulting circuit C is a sequence of unitary quantum gates. (ii) We stress that this mapping can be easily extended to open boundary conditions, i.e. systems where left and right spins are ‘free’ and thus fully summed out in the partition function. This can be eas- ily achieved by replacing the left and right states |L〉 and |R〉 by the state |+〉⊗n, where |+〉 = q−1/2 ∑q i=0 |i〉 is a superposition over all q single spin states. This yields the identity ZOBCvm = qn〈+|⊗nC|+〉⊗n . (12) Further, periodic boundary conditions can also be taken into account by summing over the diagonal matrix elements, which results in ZPBCvm = Tr(C) . (13) (iii) Similarly, one can consider other geometries such as, e.g., vertex models on a 2D tilted triangular lattice [9], where 6–body interactions take place at vertices and the Boltzmann weights can be arranged into q3×q3 matrices, corresponding to a quantum circuit with 3-body quantum gates. One such model is the 32 vertex model [9]. Also 3D models, such as mod- els on a tilted 3D square lattice, can be considered of this type and can thus be mapped to quantum circuits. In this case, one deals with 3-particle gates acting on a 2D array of quantum particles. Gemma ask Maarten why not 4-particle gates? B. Edge models Gemma put here on in the background what the potts model is: The Potts model defined on a graph G is model such that q–level particle sit at the vertices of a graph, sa = 0, 1, . . . , q−1, and interact along the edges according to he(s) = −Jeδ(sa − sb) , (14) where the edge e is adjacent to vertices a, b, and δ(sa − sb) = 1 if si − sj = 0 and it is zero otherwise [10]. The Hamiltonian is a sum of these 2–local terms over all edges H(s) = ∑ e∈E he(s) . (15) In the following we will present a similar mapping for edge models. In contrast to vertex models, in edge mod- els the classical spins sit at the vertices of the graph; we will also consider classical spins with q possible states si ∈ {0, . . . , q − 1}. In this case interactions take place along the edges. Consider, thus, a q-state edge model on an n×m square lattice with an edge–dependent energy function he(si, sj)—see Fig. 2. Let we(si, sj) := e −βhe(si,sj) (16) denote the corresponding Boltzmann weight. Then the partition function is given by Z = ∑s∏e=ij we(si, sj). As previously, the n spins in the leftmost and rightmost column of the lattice are fixed in the configurations sL := (sL1 , . . . , s L n) and s R := (sR1 , . . . , s R n ), respectively. With each horizontal edge e, we now associate a q × q matrix Whe := ∑ si,sj we(si, sj)|sj〉〈si| . (17) Furthermore, with each vertical edge e, we associate the q2 × q2 diagonal matrix W ve := ∑ si,sj we(si, sj)|si, sj〉〈si, sj | . (18) The matrices Whe and W v e will be regarded as (possi- bly non-unitary) quantum gates acting on a single, re- spectively a pair, of q-level quantum systems. We now consider a one-dimensional quantum system composed of n q-level systems and the quantum circuit C acting on this system as depicted in Fig. 2. The circuit C con- sists of alternating layers of operations associated with the horizontal and vertical edges of the 2D lattice. Each round of C associated with a layer of horizontal edges consists of a product of one-local operatorsWhe , whereas every round associated with a layer of vertical edges is a product of two-local operations W ve . We define com- putational basis states |L〉 and |R〉 associated to the left and right boundary conditions, respectively, analogously to Eq. (10). With these definitions, one has the following correspondence: ZL,Rem = 〈L|C|R〉 . (19) Mapping partition functions to  quantum circuits I Particles at the edges  Mapping for vertex models Z L,R vm = 〈L|C|R〉 Interaction at vertex Two-qudit gatea W a(ij)(kl) = ∑ e−βh a(sisjsksl)|si, sj〉〈sksl|wa(s) = ∑ e −βha(sisjsksl) Particles at the vertices  Mapping for edge models 6 .. . .. . .. . .. . sL1 sL2 sL3 sR1 sR2 sR3 i jwhij wvjk i j k k W hij W vjk 〈sL1 | 〈sL2 | 〈sLn | |sR1 〉 |sR2 〉 |sRn 〉 time FIG. 2: (Left) In an edge model, particles (black dots) sit at the vertices and interactions (pale red and blue ellipses) take place along the edges. (Right) This model is mapped to a quantum circuit, where interactions along the time direc- tion become single–qubit gates, and those perpendicular to it become two–qubit gates. This equation is readily verified by employing the defini- tions of the gates Whe and W v e . In the following we give some simple modifications of the this mapping that will be useful below. First, con- sider that at site i in the lattice a local magnetic field is present. This is represented by an additional term hi(si) in the energy function and corresponding Boltz- mann weight wi(si) = e −βhi(si) , (20) with si = 0, . . . , q − 1. Then we introduce the diagonal q × q matrix Wi := ∑ si wi(si)|si〉〈si| . (21) Now a mapping to a quantum circuit C can be established in a similar fashion as above, with the distinction that each layer associated with a slice of vertical edges now consists of a product of the associated two–qubit gates W ve and the associated single–qubit gatesWi. Note that, as all such gates are diagonal operations, there is no prob- lem regarding operator ordering. With this choice of C, it can readily be verified that the associated partition function can be written as (19). Second, this mapping can also be extended to open and periodic boundary conditions, in a completely analogous fashion as for vertex models (see Sec. IVA). Finally, we remark that the above mappings from par- tition functions to quantum circuits may easily be gen- eralized to graphs other than the 2D lattice, similarly as for vertex models. In particular, below we will consider the following class of subgraphs of the 2D square lattice: a graph G is said to be a planar circuit graph if it can be obtained from an n×m rectangular grid (for some n and m) by deleting a subset of vertical edges and contracting a subset of horizontal edges. If G is such a subgraph of an n×m rectangular grid, we call n the vertical dimen- sion of G; note that this quantity is uniquely defined for every planar circuit graph. Similar as for the 2D square lattice, one can associate a quantum circuit C with every planar circuit graph; more precisely, one associates each horizontal and vertical edge e with the gates Whe and W ve , respectively, and each vertex i with the gate Wi; see Fig. 3 for an example. If the vertical dimension of the graph is n then C acts on n q-level systems. An identity similar to (19), or to (12) in the case of open boundary conditions, is easily seen to hold for planar circuit graphs as well (both with or without an external field). .. . .. . .. . .. . sL1 sL2 sL3 sR1 sR2 sR3 wi wij wjk Wi W h e W ve 〈sL1 | 〈sL2 | 〈sLn | |sR1 〉 |sR2 〉 |sRn 〉 time FIG. 3: (Left) Edge model defined on a planar circuit graph. The latter is obtained from an rectangular grid by deleting some vertical edges and contracting some horizontal edges. (Right) Mapping of a classical spin model defined on a planar circuit graph onto a quantum circuit. Horizontal and vertical edge interactions are mapped to single–qubit non–diagonal and two–qubit diagonal gates, respectively, and local inter- actions (e.g. magnetic fields) are mapped onto single–qubit (diagonal) gates. We now specialize the above discussion to the case of the 2D Ising model. We will consider the Ising model on (sublattices of) the 2D lattice in the presence of an external field: The interaction between two spins si and sj located at the endpoints of an edge e = ij is given by he(si, sj) = −Jeδ(si + sj), and the contribution of the magnetic field at site i is hi(si) = −hisi. Here the spin states si may take values 0 and 1, the sum is per- formed modulo 2, and δ(·) is 1 if the argument is 0 and it is 0 otherwise. Further, Je and hi are constants which represent the strengths of the pairwise interaction and magnetic field, respectively. With the definitions (17), (18) and (21), we have Whe = [ eβJe 1 1 eβJe ] , W ve = diag(e βJe, 1, 1, eβJe) Wi = [ eβhi 0 0 1 ] . (22) C. Lattice gauge theories We proceed to present a similar mapping for an entirely different class of models, namely Z2 LGTs. We refer the reader to [3] for an introduction to these models. For the present purposes we will be interested in the following features of Z2 LGTs. They are models whose classical spins can take two values se ∈ {0, 1} and sit at the edges of a square lattice. There is an interaction along every face; in particular, for spins si, sj, sk, sl at the boundary of face f , the interaction takes the form hf (s) = −Jfδ(si + sj + sk + sl) , (23) Z L,R em = 〈L|C|R〉 Mapping partition functions to  quantum circuits I Int. at edge in time dir. Single qudit gate Int. at edge in space dir. Two qudit diagonal gate w ij = e −βh(si,sj) w(i)(j) = ∑ e −βh(si,sj)|si〉〈sj | w(jk)(jk) = ∑ e −βh(sj ,sk)|sjsk〉〈sjsk|wjk = e−βh(sj ,sk) 8sL1 sL2 sR1 sR2 〈sL1 | 〈sL2 | |sR1 〉 |sR2 〉 time wa,b W tf wa,b,c,d W sf FIG. 4: (Left) In a 3D LGT, particles (black and gray dots) sit at the edges and interactions (pale red and blue ellipses) take place on the faces. Gray dots indicate particles whose state has been fixed by the gauge. (Right) This model is mapped to a quantum circuit, where interactions along the time direction become two–qubit gates, and those perpendicular to it become four–qubit gates. A. Six–vertex model We will now use the mappings between vertex models and quantum circuits described in Sec. IVA to show that approximating the partition function Z of some vertex models is in certain (complex) parameter regimes BQP– complete [1]. We consider the q = 2 ‘six-vertex model’ (or: ‘ice–type model’) and the ‘eight-vertex model’ [8] on a (tilted) 2D square lattice. In the six-vertex model, only six of the 16 possible spin configurations give rise to a non-zero Boltzmann weight. More precisely, W a is a 4× 4 matrix of the form W a =   w00,00 0 0 0 0 w01,01 w01,10 0 0 w10,01 w10,10 0 0 0 0 w11,11   . (37) The eight-vertex model [8] is obtained by additionally al- lowing the entries w00,11, w11,00 to be non–zero. We con- sider a parameter regime of the classical model where all matricesW a are unitary, that is, the circuit C is a unitary circuit of two–qubit quantum gates. Notice that this gen- erally corresponds to (non–physical) complex parameters for either coupling strengths or the inverse temperature β. Finally, we assume that we have staggered left an right boundary conditions of the form L = R = (0101 . . . ). In this case, we show that approximating the partition function of six–vertex models on a n × poly(n) lattice is BQP–complete. Let us fix some notation before starting the proof. Henceforth we will denote encoded states and operators by boldface symbols, and we will also omit the tensor product symbol ⊗ to keep notation simple. Now we can proceed to prove the claim of this section. To do so, we will show that any quantum computation can be reduced to the evaluation of the partition function of a six–vertex model on a tilted 2D square lattice with stag- gered boundary conditions. We will prove this statement in three steps: (i) We show that quantum gates of the form (37) are computational universal for encoded quantum com- putation; (ii) The encoded initial state |0〉⊗N can be prepared from the state corresponding to staggered boundary conditions |0101 . . .〉; (iii) For any given poly–size quantum circuit C, one can efficiently approximate the matrix element 〈0|C|0〉 by using encoded quantum states and gates of the form (37). To show (i), we consider the exchange (or Heisenberg) interaction, Hex = σx ⊗ σx + σy ⊗ σy + σz ⊗ σz (38) with correspondingtwo–qubitt gates U = eitHex . (39) These are of the form (37) with the non–zero entries w00,00 = w11,11 = ei2t w01,01 = w10,10 = cos(2t) w01,10 = w10,01 = i sin(2t) . (40) The Heisenberg interaction is (encoded) universal for quantum computation [12, 13]. In other words, by us- ing gates of the form (39), one can prepare any quantum state |ψ〉 = C|0〉 in an encoded form. Here, we use a four-qubit encoding |0〉 with |0〉 = 1 2 (|01〉 − |10〉)⊗2 . (41) And the |1〉 ? We now turn to (ii) and consider an operation V of the form (37) with the non–zero entries w00,00 = w11,11 = 1 w01,01 = w10,10 = w01,10 = −w10,01 = 1/ √ 2 . (42) It is straightforward to check that V |01〉 = (|01〉 − |10〉)/√2, and hence |0〉 = V ⊗2|0101〉 . (43) Regarding (iii), we observe that matrix elements of the form 〈0|C|0〉 can be efficiently approximated by a Mapping partition functions to  quantum circuits I  Mapping for lattice gauge theories Particles at the edges Int. at face in time dir. Single qudit gate Int. at face in space dir. Four qudit diagonal gate w ij = e −βh(si,sj) w(i)(j) = ∑ e −βh(si,sj)|si〉〈sj | w(jk)(jk) = ∑ e −βh(sj ,sk)|sjsk〉〈sjsk|wjk = e−βh(sj ,sk) Z L,R LGT = 〈L|C|R〉 &        Fixing the temporal gauge BQP-completeness resultsII  Main idea: Model Gates corresp. to that model Show that they form a universal gate set Approximating that partition function is as hard as simulating arbitrary quantum computation Z = 〈L|C|R〉 BQP-completeness resultsII  Main idea: Model Gates corresp. to that model Show that they form a universal gate set Approximating that partition function is as hard as simulating arbitrary quantum computation Z = 〈L|C|R〉 BQP-completeness resultsII  Main idea: Model Gates corresp. to that model Show that they form a universal gate set Approximating that partition function is as hard as simulating arbitrary quantum computation Provide a quantum algorithm Prove BQP-completeness of computing Z Z = 〈L|C|R〉  Six vertex model (Encoded) universal interactionU = eitHex withHex = σx ⊗ σx + σy ⊗ σy + σz ⊗ σz Encoding |0〉 = 1 2 (|01〉 − |10〉)⊗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: BQP-completeness resultsII W(ij)(jk) =   ei2t cos(2t) i sin(2t) i sin(2t) cos(2t) ei2t    Six vertex model (Encoded) universal interactionU = eitHex withHex = σx ⊗ σx + σy ⊗ σy + σz ⊗ σz Encoding |0〉 = 1 2 (|01〉 − |10〉)⊗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: Approximating the partition function of the six vertex model on a certain complex parameter regime is BQP-complete BQP-completeness resultsII W(ij)(jk) =   ei2t cos(2t) i sin(2t) i sin(2t) cos(2t) ei2t    Potts model Each Potts gate is characterized by the pair (eβJii , eβJi!=j ) Trivial preparation of |0〉 . . . |0〉 |R〉 = |0〉|1〉 . . . |0〉|1〉from Single qubit identity Phase gate Two qubit identity Controlled phase gate BQP-completeness resultsII |0〉 = |0〉|1〉 |1〉 = |1〉|2〉 Encoding: Construct an (encoded) universal gate set: 11 is a bit more involved and we refer the reader to Appendix B for the details. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate between the two physical qutrits of the first logical qubit with (µ, ν) = (1, 1), and doing the same for the other logical qubit (see Fig. 6a). • Finally, the phase gate between logical qubits CZ = 1∑ i,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 and the upper qutrit of the second logical qudit with (µ, ν) = (−1, 1). We also need to apply the same gate between the lower qudit of the second logical qubit and an auxiliary particle in the state |2〉 (see Fig. 6b). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 (a) (b) time time FIG. 5: (a) Logical single–qubit identity I1. (b) Logical phase gate P . Each gate is determined by the pair of numbers (µ, ν) (Eq. (52)) which are indicated next to it, and its color is just a guide to the eye to identify equal gates. Auxiliary spins (i.e. fixed spins) are colored in gray, and physical spins in black. Note that in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits interact according to a Potts-type nearest-neighbor inter- action, we can perform universal quantum computation at the logical level. From Eq. (3) it follows that the com- putation of the partition function of the Potts model with 3-level systems is a BQP–complete problem. We now give a few remarks regarding this construc- tion. First, we observe that the single–qubit identity I1 requires to set ν = 0, i.e. Ji!=j = −∞. This caveat can be circumvented by applying a modified gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual parameter range 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) (b) time time FIG. 6: (a) Logical two–qubit identity I2. (b) Logical con- trolled phase gate CZ. See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, namely Z ′ = 3IZ, where I is the number of times I ′ has been applied. Thus, the com- plexity of computing Z is the same as that of computing Z. even though I may scale with the system size? Second, note that the implementation of the gates H , P andCZ require complex values of the energy Jii, more precisely: βJii = −ipi/2, 0,−∞,± ln $,pi/2 for H βJii = ipi/8 for P (58) βJii = ipi for CZ , which is outside the usual (real) parameter range where these spin models are defined. We remark that the scheme presented above enables one to perform x-rotations Rx(θ) with an arbitrary angle θ. This is achieved by setting the first single-qutrit gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two last single-qutrit gates to (µ, ν) = (i sin θ, 1). The same is true for z-rotations: they can be performed over an arbitrary angle ξ by letting the two–qutrit gate that acts on the lower qutrit have (µ, ν) = (eiξ, 1). In this case the parameter regime corresponds additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) This gives a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the constraints. We would like to point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero and infinite – so everything but the usu- ally considered regime), and (ii) geometric constraints due to the encoding (couplings have to be distributed in a specific way to make the computation of its partition function have this complexity; e.g. obviously if they were everywhere zero, or everywhere but in a trivial region, the complexity of the partition function would not be BQP. 11 is a bit more involved and we refer the reader to Appendix B for the details. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate between the two physical qutrits of the first logical qubit with (µ, ν) = (1, 1), and doing the same for the other logical qubit (see Fig. 6a). • Finally, the phase gate between logical qubits CZ = 1∑ i,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 and the upper qutrit of the second logical qudit with (µ, ν) = (−1, 1). We also need to apply the same gate between the lower qudit of the second logical qubit and an auxiliary particle in the state |2〉 (see Fig. 6b). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 (a) (b) time time FIG. 5: (a) Logical single–qubit identity I1. (b) Logical phase gate P . Each gate is determined by the pair of numbers (µ, ν) (Eq. (52)) which are indicated next to it, and its color is just a guide to the eye to identify equal gates. Auxiliary spins (i.e. fixed spins) are colored in gray, and physical spins in black. Note that in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits interact according to a Potts-type nearest-neighbor inter- action, we can perform universal quantum computation at the logical level. From Eq. (3) it follows that the com- putation of the partition function of the Potts model with 3-level systems is a BQP–complete problem. We now give a few remarks regarding this construc- tion. First, we observe that the single–qubit identity I1 requires to set ν = 0, i.e. Ji!=j = −∞. This caveat can be circumvented by applying a mod fied gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual p rameter range of the Potts model. It can be r adily verified that |2〉 (1, 1) (1, 1) (−1, 1) (−1, 1) |ψ1〉 |ψ2〉 |ψ1〉 |ψ2〉 I2|ψ1〉|ψ2〉 CZ|ψ1〉|ψ2〉 (a) (b) time time FIG. 6: (a) Logical two–qubit identity I2. (b) Logical con- trolled phase gate CZ. See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, namely Z ′ = 3IZ, where I is the number of times I ′ has been applied. Thus, the com- plexity of computing Z is the same as that of computing Z. even though I may scale with the system size? Second, note that the implementation of the gates H , P andCZ require complex values of the energy Jii, more precis ly: βJii = −ipi/2, 0,−∞,± ln $,pi/2 for H βJii = ipi/8 for P (58) βJii = ipi for CZ , which is outside the usual (real) parameter range where these spin models are defined. We remark that the scheme presented above enables one to perform x-rotations Rx(θ) with an arbitrary angle θ. This is achieved by setting the first single-qutrit gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two last single-qutrit gates to (µ, ν) = (i sin θ, 1). The same is true for z-rotations: they can be performed over an arbitrary angle ξ by letting the two–qutrit gate that acts on lower qutrit have (µ, ν) = (eiξ, 1). In this case the parameter regime corresponds additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) This gives a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the constraints. We would like to point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero and infinite – so everything but the usu- ally considered regime), and (ii) geometric constraints due to the encoding (couplings have to be distributed in a specific way to make the com utation of its partition function have this complexity; e.g. obviously if they were everyw ere zero, o ev rywhere but in a trivial egion, t e omplexity of the partition function would not be BQP. 11 is a bit more involved and we refer the reader to Appendix B for the details. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate b tween the two physical qu rits of the first logical qubit with (µ, ν) = ( , 1), an doing the same for the other logical qubit (see Fig. 6a). • Finally, the phase gate between logical qubits CZ = 1∑ i,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 and the upper qutrit of the s cond lo ical qudit with (µ, ν) = (−1, 1). We also nee to apply the same gate between the lower qudit of the second logical qubit and an auxiliary particle in the state |2〉 (see Fig. 6b). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 (a) (b) time time FIG. 5: (a) Logical single–qubit identity I1. (b) Logical phase gate P . Each gate is determined b the pair of numbers (µ, ν) (Eq. (52)) which ar indicated next to it, and its color is just a guide to the ye to id ntify equal gates. Auxi iary spins (i.e. fixed spins) are colored in gr y, and physical spins in black. Note that in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits interact according to a Potts-type nearest-neighbor inter- action, we can perform universal quantum computation at the logical level. From Eq. (3) it follows that the com- putation of the partition function of the Potts model with 3-level systems is a BQP–comple p oblem. W now give a few remarks r garding this co struc- tio . First, we observe that the si gle–qubit identity I1 requires to set ν = 0, i.e. Ji!=j = −∞. This caveat can be circumvented by applying a modified gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual parameter range 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 FIG. 6: (a) Logical two–qubit ide tit l con- trolled phase gate CZ. See the c i f r t e meaning of the pair of numbers a i to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, na ely Z ′ = 3IZ, where I is the number of times I ′ has been applied. Thus, the com- plexity of computing Z is the same as that of computing Z. even t ough I may scale with the system size? Second, note that the implementation of the gates H , P andCZ require complex values of the energy Jii, more precisely: βJii = −ipi/2, 0,−∞,± ln $,pi/2 for H βJii = ipi/8 for P (58) βJii = ipi for CZ , which is outside the usual (real) parameter range where thes spin models are defin d. We remark that the scheme presented above enables one to perform x-rotations Rx(θ) with an arbitrary angle θ. This is achieved by setting the first single-qutrit gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two last single-qutrit gates to (µ, ν) = (i sin θ, 1). The same is true for z-rota ions: they can be performed over an arbitrary angle ξ by letting the two–qut it gate that acts on the lower qutrit have (µ, ν) = (eiξ, 1). In is ase the param ter regime corresponds additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) This gives a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the constraints. We would like to point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero and infinite – so everything but the usu- ally considered regim ), and (ii) geometric constraints due to the encoding (couplings have to be distributed in a specific way to make the computation of its partition function have this complexity; e.g. obviously if they were everywhere zero, or everywhere but in a trivial region, the complexity of the partition function would not be BQP. 11 is a bit more involved and we refer the reader to Appendix B for the details. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate between the two physical qutrits of the first logical qubit with (µ, ν) = (1, 1), and doing the same for the other logic l qubit (see Fig. 6a). • Finally, the phase gate between logical qubits CZ = 1∑ i,j=0 (−1)ij |ij〉〈ij| (57) is achieved by applying a two qutrit–ga e be- tween the lower–qutrit of the first logical qubit and the upper qutrit of the second logical qudit with (µ, ν) = (−1, 1). We also ne d to apply the s me gate b tween the lower qudit of the secon logical qubit and an auxiliary p rti l in the state |2〉 (see Fig. 6 ). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 (a) (b) time time FIG. 5: (a) Logical single–qubit identity I1. (b) Logical phase gat P . Each gate is determined by the pair of ers (µ, ν) (Eq. 52)) w ich are indicated nex to it, an lor is just a guide to t e eye to identify qual gates. ili ry spins (i.e. fixed spins) are c lor d in gray, and physical spins in black. Note that in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits inter ct according to a Potts-type nearest-neighbor inter- action, w can perform universal quantum computation at the logical level. F o Eq. (3) it follows hat th com- putation of the partitio f ctio of the Potts model with 3-level systems is a lete problem. We now give a fe regarding this construc- tion. First, we obser single–qubit iden ity I1 requires to set ν 0, i.e. i! j . This caveat can be circumvented by applying a odified gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual parameter range 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) (b) time time FIG. 6: (a) Logical two–qubit identity I2. (b) Logical con- trolled phase gate CZ. See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, namely Z ′ = 3IZ, where I is the number of times I ′ has been applied. Thus, the com- plexity of computing Z is the same as that of computing Z. even though I may scale with t e syste size? Second, note that the implementation of the gates H , P andCZ require complex values of the energy Jii, more precisely: βJii = −ipi/2, 0,−∞,± ln $,pi/2 for H βJii = ipi/8 for P (58) βJii = ipi for CZ , which is outside the usual (real) parameter range where these spin models are defined. We re ark that the scheme presented above enables one to perform x-rotations Rx(θ) with an arbitrary angle θ. This is achieved by setting the first single-qutrit gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two last single-qutrit gates to (µ, ν) = (i sin θ, 1). The same i true for z-rotations: they can be perform d over an arbit ary angle ξ by letting the two–qutrit gate that acts on the lower qutrit hav (µ, ν) = (eiξ, 1). In this case the p rameter regime correspon s additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) This gives a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the co straints. We would lik t point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero a d infinite – so everything but the usu- ally considered regime), and (ii) geometric co straints due o the encoding (couplings have to be distributed in a specific way to make the computation of its partition function have this complexity; e.g. obviously if they were everywhere zero, or everywhere but in a trivial region, the complexity of the partition function would not be BQP. 11 is a bit more involved and we refer the reader to Appendix B for the details. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate between the two physical qutrits of the first logical qubit with (µ, ν) = (1, 1), and doing the same for the other logical qubit (see Fig. 6a). • Finally, the phase gate between logical qubits CZ = 1∑ i,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 and the upper qutrit of the second logical qudit with (µ, ν) = (−1, 1). We also need to apply the s me gate betwe n the l wer udit of the e nd logical qubit and an uxiliary particle in the s ate |2〉 (see Fig. 6b). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 (a) (b) time time FIG. 5: (a) Logical single–qubit identity I1. (b) Logical phase gate P . Each gate is determined by the pair of numbers (µ, ν) (Eq. (52)) which are indicated next to it, and its color is just a guide to the eye to identify equal gates. Auxiliary spins (i.e. fixed spins) are colored in gray, and physical spins in black. Note that in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits interact according to a Potts-type nearest-neighbor inter- action, we can perform universal quantum computation at the logical level. From Eq. (3) it follows that the com- putation of the partition function of the Potts model with 3-level systems is a BQP–complete problem. We now give a few remarks regarding this construc- tion. First, we observe that the single–qubit identity I1 requires to set ν = 0, i.e. Ji!=j = −∞. This caveat can be circumvented by applying a modified gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual parameter range 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) (b) time time FIG. 6: (a) Logical two–qubit identity I2. (b) Logical con- trolled phase gate CZ. See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, namely Z ′ = 3IZ, where I is the number of times I ′ has been applied. Thus, the com- plexity of compu ing Z is the same as that of computing Z. even though I may scale with the system size? Second, note hat th implementation of the gates H , P ndCZ require complex valu s of th ne gy J i, more precisely: βJii = −ipi/2, 0,−∞,± ln $,pi/2 for H βJii = ipi/8 for P (58) βJii = ipi for CZ , which is tside he usual (real) parameter range where these spin models are defined. We remark that the scheme presented above enables one to perform x-rotations Rx(θ) with an arbitrary angle θ. This is achieved by setting the first single-qutrit gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two last single-qutrit gates to (µ, ν) = (i sin θ, 1). The same is true for z-rotations: they can be performed over an arbitrary angle ξ by letting the two–qutrit gate that acts on the lower qutrit have (µ, ν) = (eiξ, 1). In this case the parameter regime corresponds additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) This gives a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the constraints. We would like to point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero and infinite – so everything but the usu- ally considered regime), and (ii) geometric constraints due to the encoding (couplings have to be distributed in a specific way to make the computation of its partition function have this complexity; e.g. obviously if they were everywhere zero, or everywhere but in a trivial region, the complexity of the partition function would not be BQP. 11 is a bit more involved and we refer the reader to Appendix B for the details. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate between the two physical qutrits of the first logical qubit with (µ, ν) = (1, 1), and doing the same for the other logical it (see Fig. 6a). • Finally, t phase gate between l gic l qubi s CZ = 1∑ i,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 and the upper qutrit of the second logical qudit with (µ, ν) = (−1, 1). We also eed t apply the am gate between the lower qudit of the second logical qubit and an auxiliary particle in the state |2〉 (see Fig. 6b). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 (a) (b) time time FIG. 5: (a) Logical single–qubit identity I1. (b) Logical phase gate P . Each gate is determined by the pair of numb rs (µ, ν) (Eq. (52)) which are indicated next o it, and its colo is just a guide to the eye to identify equal gates. Auxiliary spins (i.e. fixed spins) are colored in gray, and physical spins in black. Note that in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits interact according to a Potts-type ne rest-neighbor inter- action, we can perform universal quantum computation at the logical level. From Eq. (3) it follows that the com- putation of the partition function of the Potts model with 3-level systems is a BQP–complete problem. We now give few remarks r garding his constru - tion. First, we observe at the s ngle–qubit identity I1 requires to set ν = 0, i. . Ji!=j = −∞. This ca eat can be circumvented by applying a modified gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual parameter range 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) (b) time time FIG. 6: (a) Logical two–qubit identity I2. (b) Logical con- trolled phase gate CZ. See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, namely Z ′ = 3IZ, where I is the number of times I ′ has been applied. Thus, the com- plexity of computing Z is the same as that of computing Z. even though I may scale with the system size? Second, note that the implementation of the gates H , P andCZ require complex values of the energy Jii, more precisely: βJii = −ipi/2, 0,−∞,± ln $,pi/2 for H βJii = ipi/8 for P (58) βJii = ipi for CZ , which is outside the usual (real) parameter range where thes spin models are defined. We remark that the scheme presented above enables one to perform x-rotations Rx(θ) with an arbitrary angle θ. This is achieved by setting the first single-qutrit gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two last single-qutrit gates to (µ, ν) = (i sin θ, 1). The same is true for z-r tations: they can be performed over n arbitrary angle ξ by letting the two–qutrit gate that acts on the lower qutrit have (µ, ν) = (eiξ, 1). In this case the parameter regime corresponds additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) Thi give a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the constraints. We would like to point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero and infinite – so everything but the usu- ally c nsidered regime), and (ii) geometric constraints due to the encoding (couplings have to be distributed in a specific way to make the computation of its partition function have this complexity; e.g. obviously if they were everywhere zero, or everywhere but in a trivial region, the complexity of the partition function would not be BQP. 11 is a bit more involved and we refer the read r to Appendix B for the etails. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate between the two physical qutrits of the first logical qubit with (µ, ν) = (1, 1), and doing the same for the other logical qubit (see Fig. 6a). • Finally, the phase gate between logic l qubits CZ = 1∑ i,j=0 (−1)ij | j〉〈ij| (57) is achieved by applying a two qutrit–gate be- tween the lower–qutrit of the first logical qubit and the upper trit of the sec d logical qudit with (µ, ν) = (−1, 1). We also eed to apply t e same gate between the lower qudit of the second logical qubit and an auxiliary particle in the state |2〉 (see Fig. 6b). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 (a) (b) time time I . 5: (a) Logical single–qubit iden ity I1. (b) Logical se gate P . Each gate is determined by the pair of numbers ( , ν) ( q. (52)) which are indicated next to it, and its color is just a guide to the eye to identify equal gates. Auxiliary spins (i.e. fixed spins) are colored in gray, and physical spins in black. Note that in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits interact according to a Potts-type nearest-neighbor inter- action, we can perform universal quantum computation at the logical level. From Eq. (3) it follows that the com- putation of the partition function of the Potts model with 3-level systems is a BQP–complete problem. We now give a few remarks regarding this construc- tion. First, we observe that the single–qubit identity I1 requires to set ν = 0, i.e. Ji!=j = −∞. This caveat can be circumvented by applying a modified gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual parameter range 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) (b) time time FIG. 6: (a) L gical two–qubit identity I2. (b) Logical con- rolled phase gate CZ. See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, namely Z ′ = 3IZ, where I is the number f times I ′ has been applied. Thus, the com- plexity of computing Z is the same as that of computing Z. even though I may scale with the syste size? Second, ote that the imple entation of the gates H , P andCZ require complex values of the energy Jii, more precisely: βJii = −ipi/2, 0,−∞,± ln $,pi/2 fo H βJii = ipi/8 for P (58) βJii = pi for CZ , which is outside the usual (real) parameter range where th se spin models ar defined. We remark that the sch me pres nted above enables one to pe form x-rotations Rx(θ) with n a bitr ry angle θ. Th is achieved by setting the first single-qutri gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two la t single-qutrit ga es to (µ, ν) = (i sin θ, 1). The same is true for z-rotations: they can be performed over an arbitrary angle ξ by letting the two–qutrit gate that acts on the lower qutrit have (µ, ν) = (eiξ, 1). In this case the parameter regime corresponds additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) This gives a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the constraints. We would like to point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero and infinite – so everything but the usu- ally considered regime), and (ii) geometric constraints due to the encoding (couplings have to be distributed in a specific way to make the computation of its partition function have this complexity; e.g. obviously if they were everywhere zero, or everywhere but in a trivial region, the complexity of the partition function would not be BQP. 11 is a bit more involved and we refer the reader to Appendix B for the details. • The two–qubit identity gate I2 = 1∑ i,j=0 |ij〉〈ij| , (56) is trivially obtained by applying a two qutrit–gate between the two physical qutrits of the first logical qubit with (µ, ν) = (1, 1), and doing the same for the other logical it (see Fig. 6a). • Finally, the phase gate between l gic l qubi s CZ = 1∑ i,j=0 (−1)ij |ij〉〈ij| (57) is achieved by applying a two qutrit–ga e be- tween the lower–qutrit of the first logical qubit and the upper qutrit of the second logical qudit with (µ, ν) = (−1, 1). We also need to apply the same gate between the lower qudit of the second logical qubit and an auxiliary parti le in the state |2〉 (see Fig. 6b). |2〉 (1, 1) (eipi/8, 1) |ψ〉I1|ψ〉 |ψ〉P |ψ〉 ( ) (b) time time FIG. 5: (a) Logical single–qubit identity I1. (b) Logical ph se gat P . Each gate is d termined by the p ir of numbers (µ, ν) (Eq. (52)) which are indicated next to it, and its color is just a guide to the eye to identify equal gates. Auxiliary spins (i.e. fixed spins are colored in g ay, and physical spins in black. Note h t in both figures time runs from right to left. Gemma unify the two figures in one? In summary, we have proven that by letting the qutrits interac according to a Potts-type nearest-neighbor inter- action, we can perform universal qua tum computation at the logic lev l. From Eq. (3) it follows that the com- putation of the partition function of the Potts model with 3-level systems i a BQP–complete problem. We now give a few remarks regarding this construc- tion. First, we observe that he single–qubi identity I1 requires to set ν = 0, i.e. Ji!=j = −∞. This caveat can be ci cumvent d by applying a modified gate, I′1 with (µ, ν) = (1, 1) and is thus within the usual parameter range of the Potts mod l. 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) (b) time time FIG. 6: (a) Logical two–qubit identity I2. (b) Logical con- trolled phase gate CZ. See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. the use of I ′ instead of I results in a prefactor in the ob- tained partition function, namely Z ′ = 3IZ, where I is the number of times I ′ has been applied. Thus, the com- plexity of computing Z is the same as that of computing Z. even though I may scale with the system size? Second, note that the implementation of the gates H , P andCZ require complex values of the energy Jii, more precisely: βJii = −ipi/2, 0,−∞,± ln $,pi/2 for H βJii = ipi/8 for P (58) βJii = ipi for CZ , which is outside the usual (real) parameter range where these spin models are defined. We remark that the scheme presented above enables one to perform x-rotations Rx(θ) with an arbitrary angle θ. This is achieved by setting the first single-qutrit gate acting on the upper qutrit to (µ, ν) = (−i cot θ, 1), and the two last single-qutrit gates to (µ, ν) = (i sin θ, 1). The same is true for z-rotations: they can be performed over an arbitrary angle ξ by letting the two–qutrit gate that acts on the lower qutrit have (µ, ν) = (eiξ, 1). In this case the parameter regime corresponds additionally to βJii = ln(−i cot θ), ln(i sin θ) for Rx(θ) βJii = iξ for Rz(ξ) . (59) This gives a larger class of Potts models whose partition function is BQP–complete. Gemma Place this remark about the constraints. We would like to point out that our BQP–completeness re- sults for the Potts model has (i) constraints in the pa- rameter regime (basically the regime are all imaginary numbers, zero and infinite – so everything but the usu- ally considered regime), and (ii) geometric constraints due to the encoding (couplings have to be distributed in a specific way to make the computation of its partition function have this complexity; e.g. obviously if they were everywhere zero, or everywhere but in a trivial region, the complexity of the partition function would not be BQP. GDlC, M. Van d n Nest, W. Dür, H. J. Brieg l, M.A. Martin-Delgado (in preparation) 12 Do you want to include this paragraph? From the point of view of the complexity results, to have a discrete parameter regime of the Potts model for which its com- putation is BQP–complete is a stronger result than with a continuous parameter regime. However, from the point of view of a quantum algorithm, the larger the parame- ter regime, the stronger the result, because it can include more Potts model for which we propose a quantum al- gorithm. Note, however, that both parameter regimes are complex, and thus the quantum algorithms cannot be used to compute Potts model with real, i.e. physical, parameters. This problem was already encountered in Ref. [4–6]. Third, in the constructions presented above we need a constant supply of auxiliary qutrits. Therefore we en- visage two possible setups. One possibility is to have auxiliary qutrits in the middle of a 2D square lattice in contact with the nodes, but this requires to set bound- ary conditions also at the middle of the lattice. This drawback is circumvented in the second setup, in which physical qubits are in contact with four auxiliary qubits: one in |0〉, one in |1〉, another one in |2〉 and the fourth auxiliary in any of these values (it is four instead of three because of symmetry reasons), thus forming a triangular lattice (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 (see Fig. 7b). All single–qutrit gates for auxiliary particles are single–qutrit identity gates. Note that the auxiliary particles are left unchanged after any gate. Fourth, we see with our construction that the Potts model in a 1D array is not BQP–complete, whereas this model on a 2D setup (and with complex parameters) is BQP–complete. This is in agreement with the fact that the Potts model in 1D array or a tree–like structure is efficiently simulatable classically [14]. Finally, this result can be generalized to Potts model with any q. In this case, the encoded states are still given by Eq. (51), and all gates are performed with the same procedure except for the Hadamard. For this gate, one adds filters for the |3〉 . . . |q − 1〉 components on the upper and the lower qudit right after the filters for the |2〉 and the |0〉 component of Fig. 11. That is, the number of filters scales linearly with q (since one requires q − 2 filters for each qudit). Moreover, each physical qudit has to be connected to 2#q/2$ auxiliary particles, each fixed in a different state, namely |0〉, . . . , |q−1〉. This amounts to a similar construction to that of Fig. 7 but where each physical qudit is connected to #q/2$ auxiliary qudits to the left and to the right. Gemma do we need some extra figure on that? I wouldn’t add one, otherwise it’ll be too long D. Z2 Lattice gauge theory Now we turn to a different class of models, namely LGTs. Using the same tools (presented in Sec. IVC), 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 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 and t + 1. The figure shows an example of a circuit, where a phase gate P is applied to |ψt1〉 and the gate CZ is applied to |ψt+11 〉|ψ t+1 2 〉. will prove that computing the partition function of the 3D Z2 LGT (in a specific, complex parameter regime) is BQP–complete. Gemma check this Here we will make use of the gauge symmetry to fix the value of some spins, in- stead of fixing them boundary conditions as in Sec. VB, VC. In particular, we will fix the spins in the time di- rection of edges that connect logical qubits (see below) at different time slices, and some other spins (not in the time direction), as will be specified below. Our goal is to construct, at the logical level, the uni- versal gate set Rz(ξ) = |0〉〈0| + eiξ|1〉〈1| H = ∑1 i,j=0,1(−1)ij |j〉〈i| σz ⊗ σz = ∑1 i,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) (!, 1) (!, 1) (!, 1) (!, 1)(!, 1) ( 1 ! √ 2 , 1) ( 1 ! √ 2 , 1) ( 1 ! √ 2 , 1) (i, 1) (i, 1) (−i, 1) (1, 1) time FIG. 11: Sequence of gates at the physical level required to perform a Hadamard rotation at the logical level, H . See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. Gemma here there are new colors Gemma time is inversed! Hadamard gate BQP-completeness resultsII Example of part of a circuit: Not  distri ution of physical and auxiliary qubits 12 Do you want to include this paragraph? From the point of view of the complexity results, to have a discrete parameter regime of the Potts model for which its com- putation is BQP–complete is a stronger result than with a continuous parameter regime. However, from the point of view of a quantum algorithm, the larger the parame- ter regime, the stronger the result, because it can include more Potts model for which we propose a quantum al- gorithm. Note, however, that both parameter regimes are complex, and thus the quantum algorithms cannot be used to compute Potts model with real, i.e. physical, parameters. This problem was already encountered in Ref. [4–6]. Third, in the constructions presented above we need a constant supply of auxiliary qutrits. Therefore we en- visage two possible setups. One possibility is to have auxiliary qutrits in the middle of a 2D square lattice in contact with the nodes, but this requires to set bound- ary conditions also at the middle of the lattice. This drawback is circumvented in the second setup, in which physical qubits are in contact with four auxiliary qubits: one in |0〉, one in |1〉, another one in |2〉 and the fourth auxiliary in any of these values (it is four instead of three because of symmetry reasons), thus forming a triangular lattice (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 (see Fig. 7b). All single–qutrit gates for auxiliary particles are single–qutrit identity gates. Note that the auxiliary particles are left unchanged after any gate. Fourth, we see with our construction that the Potts model in a 1D array is not BQP–complete, whereas this model on a 2D setup (and with complex parameters) is BQP–complete. This is in agreement with the fact that the Potts model in 1D array or a tree–like structure is efficiently simulatable classically [14]. Finally, this result can be generalized to Potts model with any q. In this case, the encoded states are still given by Eq. (51), and all gates are performed with the same procedure except for the Hadamard. For this gate, one adds filters for the |3〉 . . . |q − 1〉 components on the upper and the lower qudit right after the filters for the |2〉 and the |0〉 component of Fig. 11. That is, the number of filters scales linearly with q (since one requires q − 2 filters for each qudit). Moreover, each physical qudit has to be connected to 2#q/2$ auxiliary particles, each fixed in a different state, namely |0〉, . . . , |q−1〉. This amounts to a similar construction to that of Fig. 7 but where each physical qudit is connected to #q/2$ auxiliary qudits to the left and to the right. Gemma do we need some extra figure on that? I wouldn’t add one, otherwise it’ll be too long D. Z2 Lattice gauge theory Now we turn to a different class of models, namely LGTs. Using the same tools (presented in Sec. IVC), 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 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 and t + 1. The figure shows an example of a circuit, where a phase gate P is applied to |ψt1〉 and the gate CZ is applied to |ψt+11 〉|ψ t+1 2 〉. will prove that computing the partition function of the 3D Z2 LGT (in a specific, complex parameter regime) is BQP–complete. Gemma check this Here we will make use of the gauge symmetry to fix the value of some spins, in- stead of fixing them boundary conditions as in Sec. VB, VC. In particular, we will fix the spins in the time di- rection of edges that connect logical qubits (see below) at different time slices, and some other spins (not in the time direction), as will be specified below. Our goal is to construct, at the logical level, the uni- versal gate set Rz(ξ) = |0〉〈0| + eiξ|1〉〈1| H = ∑1 i,j=0,1(−1)ij |j〉〈i| σz ⊗ σz = ∑1 i,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) (!, 1) (!, 1) (!, 1) (!, 1)(!, 1) ( 1 ! √ 2 , 1) ( 1 ! √ 2 , 1) ( 1 ! √ 2 , 1) (i, 1) (i, 1) (−i, 1) (1, 1) time FIG. 11: Sequence of gates at the physical level required to perform a Hadamard rotation at the logical level, H . See the caption of Fig. 5 for the meaning of the pair of numbers and the color associated to each gate. Gemma here there are new colors Gemma time is inversed! Hadamard gate Approx mating the partition function of a 2D 3-level Potts  with auxiliary qubits on a certain complex parameter regime is BQP-complete BQP-completeness resultsII Example of part of a circuit: Not  distri ution of physical and auxiliary qubits Encoding: |0〉 = |0〉|0〉|0〉|0〉 |1〉 = |1〉|1〉|1〉|1〉 Trivial preparation of |0〉 . . . |0〉 from |R〉 = |0〉 . . . |0〉  3D      LGTZ2 Each       LGT-type gate is characterized by the pair (eβJii , eβJi!=j )Z2 13 Note that this is a continuous universal gate set Wolf- gang, is this a problem or an advantage?. Note that this set includes the single–qubit identity I1, and the two– qubit identity I2. More precisely, we will use the fol- lowing encoding of four physical qubits into one logical qubit: |0〉 = |0〉|0〉|0〉|0〉 |1〉 = |1〉|1〉|1〉|1〉 . (61) The single–qubit identity I1 is achieved by (c, d) = (1, 0) (see Fig. 8a) . Gates Rz(ξ) are obtained by letting the logical qubit interact with a neighboring, auxiliary plaquette which has all remaining qubits fixed to |0〉, and setting (c, d) = (1, eiξ) (see Fig. 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 are marked with thick, black lines, and qubits fixed by the gauge symmetry are depicted in gray. The pair of numbers associ- ated to each gate are (c, d), which determine it. (a) The logical single–qubit identity I1 is obtained by setting (c, d) = (1, 0) in the plaquette formed by the four physical qubits that compose the logical qubit. (b) The logical rotation around the z–axis, Rz(ξ) is obtained by letting the logical qubit interact with an auxiliary plaquette whose spins are all fixed to |0〉, and set- ting (c, d) = (1, eiξ) in this auxiliary plaquette. (c) The only non–local part of CZ, diag(1, i, i, 1), is implemented by let- ting the two logical qubits interact via an auxiliary plaquette with (c, d) = (1, i). The implementation of the logical Hadamard gate H (see Fig. 9) is inspired in the idea of teleportation. In particular, we want to apply H to the logical qubit on the left of Fig. 9. To this end, we prepare the two logical qubits on its right in the state |0+〉+ |1−〉, where |±〉 = |0〉± |1〉 , (62) by analogy of the conventional definitions with physical qubits |±〉 = |0〉± |1〉. Then we apply a projection onto a Bell state |00〉 + |11〉 between the qubit we want to teleport and the first of these two logical qubits. More precisely, the three logical qubits are initially in the state |ψ〉|0〉|0〉, and they are transformed with the following gates (depicted in Fig. 9): 1. Single qubit gates with (c, d) = (1, 1) to all physical qubits of the two logical qubits on the right, which yields the state |ψ〉|++++〉⊗2, 2. The four–qubit gate (c, d) = (1, 0) on the second and third logical qubits, and the four–qubit gates (c, d) = (1, 1) to all their surrounding plaquettes, which results in the state |ψ〉|e4〉⊗2, where |e4〉 is an equal superposition of all even states of 4 qubits, |e4〉 ≡ |0000〉+ |0011〉+ . . .+ |1100〉+ |1111〉. 3. The four–qubit gates with (c, d) = (1, 0) to the sur- roundings of the two logical qubits on the right, which results in the state |ψ〉(|0000〉 + |0011〉 + |1100〉+ |1111〉)⊗2. 4. The four–qubit gates with (c, d) = (1, 0) between the second and third physical qubits of the last two logical qubits, which results in the state |ψ〉|+〉⊗2 5. The gate CZ on the last two logical qubits, which yields the state |ψ〉(|0+〉 + |1−〉). 6. A four–qubit gate with (c, d) = (1, 0) between the first and the second logical qubit (which cor- responds to the Bell measurement), and another four–qubit gate with (c, d) = (1, 0) between the first and the second logical qubit, which yields the state H |ψ〉 on the third logical qubit, as desired. This shows that we can now perform a general single qubit unitary U , since this can be expressed in its Euler decomposition U(α,β, γ) = Rz(α)HRz(β)HRz(γ) . (63) To generate the logical controlled phase gate CZ we decompose it into Rz rotations and a non–local gate: CZ = R(1)z (− pi 2 )R(2)z (− pi 2 ) diag(1, i, i, 1) . (64) The last gate is implemented by letting the last two logical qubits interact via an auxiliary plaquette with (c, d) = (1, i) (see Fig. 8c). Finally, we distribute the logical qubits in the 3D lat- tice as sketched in Fig. 10. We consider that the ver- tical and the horizontal directions are the spatial ones, and that time increases in the direction going from paper to the reader. Then the logical qubits are initially dis- tributed in a 1D vertical array, situated on the left, rear part of the circuit. Single qubit gates move the logical qubits in the time direction, while Hadamard gates move them to the right. At the end of the circuit, the logical qubits are situated in a 1D array at the right, front part of the circuit. We would like to make some comments concerning of this construction. First, the realization of I1 requires first a rescaling of the energy to (c′, d′) = 1, e−2βJ . Then, one has to let J →∞.Comment on this. 13 Note that this is a continuous universal gate set Wolf- gang, is this a problem or an advantage?. Note that this set includes the single–qubit identity I1, and the two– qubit identity I2. More precisely, we will use the fol- lowing encoding of four physical qubits into one logical qubit: |0〉 = |0〉|0〉|0〉|0〉 |1〉 = |1〉|1〉|1〉|1〉 . (61) The single–qubit identity I1 is achieved by (c, d) = (1, 0) (see Fig. 8a) . Gates Rz(ξ) are obtained by letti g t e logical qubit interact with a neighboring, auxiliary plaquette which has all remaining qubits fixed to |0〉, and setting (c, d) = ( , eiξ) (see Fig. 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 are marked with thick, black lines, and qubits fixed by th gauge symmetry are depicted in gray. The p ir of numbers associ- ated to each gate are (c, d), which determine it. (a) The logical single–qubit identity I1 is obtained by setting (c, d) = (1, 0) in the plaquette formed by the four physical qubits t at compose the logical qubit. (b) The logical rotation around the z–axis, Rz(ξ) is obtained by let ing the logical qubit interact with an auxiliary plaquette whose spins are all fixed to |0〉, and set- ting (c, d) = (1, eiξ) in this auxiliary plaquette. (c) The only non–local part of CZ, diag(1, i, i, 1), is implemented by let- ting the two logical qubits interact via an auxiliary plaquette with (c, d) = (1, i). The implementation of the logical Hadamard gate H (see Fig. 9) is inspired in the idea of teleportation. In particular, we want to apply H to the logical qubit on the left of Fig. 9. To this nd, we prepare the two logical qubits on its right in the state |0+〉+ |1−〉, where |±〉 = |0〉± |1〉 , (62) by analogy of the conventional definitions with physical qubits |±〉 = |0〉± |1〉. Then we apply a proje tion onto a Bell state |00〉 + |11〉 between the qubit we want to teleport and the first of these two logical qubits. More precisely, the three logical qubits are initially in the stat |ψ〉|0〉|0〉, and they are transformed with he following gat s (depicted in Fig. 9): 1. Single qubit gates with (c, d) = (1, 1) to all physical qubits of the two logical qubits on the right, which yields the state |ψ〉|++++〉⊗2, 2. The four–qubit gate (c, d) = (1, 0) on the second and third logical qubits, and the four–qubit gates (c, d) = (1, 1) to all their surrounding plaquettes, which results in the state |ψ〉|e4〉⊗2, where |e4〉 is an equal superposition of all even states of 4 qubits, |e4〉 ≡ |0000〉+ |0011〉+ . . .+ |1100〉+ |1111〉. 3. The f ur–qubit gates with (c, d) = (1, 0) to the sur- roundings of the two logical qubits on the right, which results in the state |ψ〉(|0000〉 + |0011〉 + |1100〉+ |1111〉)⊗2. 4. The four–qubit gates with (c, d) = (1, 0) between the second and third physical qubits of the last two logical qubits, which results in the state |ψ〉|+〉⊗2 5. The gate CZ on the last two logical qubits, which yields the state |ψ〉(|0+〉 + |1−〉). 6. A four–qubit gate with (c, d) = (1, 0) between the first and the second logical qubit (which cor- responds to the Bell measurement), and another four–qubit gate with (c, d) = (1, 0) between the first and the second logical qubit, which yields the state H |ψ〉 on the third logical qubit, as desired. This shows that we can now perform a general single qubit unitary U , since this can be expressed in its Euler decomposition U(α,β, γ) = Rz(α)HRz(β)HRz(γ) . (63) To generate the logical controlled phase gate CZ we decompose it into Rz rotations and a non–local gate: CZ = R(1)z (− pi 2 )R(2)z (− pi 2 ) diag(1, i, i, 1) . (64) The last gate is implemented by letting the last two logical qubits interact via an auxiliary plaquette with (c, d) = (1, i) (see Fig. 8c). Finally, we distribute the logical qubits in the 3D lat- tice s sketched in Fig. 10. We consider that the ver- tical and the horizontal directions are the spatial ones, and that time increases in the direction going from paper to the eader. Th n the logical qubits are initially dis- tributed in a 1D vertical array, situated on the left, rear part of the circuit. Single qubit gates move the logical qubits in the time direction, while Hadamard gates move them to right. At the end of the circuit, the logical qubits are situated in a 1D array at the right, front part of the circuit. We would like to make some comments concerning of this construction. First, the realization of I1 requires first a rescaling of the nergy to (c′, d′) = 1, e−2βJ . Then, one has to let J →∞.Comment on this. 13 Note that this is a continuous universal gate set Wolf- gang, is this a problem or an advantage?. Note that this set includes the single–qubit identity I1, and the two– qubit identity I2. More precisely, we will use the fol- lowing encoding of four physical qubits into one logical qubit: |0〉 = |0〉|0〉|0〉|0〉 |1〉 = |1〉|1〉|1〉|1〉 . (61) The single–qubit identity I1 is achieved by (c, d) = (1, 0) (see Fig. 8a) . Gates Rz(ξ) are obtained by letting the logical qubit interact with a neighboring, auxiliary plaquette which has all remaining qubits fixed to |0〉, and setting (c, d) = (1, eiξ) (see Fig. 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 are marked with thick, black lines, and qubits fixed by the gauge symmetry are depicted in gray. The pair of numbers associ- ated to each gate are (c, d), which determine it. (a) The logical single–qubit identity I1 is obtained by setting (c, d) = (1, 0) in the plaquette formed by the four physical qubits that compose the logical qubit. (b) The logical rotation around the z–axis, Rz(ξ) is obtained by letting the logical qubit interact with an auxiliary pl quett whose spins are all fixed to |0〉, and set- ting (c, d) = (1, eiξ) in this auxiliary plaquette. (c) The only non–local part of CZ, diag(1, i, i, 1), is implemented by let- ting the two logical qubits interact via an auxiliary plaquette with (c, d) = (1, i). The implementation of the logical Hadamard gate H (see Fig. 9) is inspired in the idea of teleportation. In particular, we want to apply H to the logical qubit on the left of Fig. 9. To this end, we prepare the two logical qubits on its right in the state |0+〉+ |1−〉, where |±〉 = |0〉± |1〉 , (62) by analogy of the conventional definitions with physical qubits |±〉 = |0〉± |1〉. Then we apply a projection onto a Bell state |00〉 + |11〉 between the qubit we want to teleport and the first of these two logical qubits. More precisely, the three logical qubits are initially in the state |ψ〉|0〉|0〉, and they are transformed with the following gates (depicted in Fig. 9): 1. Single qubit gates with (c, d) = (1, 1) to all physical qubits of the two logical qubits on the right, which yields the state |ψ〉|++++〉⊗2, 2. The four–qubit gate (c, d) = (1, 0) on the second and third logical qubits, and the four–qubit gates (c, d) = (1, 1) to all their surrounding plaquettes, which results in the state |ψ〉|e4〉⊗2, where |e4〉 is an equal superposition of all even states of 4 qubits, |e4〉 ≡ |0000〉+ |0011〉+ . . .+ |1100〉+ |1111〉. 3. The four–qubit gates with (c, d) = (1, 0) to the sur- roundings of the two logical qubits on the right, which results in the state |ψ〉(|0000〉 + |0011〉 + |1100〉+ |1111〉)⊗2. 4. The four–qubit gates with (c, d) = (1, 0) between the second and third physical qubits of the last two logical qubits, which results in the state |ψ〉|+〉⊗2 5. The gate CZ on the last two logical qubits, which yields the state |ψ〉(|0+〉 + |1−〉). 6. A four–qubit gate with (c, d) = (1, 0) between the first and the second logical qubit (which cor- responds to the Bell measurement), and another four–qubit gate with (c, d) = (1, 0) between the first and the second logical qubit, which yields the state H |ψ〉 on the third logical qubit, as desired. This shows that we can now perform a general single qubit unitary U , since this can be expressed in its Euler decomposition U(α,β, γ) = Rz(α)HRz(β)HRz(γ) . (63) To generate the logical controlled phase gate CZ we decompose it into Rz rotations and a non–local gate: CZ = R(1)z (− pi 2 )R(2)z (− pi 2 ) diag(1, i, i, 1) . (64) The last gate is implemented by letting the last two logical qubits interact via an auxiliary plaquette with (c, d) = (1, i) (see Fig. 8c). Finally, we distribute the logical qubits in the 3D lat- tice as sketched in Fig. 10. We consider that the ver- tical and the horizontal directions are the spatial ones, and that time increases in the direction going from paper to he reader. Then the logical qubits are initially dis- tribu ed in a 1D vertical array, situated on the left, rear part of the circuit. Single qubit gates move the logical qub ts in the t me direction, whil Hadamard gates move them to the right. At the end of the circuit, the logical qubits are situated in a 1D array at the right, front part of the circuit. We would like to make some comments concerning of this construction. First, the realization of I1 requires first a rescaling of the energy to (c′, d′) = 1, e−2βJ . Then, one has to let J →∞.Comment on this. Single qubit identity Z-Rotation Controlled phase gate BQP-completeness resultsII Construct an (encoded) universal gate set: 14 3 3 3 4 4 5 6 (1, i)(1, e i(α+pi/2)) |ψ〉 |0〉 |0〉 (1, 1) (1, 1) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, i) Rz(α)H |ψ〉 time 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 explanation of the color and the pair of numbers associated to each gate. Green faces mean (c, d) = (1, 1). Gray edges and colored edges indicate edges fixed by the gauge, and the colored numbers indicated the time steps at which they are fixed, in accordance 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/4 for σz ⊗ σz (67) Also need -I Also (c,d)=(0,1) Hadamard gate requires complex parameters (because of the CZL gate). Note also that the logical qubit is processed ahead in time and moves in space. This turns out to be convenient in order to avoid the formation of loops. Third, constraints in the parameter regime and in the distribution of the couplings (due to the encoding). Gemma write this paragraph Thus, this shows that computing the partition function of the 3D Z2 LGT is a non–trivial problem (??). Because the 2D Z2 LGT can be mapped to a 1D Ising model via a duality transfor- mation [3], its complexity is also in P ??. The 3D Z2 LGT can be mapped via a duality transformation to the 3D Ising model [3], does that imply something for the complexity of the latter? (in a very specific parameter regime). On the other hand, recently it was found that the computing the partition function of the 4D Z2 LGT in a real parameter regime is NP–complete [15, 16]. VI. FURTHER RESULTS A. One clean qubit and periodic boundary conditions Here we mention a connection between the results ob- tained on the Ising model in Sec. VB and a scheme for quantum computation called the ‘one clean qubit model’. In the latter, one considers a quantum computa- tion where all qubits but the first one are initialized in the totally mixed state (and the first qubit is, say, in the state |0〉). To this initial state, an arbitrary poly–size quantum circuit may be applied, followed by a single–qubit mea- surement in the final stage of the computation. This one- clean-qubit model comprises a scheme that is believed to be weaker than the full power of quantum computers but stronger than classical computation (although these are unproved assertions). The corresponding complexity class of decision problems that can be solved efficiently with the one-clean-qubit scheme is called DQC1. A standard problem that can be solved using one clean qubit is the problem of estimating normalized traces of unitary qantum circuits. Let U denote a poly–size n–qubit quantum circuit composed of, say, two–qubit gates. Then there exists an efficient quantum algorithm within the one-clean-qubit scheme which returns a num- ber c that provides (with exponentially small probability of failure) an $-approximation of the normalized trace 2−nTr(U) in poly(n) time, for every $ that scales at most Hadamard gate: Note: many spins fixed by the gauge BQP-completeness resultsII  3D      LGTZ2 Verify that there are no loops of spins fixed by the gauge: 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 133 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A projection of the circuit of the 3D Z2 LGT into its spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gauge corresponds in this figure to a loop of colored edges. inverse polynomially with n. The technique is a simple variant of the Hadamard test and we refer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one-clean-qubit paradigm. It thus plays a similar role as the unitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗n we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and where one vertical slice of spins is fixed in the configuration s. Finally, consider the normalized trace of the matrix element U , given by 2−n ∑ s〈s|U |s〉. Due to the above discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 133 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A projection of the circuit of the 3D Z2 LGT into its spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gauge corresponds in this figure to a loop of colored edges. inverse polynomially with n. The technique is a simple variant of the Hadamard test and we refer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one-clean-qubit paradigm. It thus plays a similar role as the unitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗n we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and where one vertical slice of spins is fixed in the configuration s. Finally, consider the normalized trace of the matrix element U , given by 2−n ∑ s〈s|U |s〉. Due to the above discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 56 7 8 3 3 4 59 10 11 2 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 33 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A projectio of the circuit of the 3D Z2 LGT into its spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gau e (black, thin l es), or r fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the g uge corresponds in this figure to a loop of colored edges. inverse polynomially with n. The technique is a simple variant of the Hadamard test and we refer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one-clean-qubit paradigm. It thus plays a similar role as the unitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗n we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and where one vertical slice of spins is fixed in the configuration s. Finally, consider the normalized trace of the matrix element U , given by 2−n ∑ s〈s|U |s〉. Due to the above discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 133 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A proj cti of the circuit of the 3D Z2 LGT into it spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gauge corresponds in this figure to a loop of colored edges. inverse polynomially with n. Th technique is a simple variant of the Hadamard tes a d we r fer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one- lean-qubit paradigm. It thus plays a similar role as the nitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗ we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and wher one vertical slice of spins is fixed in the configuratio s. Finally, consider the normalized trace of the matrix el ment U , given by 2−n ∑ s〈s|U |s〉. Due to the bove discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . BQP-completeness resultsII  3D      LGTZ2 Verify 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-complete Z2 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 133 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A projection of the circuit of the 3D Z2 LGT into its spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gauge corresponds in this figure to a loop of colored edges. inverse polynomially with n. The technique is a simple variant of the Hadamard test and we refer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one-clean-qubit paradigm. It thus plays a similar role as the unitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗n we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and where one vertical slice of spins is fixed in the configuration s. Finally, consider the normalized trace of the matrix element U , given by 2−n ∑ s〈s|U |s〉. Due to the above discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 133 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A projection of the circuit of the 3D Z2 LGT into its spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gauge corresponds in this figure to a loop of colored edges. inverse polynomially with n. The technique is a simple variant of the Hadamard test and we refer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one-clean-qubit paradigm. It thus plays a similar role as the unitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗n we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and where one vertical slice of spins is fixed in the configuration s. Finally, consider the normalized trace of the matrix element U , given by 2−n ∑ s〈s|U |s〉. Due to the above discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 56 7 8 3 3 4 59 10 11 2 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 33 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A projectio of the circuit of the 3D Z2 LGT into its spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gau e (black, thin l es), or r fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the g uge corresponds in this figure to a loop of colored edges. inverse polynomially with n. The technique is a simple variant of the Hadamard test and we refer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one-clean-qubit paradigm. It thus plays a similar role as the unitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗n we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and where one vertical slice of spins is fixed in the configuration s. Finally, consider the normalized trace of the matrix element U , given by 2−n ∑ s〈s|U |s〉. Due to the above discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . 15 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 1 1 2 3 3 4 4 56 7 8 3 3 4 4 59 10 11 12 13 133 3 Rz(α+ pi2 ) Rz(−pi2 )HRz( −pi 2 )H Rz(β + pi 2 ) Rz(γ) Two–qubit gateTwo–qubit gate Single–qubit gate all time steps eiϕσz⊗σzeiϕσz⊗σz FIG. 10: A proj cti of the circuit of the 3D Z2 LGT into it spatial dimension. The figure shows the part of the circuit with a two–qubit gate, a totally general single qubit rotation, and another two–qubit gate. Logical qubits are indicated with a thick black line. All edges in the time direction (going out of the paper) which are boundary to a logical qubit are fixed by the gauge (pink dots). Edges in the spatial direction are either not fixed by the gauge (black, thin lines), or are fixed by the gauge in different time steps 1,. . . , 13, indicated with a color for each time step. Hence, a loop of edges fixed by the gauge corresponds in this figure to a loop of colored edges. inverse polynomially with n. Th technique is a simple variant of the Hadamard tes a d we r fer to the liter- ature. Moreover, the problem of estimating normalized traces of unitary quantum circuits is known to be DQC1– hard. In other words, this problem captures all problems that can be solved efficiently within the one- lean-qubit paradigm. It thus plays a similar role as the nitary ma- trix element problem for BQP. Our results obtained in Sec. VB immediately lead to a complete problem for DQC1 involving Ising partition functions defined on graphs with periodic boundary con- ditions. We limit ourselves to a sketch of the argument. It follows from the discussion in Sec. VB that, for every poly–size quantum circuit U there exists an Ising model defined on a planar circuit graph G (which can be found efficiently), 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, instead of |+〉⊗ we consider the matrix element 〈s|U |s〉 where |s〉 = |s1 . . . sn〉 represents an arbitrary computational basis state. This matrix el- ement now coincides with Zs/γ, where Zs denotes the partition function of the same model (i.e. same graph, couplings and temperature), however considering bound- ary conditions where the left and right boundary spins are fixed in the same configuration s. Such a situation is equivalent to considering a graph G′ where each left boundary spin at the k-th ‘row’ in the graph is identified with its corresponding right boundary spin, and the re- sulting spin is fixed in the state sk, for all k. One thus arrives at an Ising model on a new graph G′ which is obtained from G by enforcing periodic boundary condi- tions, and wher one vertical slice of spins is fixed in the configuratio s. Finally, consider the normalized trace of the matrix el ment U , given by 2−n ∑ s〈s|U |s〉. Due to the bove discussion, this normalized trace may hence be approximated with 1/poly accuracy by 1 2nγ ∑ s Zs. (68) But as Zs is the partition function on G′ with one ver- tical slice of spins fixed in the configuration x, the sum∑ s Zs ≡ Z ′ simply represents the partition function on G′ where these spins are now fully summed out. The quantity Z ′ is hence the full-fledged partition function on G′ of the Ising model with couplings and tempera- ture as before, and without any fixed spins or boundary conditions. We thus arrive at the following result: consider any planar circuit graph G. Let t denote the number of hori- zontal edges in G and let n be its vertical dimension. Let G′ be the graph obtained by enforcing periodic boundary conditions on G (as above). Consider a classical Ising model at inverse temperature β defined on G, where on each site a constant (complex) magnetic field ha is present satisfying eβha = i, and on each edge a constant (complex) coupling Je is present satisfying eβJe = e ipi 4 . BQP-completeness resultsII  3D      LGTZ2 Summary Summary  Completeness Z = 〈α |ψ 〉  Complexity Z = 〈L |C |R 〉 ✓ any dimensions ✓ q-level systems, any q ✓ any many-body int. real Abelian discrete Z4DZ2LGT(J, J ′) = Zany classical spin model(J) Six vertex model Potts model 3D       LGTZ2 Approximating Z of is BQP-complete in a certain complex parameter regime Thank 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) C om pl et en es s C om pl ex ity ** ** ** **

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 22 2
Japan 8 0
United States 4 0
Canada 2 0
City Views Downloads
Beijing 20 0
Tokyo 8 0
Mountain View 3 0
Vancouver 2 0
Shenzhen 2 2
Ashburn 1 0

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

Share

Share to:

Comment

Related Items