Tensor network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits channels protocols open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae whereas the second is Penroses tensor contraction algorithm returning the number of 3edgecolorings of 3regular planar graphs.
['Quantum Physics', 'Condensed Matter - Disordered Systems and Neural Networks', 'General Relativity and Quantum Cosmology', 'High Energy Physics - Theory', 'Mathematical Physics']
Tensor Networks in a Nutshell
{'Quantum Tensor Networks in a Nutshell': "Jacob Biamonte 1, 2, ∗ and Ville Bergholm 1, † 1 Quantum Software Initiative Skolkovo Institute of Science and Technology, Skoltech Building 3, Moscow 143026, Russia 2  \nInstitute for Quantum Computing  \nUniversity of Waterloo, Waterloo, N2L 3G1 Ontario, Canada  \nTensor network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states, and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits, channels, protocols, open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions, the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae, whereas the second is Penrose's tensor contraction algorithm, returning the number of 3 -edge-colorings of 3 -regular planar graphs.  \n<!-- image -->", '1. QUANTUM LEGOS': "Tensors are a mathematical concept that encapsulates and generalizes the idea of multilinear maps, i.e. functions of multiple parameters that are linear with respect to every parameter. A tensor network is simply a countable collection of tensors connected by contractions. 'Tensor network methods' is the term given to the entire collection of associated tools, which are regularly employed in modern quantum information science, condensed matter physics, mathematics and computer science.  \nTensor networks come with an intuitive graphical language that can be used to reason about them. This diagrammatic language dates back to at least the early 1970s by Roger Penrose [1]. These methods have seen many advancements and adaptations to different domains of physics, mathematics and computer science. An important milestone was David Deutsch's use of the diagrammatic notation in quantum computing, developing the quantum circuit (a.k.a. quantum computational network) model [2]. Quantum circuits are a special class of tensor networks, in which the arrangement of the tensors and their types are restricted. A related diagrammatic language slightly before that is due to Richard Feynman [3]. The quantum circuit model-now well over two decades old-is widely used to describe quantum algorithms and their experimental implementations, to quantify the resources they use (by e.g. counting the quantum gates required), to classify the entangling properties and computational power of specific gate families, and more.  \nThere is now a lot of excitement about tensor network algorithms-for reviews see [416]. Some of the best known applications of tensor networks are 1D Matrix Product States (MPS), Tensor Trains (TT), Tree Tensor Networks (TTN), the Multi-scale Entanglement Renormalization Ansatz (MERA), Projected Entangled Pair States (PEPS)-which generalize matrix product states to higher dimensions-and various other renormalization methods [5-8, 12, 15, 17]. The excitement is based on the fact that certain classes of quantum systems can now be simulated more efficiently, studied in greater detail, and this has opened new avenues for a greater understanding of certain physical systems.  \nThese methods approximate a complicated quantum state using a tensor network with a simplistic, regular structure-essentially applying lossy data compression that preserves the most important properties of the quantum state. To give the reader a rough idea how these methods work, below we conceptually depict how the quantum state ψ could be represented (or approximated) using tensor networks in various ways.  \n<!-- image -->  \nWe assume that most readers will have a basic understanding of some quantum theory, linear algebra and tensors. In Appendix A, we provide a short mathematical definition of tensors and tensor products. However, readers may wish to skip these definitions and for now proceed with a more informal or intuitive understanding of the idea.  \nThere are several notational approaches to tensors. We begin by using abstract index notation, and then explain how it connects to the Dirac notation used in quantum computing. The connection between tensor networks and quantum circuits is elucidated at the end of Section 2.", '2. FROM TENSORS TO NETWORKS': "- 1. Drawing tensors. In the tensor diagram notation, a tensor is a labelled shape such as a box, oval or triangle, with zero or more open output legs (or arms ) pointing up, and zero or more open input legs pointing down. Individual arms and legs each correspond to upper and lower indices, respectively. 1 The arm and leg wires may be labelled with the indices they represent, or with the vector spaces they correspond to, if necessary. An order-(0 , 0) tensor without any open arms or legs is simply a complex number.  \ni k j (a) (b) A k j i (c) T (2)  \nFor example, diagram (a) above represents the tensor ψ i with a single upper index (a vector), diagram (b) the tensor A j k (a matrix), and diagram (c) the tensor T i jk .  \n- 2. Tensor juxtaposition. When two or more disconnected tensors appear in the same diagram they are multiplied together using the tensor product. In quantum physics notation, they would have a tensor product sign ⊗ between them. In the abstract index notation the tensor product sign is omitted.  \nTensors can be freely moved past each other. This is sometimes called planar deformation.  \n<!-- image -->  \nFrom the diagram above, using equations we have  \n( 1 1 ⊗ B )( A ⊗ 1 1) = A ⊗ B = ( A ⊗ 1 1)( 1 1 ⊗ B ) , (4)  \nwhere we make use of the wire also playing the role of the identity tensor 1 1-detailed in Section 3. As we shall soon see, wires are allowed to cross tensor symbols and other wires, as long as the wire endpoints are not changed. This is one reason why tensor diagrams are often simpler to deal with than their algebraic counterparts.  \n<!-- image -->  \nIn the diagram above we did not label the wires, since it is an arbitrary assignment. If we did, we could for example denote it as Q deg b R f ac .  \n- 3. Connecting wires. Connecting two tensor legs with a wire means that the corresponding indices are contracted (summed over).  \n(a)  \n(b)  \n<!-- image -->  \nIn diagram (a) above we find a matrix multiplying a vector which results in another vector.  \nDiagram (a) is equivalent to the expression  \nA j i ψ i = φ j , (7)  \nwhere we notice that the wire labeled i is fully connected, and hence the corresponding index is summed over. We used the Einstein summation convention , in which any index that appears exactly twice in a term is summed over.  \n- In (b) we face a slightly more complicated case, departing from familiar vectors and matrices, contracting two indices between two order-3 tensors. Diagram (b) is equivalent to  \nΓ i jk ∆ jk l = B i l . (8)  \nTogether, two or more tensors in a diagram form a tensor network . If none of the tensors have any open arms or legs the network is said to be fully contracted: it evaluates to some complex number, a scalar.  \nYou have probably noticed that we are being strict and are leaving spaces to identify the order of indices as we read them left to right across the page (e.g. in Γ i jk we have i , followed by jk ). In Section 3 we are going to talk about this in more detail, and justify why it is not necessary: we are doing it here for ease of illustration.  \nSome authors like to put arrows on the tensor diagram wires [18], to denote the difference between vector spaces and their duals. 2 In this work we mostly deal with finite-dimensional vector spaces over real or complex numbers, and for each vector space V we pick a preferred basis (called the computational basis in quantum computing). The basis can be used to define an inner product, turn V into a Hilbert space, and establish a bijective mapping between V and its dual V ∗ . We then use this mapping to equate dual vectors in V ∗ with their counterparts in V . In this case arrows on the wires add nothing essential, so we omit them.  \n- 4. Connection to quantum computing notation. As mentioned, tensors are multilinear maps. They can be expanded in any given basis, and expressed in terms of their components. In quantum information science one often introduces a computational basis {| k 〉} k for each Hilbert space and expands the tensors in it, using kets ( | 〉 ) for vectors and bras ( 〈 | ) for dual vectors:  \nT = ∑ ijk T i jk | i 〉〈 jk | . (9)  \nHere T i jk is understood not as abstract index notation but as the actual components of the tensor in the computational basis. In practice there is little room for confusion. The Einstein summation convention is rarely used in quantum information science, hence we write the sum sign explicitly.  \nSo far we have explained how tensors are represented in tensor diagrams, and what happens when wires are connected. The ideas are concluded by four examples; we urge the reader to work through the examples and check the results for themselves.  \nThe first example introduces a familiar structure from linear algebra in tensor form. The next two examples come from quantum entanglement theory-see connecting tensor networks with invariants [19, 20]. The fourth one showcases quantum circuits, a subclass of tensor networks widely used in the field of quantum information. The examples are chosen to illustrate properties of tensor networks and should be self-contained.  \nExample 1 (The glyph[epsilon1] tensor) . A tensor is said to be fully antisymmetric if swapping any pair of indices will change its sign: A ij = -A ji . The glyph[epsilon1] tensor is used to represent the fully antisymmetric Levi-Civita symbol, which in two dimensions can be expressed as  \nglyph[epsilon1] 00 = glyph[epsilon1] 11 = 0 , glyph[epsilon1] 01 = -glyph[epsilon1] 10 = 1 . (10)  \nThe glyph[epsilon1] tensor can be used to compute the determinant of a matrix. In two dimensions we have  \ndet( S ) = glyph[epsilon1] ij S i 0 S j 1 . (11)  \nUsing this we obtain  \n= S S · det S (12)  \nas can be seen by labeling the wires in the diagram. In equational form this is  \nglyph[epsilon1] ij S i m S j n = det( S ) glyph[epsilon1] mn . (13)  \nIn terms of quantum mechanics, glyph[epsilon1] corresponds to the two-qubit singlet state:  \n1 √ 2 | glyph[epsilon1] 〉 = 1 √ 2 ( | 01 〉 - | 10 〉 ) . (14)  \nThis quantum state is invariant under any transformation of the form U ⊗ U , where U is a 2 × 2 unitary, as it only gains an unphysical global phase factor det( U ).  \nExample 2 (Concurrence and entanglement) . Given a two-qubit pure quantum state | ψ 〉 , its concurrence C ( ψ ) = | C ' ( ψ ) | is the absolute value of the following tensor network expression [21]:  \nC'( ) = (15)  \nHere ψ is the complex conjugate of ψ in the computational basis. The concurrence is an entanglement monotone, a function from states to nonnegative real numbers that measures how entangled the state is. | ψ 〉 is entangled if and only if the concurrence is greater than zero.  \nConsider now what happens when we act on | ψ 〉 by an arbitrary local unitary operation, i.e. | ψ ' 〉 = ( U 1 ⊗ U 2 ) | ψ 〉 . Using the result of Example 1 we obtain  \nC (( U 1 ⊗ U 2 ) | ψ 〉 ) = C ( ψ ) | det( U 1 ) det( U 2 ) | . (16)  \nDue to the unitarity | det U 1 | = | det U 2 | = 1, which means that the value of the concurrence is invariant (i.e. does not change) under local unitary transformations. This is to be expected, as local unitaries cannot change the amount of entanglement in a quantum state. We will revisit concurrence in Example 11.  \nMore complicated invariants can also be expressed as tensor networks [19]. We will leave it to the reader to write the following network as an algebraic expression:  \n<!-- image -->  \nIf | ψ 〉 is a 3-qubit quantum state, τ ( ψ ) = 2 | τ ' ( ψ ) | represents the entanglement invariant known as the 3-tangle [22]. It is possible to form invariants also without using the epsilon tensor. For example, the following expression represents the 3-qubit entanglement invariant known as the Kempe invariant [23]:  \nK ( ψ ) = ψ ijk ψ ilm ψ nlo ψ pjo ψ pqm ψ nqk . (18)  \nThe studious reader would draw the equivalent tensor network.  \nExample 3 (Quantum circuits) . Quantum circuits are a restricted subclass of tensor networks that is widely used in the field of quantum information. In a quantum circuit diagram each horizontal wire represents the Hilbert space associated with a quantum subsystem, typically a single qubit. The tensors attached to the wires represent unitary propagators acting on those subsystems, and are called quantum gates . Additional symbols may be used to denote measurements. The standard notation is described in [24].  \nHere we will consider a simple quantum circuit that can generate entangled Bell states. It consists of two tensors, a Hadamard gate ( H ) and a controlled NOT gate ( CNOT , denoted by the symbol inside the dashed region):  \ni j k l m /uniF048 (19)  \nThe CNOT and Hadamard gates are defined as  \nCNOT = ∑ | a, a ⊕ b 〉〈 a, b | and  \nH = √ 2 ∑ ( -1) ab | a 〉〈 b | ,  \nab (20) 1 ab (21)  \nwhere the addition in the CNOT is modulo 2. 3 The reader should verify that acting on the quantum state | 00 〉 the above circuit yields the Bell state 1 √ 2 ( | 00 〉 + | 11 〉 ), and acting on | 11 〉 it yields the singlet state 1 √ 2 ( | 01 〉 - | 10 〉 ).  \nExample 4 ( COPY and XOR tensors) . One can view the CNOT gate itself as a contraction of two order-three tensors [25]:  \n<!-- image -->  \nThe top tensor ( · with three legs) is called the COPY tensor. It equals unity when all the indices are assigned the same value (0 or 1), and vanishes otherwise:  \n<!-- image -->  \nHence, COPY acts to copy the binary inputs 0 and 1:  \n<!-- image -->  \nThe bottom tensor ( ⊕ with three legs) is called the parity or XOR tensor. It equals unity when the index assignment contains an even number of 1s, and vanishes otherwise:  \n<!-- image -->  \nThe XOR and COPY tensors are related via the Hadamard gate as  \n= 1 √ 2 H H H (26)  \nThus one can think of XOR as being a (scaled) copy operation in another basis:  \n1 √ 2 XOR | + 〉 = | + 〉| + 〉 , (27a) 1 √ 2 XOR |-〉 = |-〉|-〉 , (27b)  \nwhere | + 〉 := H | 0 〉 and |-〉 := H | 1 〉 . In terms of components,  \nCOPY ij = (1 -i )(1 -j )(1 -k ) + ijk,  \nk (28a) XOR qr s = 1 -( q + r + s ) + 2( qr + qs + sr ) -4 qrs. (28b)  \nThe CNOT gate is now obtained as the tensor contraction  \n∑ m COPY qm i XOR r mj = CNOT qr ij . (29)  \nThe COPY and XOR tensors will be explored further in later examples and have many convenient properties [26, 27, 39].", '3. BENDING AND CROSSING WIRES': "' It now ceases to be important to maintain a distinction between upper and lower indices. ' - Roger Penrose, 1971 [1]  \n- 1. Cups and caps. As explained in the previous section, wires are used to denote the contraction of pairs of tensor indices. However, it is often useful to interpret certain wire structures as independent tensors of their own. We start with three of these special wire tensors that allow one to rearrange the arms and legs of another tensor:  \nij (a) (b) (c) ij = = = (30)  \nThe identity tensor (a) is used for index contraction by connecting the corresponding legs. The cup (b) and the cap (c) raise and lower tensor indices by bending the corresponding tensor legs. 4 Expanding them in the computational basis we obtain  \n1 1 = ∑ ij δ i j | i 〉〈 j | = ∑ k | k 〉〈 k | , (31)  \n|∪〉 = ∑ ij δ ij | ij 〉 = ∑ k | kk 〉 , (32)  \n〈∩| = ∑ ij δ ij 〈 ij | = ∑ k 〈 kk | . (33)  \nIn a quantum information context, the cup also corresponds to an (unnormalized) Bell state, generalized so that it is not defined just for qubits.  \n- 2. Snake equation. One can raise and then lower an index or vice versa, which amounts to doing nothing at all. This idea is captured diagrammatically by the so called snake or zig-zag equation [1].  \n= = (34)  \nIn abstract index notation it is expressed succinctly as δ ij δ jk = δ i k = δ kj δ ji .  \n- 3. SWAP gate. Crossing two wires (as in diagram (a) below) can be thought of as swapping the relative order of two vector spaces. It corresponds to the SWAP gate used in quantum computing. If both wires represent the same vector space, it can be alternatively understood as swapping the states of the two subsystems.  \n(a) (b) = (35)  \nEquation (b) illustrates that the SWAP operation is self inverse. It may be written as SWAP ij kl = δ j k δ i l , or expanded in the computational basis as SWAP = ∑ ij | ij 〉〈 ji | . It also has a well-known implementation in terms of three CNOT gates as  \n= (36)  \nSWAP is the simplest nontrivial example of a permutation tensor. More complicated permutations may be built out of the δ i j tensors in an obvious way. We will return to this idea in Example 7.  \n- 4. Transpose. Given A i j , we may reverse the positions of its indices using a cup and a cap. This is equivalent to transposing the corresponding linear map in the computational basis:  \nA = A (37)  \n- 5. Trace. In the tensor diagram notation, trace is given by appropriately joining all the output wires of a tensor to corresponding input wires. Diagram (a) below represents the trace A i i . Diagram (b) represents the trace B iq iq .  \n(a) A (b) B (c) C i i q p i j k (38)  \nPartial trace means contracting only some of the outputs with their corresponding inputs, such as with the tensor C ijk pk shown in diagram (c).  \nExample 5 (Partial trace) . The following is an early rewrite representing entangled pairs due to Penrose [28].  \n<!-- image -->  \nThe diagram on the left represents the partial trace of | ψ 〉〈 ψ | over the second subsystem. Readers can prove that this equality follows by interpreting the bent wires as cups and caps, and the crossing wires as SWAP s.  \nExample 6 (Partial trace of Bell states) . Continuing on from Example 5, if we choose | ψ 〉 = |∪〉 , i.e. | ψ 〉 is an unnormalized Bell state, we obtain  \n<!-- image -->  \nExample 7 (Relation between glyph[epsilon1] and SWAP ) . For any order-2 tensor T ij we can define its antisymmetrization as T [ ij ] = 1 2 ( T ij -T ji ). Here we used the notation of putting brackets around a group of indices-[ ij ]-to denote their antisymmetrization. Only indices of the same dimension may be antisymmetrized (otherwise the expression would be undefined for some index values).  \nThe fully antisymmetric glyph[epsilon1] tensor from Example 1 has an interesting relation to the SWAP gate:  \n= -(41)  \nor alternatively  \nglyph[epsilon1] kl glyph[epsilon1] ij = δ k i δ l j -δ k j δ l i . (42)  \nIt is now easy to show that for any tensor T ij (for which both indices are two-dimensional) we can write T [ kl ] = 1 2 glyph[epsilon1] kl glyph[epsilon1] ij T ij .  \nBoth the concept of antisymmetrization and the epsilon tensor can be extended to more than two indices. The antisymmetrizer of n d -dimensional vector spaces is an order-( n, n ) tensor A i 1 ··· i n j 1 ··· j n . It can be expressed as the sum of all n -element permutations multiplied by their signatures. 5 It antisymmetrizes n d -dimensional indices by contraction:  \nT [ i 1 ··· i n ] = A i 1 ··· i n j 1 ··· j n T j 1 ··· j n . (43)  \nWhen d < n the only possible antisymmetric combination is a zero tensor, and the corresponding A vanishes identically.  \nFor the general order-(0 , n ) epsilon tensor, all the n vector spaces need to be n -dimensional. We then define glyph[epsilon1] 012 ... ( n -1) = 1, and all the other components are fixed by requiring complete antisymmetry, i.e. change of sign under the interchange of any two indices. In particular, if any index value is repeated the corresponding component is zero. Now 1 n ! glyph[epsilon1] i 1 ··· i n glyph[epsilon1] j 1 ··· j n is an antisymmetrizer.  \nWe shall use order-three epsilon tensors to count graph edge colorings by tensor contraction in Section 6 2.  \nExample 8 (Quantum circuits for cups and epsilon states) . The quantum circuit from Example 3 is typically used to generate entangled qubit pairs. For instance, acting on the state | 00 〉 yields the familiar Bell state-as a tensor network, this is equal to a normalized cup. Here we also show the mathematical relationship the XOR and COPY tensors have with the cup (here | + 〉 := | 0 〉 + | 1 〉 ):  \n<!-- image -->  \nSimilarly, one can use the circuit (19) to generate the epsilon state. Let us denote the Pauli matrices by X := | 0 〉〈 1 | + | 1 〉〈 0 | , Y := -i | 0 〉〈 1 | + i | 1 〉〈 0 | and Z := | 0 〉〈 0 | - | 1 〉〈 1 | . The  \nZ gate commutes with the COPY tensor, and the X or NOT gate (which we denote with ⊕ ) commutes with XOR . Commuting those tensors to the right hand side, allows us to apply Eq. (44). Making use of the Pauli algebra identity ZX = iY , one recovers the epsilon state:  \n<!-- image -->  \nExample 9 (Map-state duality) . The index raising and lowering using cups and caps can be interpreted as a linear map between bipartite vectors and linear maps leading to a relationship between quantum states and operators acting on them. We will start with the linear map A . Raising the second index using a cup (a) yields a tensor with two output legs (b), i.e. something that can be interpreted as a bipartite vector | A 〉 .  \n(a) (b) A (c) A = = A (46)  \nFinally, using the snake equation (34) together with the equality (37) we can see that this is equal to (c) the transposed map A glyph[latticetop] with a cup raising the input index to the other side. Indeed, a tensor may be moved around a cup or a cap by transposing it. The relationship (46) arises in practice in the following scenario from quantum information science:  \n<!-- image -->  \nHere an entangled state | ψ 〉 acted on by a map A can instead be viewed as a map ψ acting on a state | A glyph[latticetop] 〉 . 6 This is a diagrammatic form of map-state duality underlying bipartite entanglement evolution [29, 30]. See e.g. the survey [15] which includes a detailed discussion on reshaping tensors.  \n- 6. Dagger and complex conjugation. If the order-( p, q ) tensor T is a map between Hilbert spaces, we may define its (Hermitian) adjoint T † , an order-( q, p ) tensor, using the inner product: 〈 x, T y 〉 = 〈 T † x, y 〉 for all x, y . Diagrammatically the adjoint is obtained by mirroring the tensor network such that input and output wires switch places, the relative order of the tensors in the diagram is reversed, and each tensor symbol is decorated with a dagger (with T †† = T ).  \nSimilarly, the dagger operation maps Hilbert space ket vectors one-to-one to their dual bra vectors (and vice versa) in the sense of the Riesz representation theorem. This is denoted | a 〉 † = 〈 a | . Note that we have been using this notation implicitly, as it should be familiar to many readers from basic quantum mechanics.  \nThe dagger is an antilinear (or conjugate-linear) operation, ( cT + dU ) † = c T † + dU † , since we have to take the complex conjugate of the scalars c and d . This means that it cannot be represented by the linear cups and caps alone, unlike the transpose. However, it can be represented as transpose together with complex conjugation in the same basis. This is summarized in the following adjoint square .  \n<!-- image -->  \nNote that some authors mark one of the corners of each tensor box, and use the convention that mirroring a diagram across the horizontal plane corresponds to the † operation. We do not adhere to this convention and instead place the dagger on the symbol such as A → A † .  \nFor kets and bras, bending a wire on a ket yields the complex conjugate of the corresponding bra, and vice versa.  \n= (49)  \n7. Index position. Now we will consider the set of operations formed by bending tensor wires forwards and backwards using cups and caps, as well as exchanging the order of wires using SWAP . If one conceptualizes a tensor as an array of numbers, these transforms correspond to array reshapes and reorderings. As the snake equation (34) shows, the action of cups and caps can be inverted, and SWAP is self inverse (35). This means that all possible configurations of a tensor's wires obtained using these operations are isomorphic.  \nAs an example, given a tensor T i j one can use cups and caps to naively rearrange the index elevations and positions, arriving at  \nT i j , T ij , T ij , T j i , T j i , T ji , T ji and T i j , (50)  \nfor a total of eight possible reshapes. If the tensor has more than two indices, one can additionally use SWAP s to arrange the indices in any relative order. Thus one might think that for a general n -index tensor there are n ! · 2 n different ways of arranging the indices ( n ! different permutations of the indices, with each index being either up or down). However, this way one overcounts the number of index configurations that are truly different. In our  \nexample, in fact T i j = T i j and T j i = T j i , as can be seen from the diagram below:  \nT j i = = (51)  \nConsequently, the tensor T i j in actuality only has six unique reshapes:  \n(a) (d) (b) (e) (c) (f) T i j T ij Tij T j i = = = = = = (52)  \nMore generally, one finds that the number of unique reshapes generated by cups, caps and SWAP s for an order-( p, q ) tensor T i 1 ··· i p j 1 ··· j q is ( p + q +1)!.", '4. DIAGRAMMATIC SVD': "In this section, we explain the diagrammatic version of the singular value decomposition (SVD). This method is at the heart of many numerical simulation algorithms in wide use today-we are explaining it as a prelude leading to Section 5. The SVD factors an arbitrary order-(1 , 1) tensor into well defined building blocks with simple properties: (i) an order-(1 , 1) diagonal tensor storing the singular values, and (ii) two order-(1 , 1) unitary tensors. As several tensor legs can always be grouped together to form a single leg, the method works for any tensor of order two or higher.  \nInterpreting order-(1 , 1) tensors as linear maps (or simply as matrices), we may use the SVD to factor any tensor T : A → B (for vector spaces A and B ) as  \nT b a = U b j Σ j i V i a , (53)  \nwhere U and V are unitary, and Σ is real, non-negative, and diagonal in the computational basis. Σ has the singular values { σ k } k of T on its diagonal, typically arranged in a nonincreasing order: σ 1 ≥ σ 2 ≥ . . . ≥ σ min(dim A, dim B ) ≥ 0. It can be expanded as  \nΣ = ∑ k σ k | k 〉 B 〈 k | A . (54)  \nDiagrammatically this is represented as  \n= U A A V /uni03A3 A B B B T . (55)  \nAs will be seen in the next section, the SVD is centrally employed in the efficient representation of certain quantum states by tensor networks. The idea is to represent a small but physically relevant portion of the Hilbert space-such as low entanglement states-by repeated application of the SVD paired with low-rank approximations.  \nThe rank of a matrix T is the number of non-zero singular values it has. To determine its optimal rankr approximation (with r < rank( T )), we can turn to a classic theorem by Eckart and Young which was generalized by Mirsky. Given the SVD T = U Σ V † , we will discard rank( T ) -r smallest singular values in Σ by setting them to zero, obtaining Σ ' . This process is often called trimming.  \nThis gives rise to T ' = U Σ ' V † , an approximation of T . The Eckart-Young-Mirsky theorem states that  \n‖ T -T ' ‖ = min rank( ˆ T ) ≤ r ‖ T -ˆ T ‖ (56)  \nfor any unitarily invariant matrix norm. 7 Here ˆ T is any approximation to T of the same or lesser rank as T ' . This implies that truncating or trimming Σ in this way yields as good of an approximation as one can expect. In the following section, we will specifically consider the induced error for such an approximation.  \nUsing the wire bending techniques from Section 3, we immediately obtain the Schmidt decomposition as a corollary to the SVD:  \n<!-- image -->  \nGiven a vector | ψ 〉 ∈ A ⊗ B (for example a ket vector describing a pure state of a bipartite quantum system), we may use the snake equation to convert it into a linear map ψ : A → B (inside the dashed region). Now we apply the SVD on ψ as above. Diagram reorganization leads to the diagrammatic Schmidt decomposition  \n| ψ 〉 A ⊗ B = ∑ i σ i | ϕ i 〉 A | φ i 〉 B . (58)  \nThe singular values { σ k } k now correspond to the Schmidt coefficients. If | ψ 〉 is normalized, we have ∑ k σ 2 k = 1.  \nExample 10 (Entanglement topology) . The topology of the bipartite quantum state | ψ 〉 depends solely on the Schmidt coefficients { σ k } k .  \n<!-- image -->  \nIf the coefficients are all equal, we may replace the diamond in (a) with a cup tensor times a scaling factor as in diagram (b). This corresponds to a maximally entangled state. In the other extreme, illustrated in diagram (c), we have just one nonzero Schmidt coefficient σ 1 = 1. In this case the diagram breaks into two pieces and thus corresponds to a factorizable state. The number of nonzero Schmidt coefficients is called the Schmidt rank of the decomposition-see Def. 17 for the relation with R'enyi entropy of order zero.  \nExample 11 (Concurrence-part II) . Continuing on from Example 2, one can apply the Schmidt decomposition to the tensor network defining the concurrence of a two-qubit state | ψ 〉 . We obtain  \n<!-- image -->  \nand thus  \n= = C'( ) = ·det(  )·det(  ) (60)  \nC ( ψ ) = | C ' ( ψ ) | = ∣ ∣ Tr(( glyph[epsilon1] Σ) 2 ) ∣ ∣ = 2 σ 1 σ 2 = 2 | det( ψ ) | . (61)  \nThe unitaries glyph[squaresolid] and glyph[square] vanish from the expression since | det( glyph[squaresolid] ) | = | det( glyph[square] ) | = 1. Given the basis expansion of the state,  \n| ψ 〉 = a | 00 〉 + b | 01 〉 + c | 10 〉 + d | 11 〉 , (62)  \nits two Schmidt coefficients are given as  \nσ 2 k = 1 2 ( 1 + ( -1) k +1 √ 1 -4 | ad -bc | 2 ) . (63)  \nExample 12 (Purification backwards) . For any bipartite ket vector | ψ 〉 , the partial trace of | ψ 〉〈 ψ | yields a positive semidefinite operator. We can see this by using the Schmidt decomposition, and then reorganizing the diagram so that two of the unitaries cancel:  \n<!-- image -->  \nOn the right hand side we have an eigendecomposition of a square matrix with strictly nonnegative eigenvalues { σ 2 k } k , which can be interpreted as a density matrix if | ψ 〉 is normalized. Conversely, any density matrix representing a mixed quantum state can be purified , or expressed as the partial trace of a bipartite pure state.", '5. MATRIX PRODUCT STATES': "Matrix product states (MPSs) are quantum states presented as a linear chain or ring of tensors. Any quantum state can be exactly represented in this form and the representation is known to approximate a class of 1D gapped systems efficiently [31]. We will explain the basic ideas of the MPS representation here and point the reader to [6, 7] and the references therein for additional information.  \nGiven an n -party quantum state | ψ 〉 , fully describing this state generally requires an amount of information (or computer memory) that grows exponentially with n . If | ψ 〉 represents the state of n qubits,  \n| ψ 〉 = ∑ ij ··· k ψ ij ··· k | ij · · · k 〉 , (65)  \nthe number of independent coefficients ψ ij ··· k in the basis expansion in general would be 2 n which quickly grows into a computationally unmanageable number as n increases. The goal is to find an alternative representation of | ψ 〉 which is less data-intensive. We wish to write | ψ 〉 as  \n| ψ 〉 = ∑ ij ··· k Tr( A [1] i A [2] j · · · A [ n ] k ) | ij · · · k 〉 , (66)  \nwhere A [1] i , A [2] j , . . . , A [ n ] k are indexed sets of matrices. Calculating the components of | ψ 〉 then becomes a matter of calculating the products of matrices, hence the name matrix product state .  \nIf the matrices are bounded in size, the representation becomes efficient in the sense that the amount of information required to describe them is only linear in n . The point of the method is to choose these matrices such that they provide a good (and compact) approximation to | ψ 〉 . For instance, if the matrices are at most χ by χ , the size of the representation scales as ndχ 2 , where d is the dimension of each subsystem.  \nWithout loss of generality, we will now show how to obtain an MPS representation of an arbitrary four-party state | ψ 〉 . The key ingredient is the recursive application of the singular value decomposition (SVD) presented in Section 4. We start by considering the tensor which represents the state vector. We select a bipartition that separates one leg from the rest (starting at either end), and apply the SVD. This process is then repeated, traversing the entire tensor. This results in a 1D tensor network representation of the state, as shown below.  \n<!-- image -->  \nFinally the tensors are grouped-though the grouping has some ambiguity-resulting in the typical form shown below.  \n<!-- image -->  \nWe note that one can recover the form in Eq. (66) as  \n| ψ 〉 = ∑ ijkm A [1] i A [2] j A [3] k A [4] m | ijkm 〉 . (69)  \nIn this case the first and last sets of matrices A [1] i and A [4] m have just a single row and a single column, respectively, so the product always yields a scalar and the trace is not required. The tensor network in Eq. (68) is called an MPS with open boundary conditions. MPSs also come with periodic boundary conditions, in which case the tensors form a ring instead of a chain, and the trace represents the contraction that closes the ring.  \nYou might have noticed that we made a choice to perform the factorization starting from the left of the tensor and applying the SVD successively on tensors as we moved to the right. This apparent ambiguity has been characterized in detail [32]. For open boundary conditions as have been considered here, there is a canonical choice unique up to degeneracies in the spectrum of local reduced density operators [32].  \nFor a general n -qubit quantum state it can be shown that the MPS matrix size can be bounded by χ = 2 glyph[floorleft] n/ 2 glyph[floorright] , which still grows exponentially as expected. A compact approximate representation is obtained by choosing a cutoff value ξ for the singular values across each partition, or a maximum number χ of singular values to be kept-see Example 13. This allows one to compress data by truncating the Hilbert space and is at the heart of the MPS algorithms. If an MPS is cut into two parts, the Schmidt rank of the decomposition, describing the degree of entanglement between the parts, is always ≤ χ , the dimension of the internal wire that was cut-see Example 10 for Schmidt rank and set q = 0 in Eq. (86) for the connection to entropy.  \nAbove we have illustrated how to obtain the MPS representation of any pure quantum state, but it is normally not practical to factor states in this way for computational reasons. Instead, efficient MPS-generating algorithms are given an indirect, compact description of a state e.g. in the form of a nearest-neighbor Hamiltonian whose ground state we are interested in, and they then iteratively produce an MPS that closely approximates that state. The seminal algorithm of this type is the Density Matrix Renormalization Group (DMRG), which essentially works as a variational method in MPS space. Another class of algorithms can efficiently time-evolve MPSs under a nearest-neighbor Hamiltonian. One of the most used methods of this type is Time-Evolving Block Decimation (TEBD).  \nExample 13 (MPS approximation error) . As explained, matrix product state algorithms employ repeated application of the singular value decomposition. The size of the representation can be reduced by lossy truncation in one of two ways. Each of these rely on truncation of singular values. For a fixed rank, the Eckart-Young-Mirsky theorem-from the last Section-tells us that truncation of the singular values is the best approximation that one can expect.  \nIn the first approximation, one can simply discard some fixed number of lowest singular values and their corresponding vectors-in other words, we will fix the dimension χ of all internal wires. In another approximation-which we will consider here-one will pick a cutoff value ξ , and truncate all singular values which are less than this. Such a cutoff value is not guaranteed to provide a useful partition of the singular values-e.g. it could be smaller than the smallest singular value. Here we will analyze the errors of this truncation assuming this cutoff partitions the singular values-which in practice is very often the case.  \nGiven a bipartite state | ψ 〉 we write  \n| ψ 〉 = k ∑ i =1 σ i | u i 〉| v i 〉 = k ∑ i =1 σ i | i 〉 . (70)  \nwhere to simplify the notation we write | u i 〉| v i 〉 as just | i 〉 . We order the singular values in  \na non-decreasing sequence and introduce a cutoff ξ > 0:  \n0 < σ 1 ≤ σ 2 ≤ σ 3 ≤ · · · ≤ σ n ≤ ξ ≤ σ n +1 ≤ · · · ≤ σ k . (71)  \nAs a heuristic, the small cutoff ξ can be chosen such that ξ < 1 √ dim H where H is the vector space acted on by | ψ 〉 -you could also write ξ < 1 √ d q where d is the dimension of q constituent spaces.  \nAnd then we will partition our space in terms of the n singular values less than ξ and the k -n ones that are greater than ξ .  \n| ψ 〉 = n ∑ i =1 σ i | i 〉 + k ∑ j = n +1 σ j | j 〉 = n ∑ i =1 σ i | i 〉 + | ψ ' 〉 , (72)  \nwhere | ψ ' 〉 in (72) represents a (so far, non-normalized) approximation to | ψ 〉 . To understand the limits of validity of this approximation, we consider the inequality  \nn ∑ i =1 σ i ≤ n · σ n ≤ n · ξ, (73)  \nand hence n · σ 2 n ≤ n · ξ 2 .  \nProvided ξ is small, and for constant n we can return to (72) and consider another normalized but otherwise arbitrary vector | φ 〉 (element of the same space as | ψ 〉 and | ψ ' 〉 )  \n|〈 φ | ψ -ψ ' 〉| = ∣ ∣ ∣ ∣ ∣ n ∑ i =1 σ i 〈 φ | i 〉 ∣ ∣ ∣ ∣ ∣ ≤ n ∑ i =1 σ i |〈 φ | i 〉| ≤ n ∑ i =1 σ i ≤ n · ξ, (74)  \nwhich scales linearly in the upper-bound of the error independent of | φ 〉 .  \nIt's common to introduce a function O ( ξ ) to collect terms up to a constant that approach zero no slower than O 's argument. So (74) simply says that the absolute value of the difference between | ψ ' 〉 and | ψ 〉 projected onto 〈 φ | is bounded by a function proportional to ξ . From this we can readily conclude that the error in the approximation considered here is linear in ξ -or in other words, the error scales at most as O ( ξ ).  \nHowever, as | ψ 〉 is normalized, we note that  \n〈 ψ | ψ 〉 = n ∑ i =1 σ 2 i + k ∑ j = n +1 σ 2 j = 1 , (75)  \nand then calculate the inner product  \n〈 ψ | ψ ' 〉 = k ∑ j = n +1 σ 2 j = 1 -n ∑ i =1 σ 2 i ≥ 1 -nξ 2 = 1 + O ( ξ 2 ) . (76)  \nWe hence conclude that the error in the inner product is only quadratic. In fact, if we normalize | ψ ' 〉 → | ψ '' 〉 and calculate  \n|〈 ψ | ψ '' 〉| 2 = 1 -n ∑ i =1 σ 2 i ≥ 1 -nξ 2 = 1 + O ( ξ 2 ) , (77)  \nwe recover the same thing.  \nExample 14 (MPS for the GHZ state) . The standard MPS representation of the GreenbergerHorne-Zeilinger (GHZ) state is given as  \n| GHZ 〉 = 1 √ 2 Tr ( | 0 〉 0 0 | 1 〉 ) n = 1 √ 2 ( | 00 . . . 0 〉 + | 11 . . . 1 〉 ) . (78)  \nAlternatively, we may use a quantum circuit made of CNOT gates to construct the GHZ state, and then use the rewrite rules employed in Examples 4 and 8 to recover the familiar MPS comb-like structure consisting of COPY tensors:  \n<!-- image -->  \nDiagrammatically, any tensor network formed from connected COPY -tensors reduces to a single dot with the appropriate number of input and output legs. Hence one might write the n-party GHZ-state as  \n| GHZ 〉 = 1 √ 2 ∑ ijk...l COPY ijk...l | ijk . . . l 〉 . (80)  \nExample 15 (MPS for the W state) . Like the GHZ state from Example 14, the n -qubit Wstate ( n ≥ 3) has the following MPS representation:  \n| W 〉 = 1 √ n ( | 1 〉 | 0 〉 ) ( | 0 〉 0 | 1 〉 | 0 〉 ) n -2 ( | 0 〉 | 1 〉 ) = 1 √ n ( | 10 . . . 0 〉 + | 010 . . . 0 〉 + . . . + | 0 . . . 01 〉 ) . (81)  \nExample 16 (The AKLT model) . The AKLT model [33] (named after the authors Affleck, Kennedy, Lieb and Tasaki) is a theoretically important exactly solvable model of a spin-1 Heisenberg chain with an extra quadratic interaction term:  \nH = ∑ j glyph[vector] S j · glyph[vector] S j +1 + 1 3 ( glyph[vector] S j · glyph[vector] S j +1 ) 2 , (82)  \nwhere glyph[vector] S is a three-vector of the familiar spin-1 operators. The exact ground state of this Hamiltonian has an elegant expression as a matrix product state. Here we will carry on from Examples 1 and 7 which define and use the glyph[epsilon1] tensor-see also Example 8 which provides a quantum circuit realization for the corresponding singlet state. We start with a tensor product of these states,  \n... ... (83)  \nand then project each neighboring qubit pair onto a three-dimensional (spin-1) Hilbert space using the projectors P :  \n<!-- image -->  \nThe open wires on the P 's have three degrees of freedom (spin-1). The projectors are defined as  \nP = | +1 〉〈 11 | + 1 √ 2 | 0 〉 ( 〈 01 | + 〈 10 | ) + | -1 〉〈 00 | . (85)  \nThe kets | +1 〉 , | 0 〉 and | -1 〉 are the standard spin-1 basis states and clearly the bond dimension χ = 2. The AKLT state obtained after projection is rotationally symmetric but has a non-trivial entanglement structure and a host of other interesting properties-see e.g. [4] and the references therein.  \nThe singular values found from the MPS factorization can be used to form a complete polynomial basis to express invariant quantities related to an MPS. This has a close connection to Schmidt rank and other concepts-see Examples 10 and 11.  \nDefinition 17 (R'enyi and von Neumann entropies) . Given a density operator ρ , its R'enyi entropy of order q is defined to be  \nH q ( ρ ) = 1 1 -q log Tr( ρ q ) = 1 1 -q log ∑ i λ q i , (86)  \nwhere λ i are the eigenvalues of ρ . The case q → 0 gives the rank of ρ (here we define 0 0 = 0), and the limit q → 1 recovers the familiar von Neumann entropy  \nH q → 1 ( ρ ) = -Tr( ρ log ρ ) . (87)  \nFor a pure bipartite state | ψ 〉 with subsystems A and B , the entropies of the reduced density operator ρ A = Tr B ( | ψ 〉〈 ψ | ) can be used to quantify bipartite entanglement in the state. In this context they are called entanglement entropies. The eigenvalues of ρ A (and ρ B ) are the squares of the Schmidt coefficients of | ψ 〉 , and H 0 ( ρ A ) is equal to the Schmidt rank of the bipartition-see Example 10.  \nArea laws are quantified in terms of the scaling of entropy across tensor network partitions [34]. Whenever you bipartition a tensor network representing a pure quantum state, the total dimension χ of wires 'cut' by this partition gives an upper bound to the entanglement entropy: H 0 ( ρ A ) ≤ χ and H 1 ( ρ A ) ≤ log χ .", '6. COUNTING BY TENSOR CONTRACTION': "In the tensor network language, counting problems can be expressed by evaluating fully contracted diagrams [1, 28, 35, 36].  \nTo understand counting problems, imagine a phone book. But this phone book has a problem. The names are arranged randomly, without the standard alphabetical order we'd  \nall expect. If you're task is to determine Stephen Clark's phone number, the average number of names you'll need to examine before finding 'Stephen Clark' is exactly half the number in the phone book-assuming the name is unique. This is an example of a search problem. If we tell you the page number and location on the page where Stephen Clark's name appears, you can easily check and see if we're correct or not. Often times in computer science, problems are classified not in terms of how hard they are to solve-which is often unknown-but in terms of how hard it is to check if a given solution is correct or not.  \nCounting problems arise from search problems in the following way. Imagine you want to determine all the entries in this random phone book with the last name 'Jaksch'. This is then the counting version of the above search problem.  \nIn these examples, both problems can be solved efficiently in the number of entries in the phone book. 'Efficiently' in the language of computer science means that the computational memory and runtime required is less than a polynomial in the problem size-in this case, the number of phone book entries.  \nIn the language of computer science, more generally search problems are complete for the complexity class NP . Counting versions of NP -complete problems are #P -complete [37] in the language of computational complexity theory (pronounced sharp-P).  \nConnections between counting problems and tensor networks arose from the very early days of tensor networks. Penrose showed [1] that certain graph coloring problems can be solved by tensor contraction. We're going to outline Penrose's algorithm in Section 6 2. Before doing that, we will describe in Section 6 1 how tensor contractions can count the number of inputs that cause a given Boolean function to output 1.", '1. Counting Boolean Formula Solutions': "A Boolean function (a.k.a. switching function) takes an n -bit string of binary numberse.g. 00110101011-and maps this to a single binary digit (either 0 or 1). Several problems in physics can be mapped to Boolean functions [38]. In what follows, we will often denote this n -bit string as x . We will show how to associate the Boolean function f ( x ) with a non-normalized quantum state, written as a tensor network. We will establish the following (Remark 18) by a few examples.  \nDefinition 18 (The class of Boolean tensors [35, 36]) . Every Boolean function f ( x ) gives rise to a Boolean tensor  \nf = ∑ x | f ( x ) 〉〈 x | , (88)  \nwith binary coefficients in { 0 , 1 } . Moreover, a tensor network representing this state is determined from the classical logic gate network description of f ( x ).  \nAs an example, consider the logical AND operation which takes Boolean input variables x 1 and x 2 and outputs the Boolean product x 1 ∧ x 2 -as a tensor, we write  \nAND := ∑ x 1 ,x 2 | x 1 ∧ x 2 〉〈 x 1 , x 2 | = | 0 〉〈 00 | + | 0 〉〈 01 | + | 0 〉〈 10 | + | 1 〉〈 11 | . (89)  \nWe will use the standard AND gate symbol also for the corresponding tensor:  \n(90)  \nUsing (88) we can map any Boolean tensor f to an (unnormalized) Boolean state | f 〉 by contracting the output with | 1 〉 :  \n| f 〉 = f glyph[latticetop] | 1 〉 = ∑ x 〈 f ( x ) | 1 〉| x 〉 = ∑ x f ( x ) | x 〉 . (91)  \nIn addition to AND we have already seen other examples from this class of states, the GHZ and W states from Examples 14 and 15. The corresponding Boolean functions (for three variables/qubits) are  \nf GHZ ( x ) = x 1 x 2 x 3 +(1 -x 1 )(1 -x 2 )(1 -x 3 ) (92)  \nand  \nf W ( x ) = x 1 x 2 (1 -x 3 ) + x 1 (1 -x 2 ) x 3 +(1 -x 1 ) x 2 x 3 . (93)  \nInserting these functions in Eq. (91), we obtain the corresponding (unnormalized) quantum states:  \n| GHZ 〉 = | 000 〉 + | 111 〉 , (94)  \n| W 〉 = | 001 〉 + | 010 〉 + | 100 〉 . (95)  \nNow, given a Boolean function f ( x ), each input for which the function returns 1 is said to satisfy the function. The number of satisfying inputs is then equal to the size of the support of f ( x ).  \n<!-- image -->  \nWe may count the number of inputs that satisfy f ( x ) by contracting the tensor f with | 1 〉 to obtain the corresponding Boolean state | f 〉 (diagram (b)). The contraction post-selects the tensor network such that its support now consists solely of inputs that satisfy f ( x ).  \nTo explicitly translate this into a counting problem, we compute the squared norm,  \n‖| f 〉‖ 2 = 〈 f | f 〉 = ∑ x , y f ( x ) f ( y ) 〈 x | y 〉 = ∑ x f ( x ) 2 = ∑ x f ( x ) , (97)  \nwhich clearly gives the number of satisfying inputs. In general for Boolean states the square of the two-norm always equals the one-norm since f ( x ) ∈ { 0 , 1 } . In diagram form this is depicted as  \n<!-- image -->  \nwhere | + 〉 := | 0 〉 + | 1 〉 and thus | + 〉 ⊗ | + 〉 ⊗ . . . ⊗| + 〉 = ∑ x | x 〉 . More formally,  \n1  \nTheorem 19 (Counting SAT solutions [35, 36]) . Let f be a SAT instance. Then the standard two-norm length squared of the corresponding Boolean state | f 〉 gives the number of satisfying assignments of the problem instance.  \nSolving the counting problem for general formula is known to be #P -complete [37]. Just to remind you what we talked about in the introduction to this section, computational complexity jargon for the set of the counting problems associated with the decision problemsdecision problems seek to determine if a state is satisfiable at all, whereas counting problems seek to determine the total number of satisfying solutions. Indeed, the condition 〈 f | f 〉 > 0 implies that the SAT instance f has a satisfying assignment. Determining whether this condition holds for general Boolean states is a NP -complete decision problem-as described in the introduction to this section.  \nFormulating these problems as tensor contractions allows the adaptation of tools developed to simulate quantum systems and circuits such that they now apply to an areas traditionally considered in computer science [35, 36]. We adapted these tools and discovered efficient tensor network descriptions of finite Abelian lattice gauge theories [27]. These tools also lead to the discovery of a wide class of efficiently contractable tensor networks, representing counting problems [36].  \nExample 20 (AND from Toffoli) . The Toffoli gate has long been studied in reversible computing, and also in quantum computing. One can view this operation as being formed internally by an AND tensor, two copy tensors (black dots) and one XOR tensor ( ⊕ )-see Examples 3 and 14. One can create the | AND 〉 state in an experiment by preparing the state  \n| + 〉| + 〉| 0 〉 , (99)  \nwhere | + 〉 := | 0 〉 + | 1 〉 , and then applying the Toffoli gate. This is illustrated with the following tensor diagram.  \n<!-- image -->  \nExample 21 (Hadamard from AND) . By considering the contraction formed with the state |-〉 := 1 √ 2 ( | 0 〉 - | 1 〉 ) and the output of the AND tensor, one recovers the Hadamard gate defined in Eq. (21). Note that we've been using | + 〉 without normalization and here we normalize |-〉 .  \n<!-- image -->  \nExample 22 (De Morgan's laws) . A common identity used in Boolean algebra is  \n¬ ( a ∧ b ) = ( ¬ a ) ∨ ( ¬ b ) , (102)  \nwhere negation denoted as ¬ , logical OR as ∨ , and logical AND as ∧ . When expressed as a tensor network,  \n<!-- image -->  \nthis relation has the same structure as the relationship between the COPY and XOR tensors and the Hadamard gate in Eq. (26) Such diagrammatic rewrite rules can be used to formalize a system of graphical reasoning, and reduce calculations through easily employed graphical rewrite identities.  \nThe synthesis problem seeks to determine how to build a logical circuit from basic logic gates (such as AND) that realizes a given Boolean function. Given this logical circuit, we can obtain the corresponding tensor network simply by replacing the gates with their tensor counterparts. Using tensors that represent classical logical gates provides an alternative means to determine tensor networks representing for instance the GHZ and AND states [25], compared to the MPS representations given in Examples 14 and 15.", '2. Counting Graph Colorings': 'Given a 3-regular planar graph 8 , how many possible edge colorings using three colors exist, such that all edges connected to each node have distinct colors? This counting problem can be solved in an interesting (if not computationally efficient) way using the order-3 glyph[epsilon1] tensor, which is defined in terms of components as  \nglyph[epsilon1] 012 = glyph[epsilon1] 120 = glyph[epsilon1] 201 = 1 , glyph[epsilon1] 021 = glyph[epsilon1] 210 = glyph[epsilon1] 102 = -1 , (104)  \notherwise zero. The counting algorithm is stated as  \nTheorem 23 (Planar graph 3-colorings, Penrose 1971 [1]) . The number K of proper 3 -edge-colorings of a planar 3 -regular graph is obtained by replacing each node with an order-3 epsilon tensor, replacing each edge with a wire, and then contracting the resulting tensor network.  \nWe will first consider the simplest case, a graph with just two nodes. In this case we obtain  \n2  \n<!-- image -->  \nThere are indeed 6 distinct edge colorings for this graph, given as  \n<!-- image -->  \nTo understand Theorem 23, note first that the contraction K of the epsilon tensor network is the sum of all possible individual assignments of the index values to the epsilon tensors comprising the network. Each of the three possible index values can be understood as a color choice for the corresponding edge. Whenever the index values for a given epsilon tensor are not all different, the corresponding term in K is zero. Hence only allowed color assignments result in nonzero contributions to K , and for a graph that does not admit a proper 3-edge-coloring we will have K = 0. For instance, for the non-3-colorable Petersen graph we obtain  \n<!-- image -->  \nHowever, for K to actually equal the number of allowed colorings, each nonzero term must have the value 1 (and not -1). This is only guaranteed if the graph is planar, as can  \nbe seen by considering the non-planar graph K 3 , 3 :  \n<!-- image -->  \nThe edges can be colored with three colors-in 12 different ways-yet the contraction vanishes.  \nThe computational complexity of this problem has been studied in [40]. Interesting, by a well known result (Heawood 1897), the 3-colorings as stated above, are one quarter of the ways of coloring the faces of the graph with four colors, so that no two like-colored faces have an edge in common.  \nExample 24 (Physical implementation of glyph[epsilon1] abc in quantum computing) . In quantum computing, typically one works with qubits (two level quantum systems) but implementations using qutrits exist (three level quantum systems, available in e.g. nitrogen vacancy centers in diamond-see for instance [41]). The epsilon tensor glyph[epsilon1] abc could be realized directly as a locally invariant 3-party state using qutrits, and can also be embedded into a qubit system. We leave it to the reader to show that by pairing qubits, glyph[epsilon1] abc can be represented with six qubits, where each leg now represents a qubit pair. (Note that a basis of 3 states can be isometrically embedded in 4-dimensional space in any number of ways.) Show further that the construction can be done such that the two qubit pairs (together representing one leg) are symmetric under exchange. Note the similarities with Eq. (85) in Example 16.', '7. FRONTIERS IN TENSOR NETWORKS': "Tensor network methods represent a vibrant area of active research, with new results and ideas appearing regularly. Here we have covered the elementary aspects of the tensor network language and three applications. The first was the matrix product state representation, the next was tensor contractions to count Boolean formula solutions and the final application focused on tensor contractions to evaluate 3-edge-colorings of 3-regular planar graphs. These three sample applications should provide a good base to move forward into active research.  \nThe most common tensor network structures and algorithms used in quantum mechanics include Matrix Product States (MPS) [42-44] (see Section 5) and the related Density Matrix Renormalization Group (DMRG) [8], Matrix Product Operators (MPO) [45], Tensor  \nTrains [15], Tree Tensor Networks (TTN) [46], the Multiscale Entanglement Renormalization Ansatz (MERA) [5, 47-49], Projected Entangled Pair States (PEPS) [50], Correlator Product States (CPS) [51] and Time-Evolving Block Decimation (TEBD) [52]-see also time-evolution with MERA [53, 54].  \nOur reference list above is admittedly very much incomplete but should provide a solid starting place for further study. Going further, there are several reviews that we encourage readers to consult. These proceed largely towards approaches that map lattice problems to tensor networks as tools to solve models of strongly correlated systems [4-8, 10, 11, 14]see also the viewpoint [9]. There is a growing and active community exploring the use of tensor network algorithms as a means to discover and understand new properties of quantum systems.  \nIn terms of the graphical language, category theory is a branch of mathematics well suited to describe a wide range of networks [18]. Quantum circuits were first given a 'categorical model' in pioneering work by Lafont in 2003 [55] and dagger compact closed categories [56], also called Baez-Dolan † -categories, were first derived to describe both standard quantum theory as well as classes of topological quantum field theories in seminal work published in 1995 [56]. (See [18] for a well written review of categorical quantum mechanics.) For practical purposes, the graphical language turns out to be mathematically equivalent to the categorical formulation.  \nThere has been some recent excitement surrounding MERA [5, 47-49]-which is capable of representing the ground state of certain many-body models at their critical pointsand its connection to quantum gravity research. Several interesting discoveries [57] have recently been made around the so called tensor network incarnation of the AdS/MERA correspondence; networks which realize a discrete anti-de Sitter space have a corresponding MERA network which represents the ground state of a critical system [57, 58]. This has generated significant recent interest and excitement. If this sounds exciting to you, you might want to take a look at [11, 13, 59].", 'ACKNOWLEDGMENTS': "We've had a number of excellent collaborators over the years, who certainly influenced our understanding of the topic. The least we can do is thank them here. In alphabetical order we thank John Baez, Stephen Clark, Sam Denny, Dieter Jaksch, Tomi Johnson, Marco Lanzagorta, Jason Morton, Lea Trenkwalder, Jacob Turner, Chris Wood and Zolt'an Zimbor'as, as well as others we're probably forgetting. J.B. acknowledges AFOSR grant FA9550-16-10300, Models and Protocols for Quantum Distributed Computation, for financial support. Diagrams and cover courtesy of Lusa Zheglova (illustrator).  \n- [4] R. Or'us, 'A practical introduction to tensor networks: Matrix product states and projected entangled pair states,' Annals of Physics 349 , 117-158 (2014), arXiv:1306.2164.\n- [5] G. Vidal, 'Entanglement renormalization: an introduction,' in Understanding Quantum Phase Transitions , edited by Lincoln D. Carr (Taylor & Francis, Boca Raton, 2010).\n- [6] F. Verstraete, V. Murg, and J. I. Cirac, 'Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems,' Advances in Physics 57 , 143-224 (2008), arXiv:0907.2796.\n- [7] J. I. Cirac and F. Verstraete, 'Renormalization and tensor product states in spin chains and lattices,' J. Phys. A Math. Theor. 42 , 504004 (2009), arXiv:0910.1130.\n- [8] U. Schollwock, 'The density-matrix renormalization group in the age of matrix product states,' Annals of Physics 326 , 96-192 (2011), arXiv:1008.3477.\n- [9] S. Sachdev, 'Viewpoint: Tensor networks-a new tool for old problems,' Physics 2 , 90 (2009), arXiv:1006.0675.\n- [10] Ulrich Schollwock, 'The density-matrix renormalization group: a short introduction,' Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 369 , 2643-2661 (2011).\n- [11] R. Or'us, 'Advances on tensor network theory: symmetries, fermions, entanglement, and holography,' European Physical Journal B 87 , 280 (2014), arXiv:1407.6552.\n- [12] J. Eisert, 'Entanglement and tensor network states,' Modeling and Simulation 3 , 520 (2013), arXiv:1308.3318.\n- [13] G. Evenbly and G. Vidal, 'Tensor Network States and Geometry,' Journal of Statistical Physics 145 , 891-918 (2011), arXiv:1106.1082.\n- [14] J. C. Bridgeman and C. T. Chubb, 'Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks,' ArXiv e-prints (2016), arXiv:1603.03039 [quant-ph].\n- [15] Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P. Mandic, 'Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions,' Foundations and Trends in Machine Learning 9 , 249-429 (2016), 1609.00893.\n- [16] Andrzej Cichocki, Anh-Huy Phan, Qibin Zhao, Namgil Lee, Ivan Oseledets, Masashi Sugiyama, and Danilo P. Mandic, 'Tensor networks for dimensionality reduction and largescale optimization: Part 2 applications and future perspectives,' Foundations and Trends in Machine Learning 9 , 431-673 (2017).\n- [17] M. J. Hartmann, J. Prior, S. R. Clark, and M. B. Plenio, 'Density matrix renormalization group in the Heisenberg picture,' Phys. Rev. Lett. 102 , 057202 (2009), arXiv:0808.0666.\n- [18] J. C. Baez and A. Lauda, 'A Prehistory of n-Categorical Physics,' in Deep Beauty (Cambridge University Press, 2011) pp. 13-128, arXiv:0908.2469.\n- [19] Jacob D. Biamonte, Ville Bergholm, and Marco Lanzagorta, 'Tensor network methods for invariant theory,' J. Phys. A: Math. Theor. 46 , 475301 (2013), arXiv:1209.0631.\n- [20] A. Critch and J. Morton, 'Algebraic Geometry of Matrix Product States,' SIGMA 10 , 095 (2014), arXiv:1210.2812 [quant-ph].\n- [21] William K. Wootters, 'Entanglement of formation of an arbitrary state of two qubits,' Phys. Rev. Lett. 80 , 2245-2248 (1998), arXiv:quant-ph/9709029.\n- [22] V. Coffman, J. Kundu, and W. K. Wootters, 'Distributed entanglement,' Phys. Rev. A 61 , 052306 (2000), arXiv:quant-ph/9907047.\n- [23] Julia Kempe, 'Multiparticle entanglement and its applications to cryptography,' Phys. Rev. A 60 , 910-916 (1999), arXiv:quant-ph/9902036.  \n- [24] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter, 'Elementary gates for quantum computation,' Phys. Rev. A 52 , 3457-3467 (1995), arXiv:quant-ph/9503016.\n- [25] J. D. Biamonte, S. R. Clark, and D. Jaksch, 'Categorical tensor network states,' AIP Advances 1 , 042172 (2011).\n- [26] Ville Bergholm and Jacob D. Biamonte, 'Categorical quantum circuits,' J. Phys. A: Math. Theor. 44 , 245304 (2011), arXiv:1010.4840.\n- [27] S. J. Denny, J. D. Biamonte, D. Jaksch, and S. R. Clark, 'Algebraically contractible topological tensor network states,' Journal of Physics A Mathematical General 45 , 015309 (2012), arXiv:1108.0888.\n- [28] Roger Penrose, 'The theory of quantized directions,' in Collected Works , Vol. 1 (October 1953-67) (Oxford University Press, 2010) Chap. 31, pp. 769-800.\n- [29] Christopher J. Wood, Jacob D. Biamonte, and David G. Cory, 'Tensor networks and graphical calculus for open quantum systems,' Quant. Inf. Comp. 15 , 759-811 (2015), arXiv:1111.6950.\n- [30] S. Meznaric and J. Biamonte, 'Tensor networks for entanglement evolution,' in Quantum Information and Computation for Chemistry: Advances in Chemical Physics , Vol. 154, edited by Sabre Kais (John Wiley & Sons, 2014) pp. 561-574, arXiv:1204.3599.\n- [31] M. B. Hastings, 'An area law for one-dimensional quantum systems,' Journal of Statistical Mechanics: Theory and Experiment 8 , 08024 (2007), arXiv:0705.2024.\n- [32] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, 'Matrix product state representations,' Quant. Inf. and Comp. 7 , 401-430 (2007), arXiv:quant-ph/0608197.\n- [33] I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki, 'Rigorous results on valence-bond ground states in antiferromagnets,' Phys. Rev. Lett. 59 , 799-802 (1987).\n- [34] J. Eisert, M. Cramer, and M. B. Plenio, 'Colloquium: Area laws for the entanglement entropy,' Reviews of Modern Physics 82 , 277-306 (2010), arXiv:0808.3773.\n- [35] T. H. Johnson, J. D. Biamonte, S. R. Clark, and D. Jaksch, 'Solving search problems by strongly simulating quantum circuits,' Scientific Reports 3 , 1235 (2013), arXiv:1209.6010.\n- [36] Jacob Biamonte, Jason Morton, and Jacob Turner, 'Tensor network contractions for #SAT,' Journal of Statistical Physics 160 , 1389-1404 (2015), arXiv:1405.7375.\n- [37] Leslie G Valiant, 'The complexity of computing the permanent,' Theoretical computer science 8 , 189-201 (1979).\n- [38] J. D. Whitfield, M. Faccin, and J. D. Biamonte, 'Ground-state spin logic,' EPL (Europhysics Letters) 99 , 57004 (2012), arXiv:1205.1742 [quant-ph].\n- [39] Jacob Biamonte, 'Charged string tensor networks,' Proceedings of the National Academy of Sciences 114 , 2447 (2017).\n- [40] Mingji Xia, Peng Zhang, and Wenbo Zhao, 'Computational complexity of counting problems on 3-regular planar graphs,' Theoretical Computer Science 384 , 111-125 (2007).\n- [41] F. Dolde et al. , 'High-fidelity spin entanglement using optimal control,' Nature Communications 5 , 3371 (2014), arXiv:1309.4430.\n- [42] M. Fannes, B. Nachtergaele, and R. F. Werner, 'Finitely correlated states on quantum spin chains,' Communications in Mathematical Physics 144 , 443-490 (1992).\n- [43] Stellan Ostlund and Stefan Rommer, 'Thermodynamic limit of density matrix renormalization,' Phys. Rev. Lett. 75 , 3537-3540 (1995), arXiv:cond-mat/9503107.\n- [44] Stefan Rommer and Stellan Ostlund, 'Class of ansatz wave functions for one-dimensional spin systems and their relation to the density matrix renormalization group,' Phys. Rev. B 55 , 2164-2181 (1997), arXiv:cond-mat/9606213.  \n- [45] F. Verstraete, J. J. Garc'ıa-Ripoll, and J. I. Cirac, 'Matrix product density operators: Simulation of finite-temperature and dissipative systems,' Phys. Rev. Lett. 93 , 207204 (2004), arXiv:cond-mat/0406426.\n- [46] Y.-Y. Shi, L.-M. Duan, and G. Vidal, 'Classical simulation of quantum many-body systems with a tree tensor network,' Phys. Rev. A 74 , 022320 (2006), arXiv:quant-ph/0511070.\n- [47] G. Vidal, 'Entanglement renormalization,' Phys. Rev. Lett. 99 , 220405 (2007), arXiv:condmat/0512165.\n- [48] V. Giovannetti, S. Montangero, and R. Fazio, 'Quantum Multiscale Entanglement Renormalization Ansatz Channels,' Physical Review Letters 101 , 180503 (2008), arXiv:0804.0520.\n- [49] G. Vidal, 'Class of quantum many-body states that can be efficiently simulated,' Phys. Rev. Lett. 101 , 110501 (2008), arXiv:quant-ph/0610099.\n- [50] F. Verstraete, M. M. Wolf, D. Perez-Garcia, and J. I. Cirac, 'Criticality, the area law, and the computational power of projected entangled pair states,' Physical Review Letters 96 , 220601 (2006), arXiv:quant-ph/0601075.\n- [51] S. Al-Assam, S. R. Clark, C. J. Foot, and D. Jaksch, 'Capturing long range correlations in two-dimensional quantum lattice systems using correlator product states,' Phys. Rev. B 84 , 205108 (2011), arXiv:1107.0936.\n- [52] G. Vidal, 'Efficient classical simulation of slightly entangled quantum computations,' Physical Review Letters 91 , 147902 (2003), arXiv:quant-ph/0301063.\n- [53] M. Rizzi, S. Montangero, and G. Vidal, 'Simulation of time evolution with multiscale entanglement renormalization ansatz,' Phys. Rev. A 77 , 052328 (2008), arXiv:0706.0868.\n- [54] J. Molina-Vilaplana and J. Prior, 'Entanglement, tensor networks and black hole horizons,' General Relativity and Gravitation 46 , 1823 (2014), arXiv:1403.5395.\n- [55] Yves Lafont, 'Towards an algebraic theory of boolean circuits,' Journal of Pure and Applied Algebra 184 , 2003 (2003).\n- [56] John C. Baez and James Dolan, 'Higher-dimensional algebra and topological quantum field theory,' Journal of Mathematical Physics 36 , 6073-6105 (1995).\n- [57] B. Swingle, 'Entanglement renormalization and holography,' Phys. Rev. D 86 , 065007 (2012), arXiv:0905.1317.\n- [58] N. Bao, C. Cao, S. M. Carroll, A. Chatwin-Davies, N. Hunter-Jones, J. Pollack, and G. N. Remmen, 'Consistency conditions for an AdS multiscale entanglement renormalization ansatz correspondence,' Phys. Rev. D 91 , 125036 (2015), arXiv:1504.06632.\n- [59] M. Van Raamsdonk, 'Lectures on gravity and entanglement,' (2016), arXiv:1609.00026 [hepth].", 'Appendix A: Tensors and Tensor Products': "The definition of a tensor starts with the tensor product ⊗ . There are many equivalent ways to define it, but perhaps the simplest one is through basis vectors. Let V and W be finite-dimensional vector spaces over the same field of scalars K . In physics-related applications K is typically either the real numbers R or the complex numbers C . Now V ⊗ W is also a vector space over K . If V and W have the bases { e j } j and { f k } k , respectively, the symbols { e j ⊗ f k } jk form a basis for V ⊗ W . Thus, for finite-dimensional spaces dim( V ⊗ W ) = dim V dim W .  \nThe tensor product of two individual vectors v ∈ V and w ∈ W is denoted as v ⊗ w . For vectors the tensor product is a bilinear map V × W → V ⊗ W , i.e. one that is linear in both input variables. For finite-dimensional spaces one can obtain the standard basis coordinates of the tensor product of two vectors as the Kronecker product of the standard basis coordinates of the individual vectors:  \n( v ⊗ w ) jk = v j w k . (A1)  \nIt is important to notice that due to the bilinearity ⊗ maps many different pairs of vectors ( v, w ) to the same product vector: v ⊗ ( sw ) = ( sv ) ⊗ w = s ( v ⊗ w ), where s ∈ K . For inner product spaces (such as the Hilbert spaces encountered in quantum mechanics) the tensor product space inherits the inner product from its constituent spaces:  \n〈 v 1 ⊗ w 1 , v 2 ⊗ w 2 〉 V ⊗ W = 〈 v 1 , v 2 〉 V 〈 w 1 , w 2 〉 W . (A2)  \nA tensor T is an element of the tensor product of a finite number of vector spaces over a common field of scalars K . The dual space V ∗ of a vector space V is defined as the space of linear maps from V to K . It is not hard to show that V ∗ is a vector space over K on its own. This leads us to define the concept of an order-( p, q ) tensor, an element of the tensor product of p primal spaces and q dual spaces:  \nT ∈ W 1 ⊗ W 2 ⊗ . . . ⊗ W p ⊗ V ∗ 1 ⊗ V ∗ 2 ⊗ . . . ⊗ V ∗ q . (A3)  \nGiven a basis { e ( i ) k } k for each vector space W i and a dual basis { η ( i ) k } k for each dual space V ∗ i , we may expand T in the tensor products of these basis vectors:  \nT = T i 1 ...i p j 1 ...j q e (1) i 1 ⊗ . . . ⊗ e ( p ) i p ⊗ η (1) j 1 ⊗ . . . ⊗ η ( q ) j q . (A4)  \nT i 1 ...i p j 1 ...j q is simply an array of scalars containing the basis expansion coefficients. Here we have introduced the Einstein summation convention , in which any index that is repeated exactly twice in a term, once up, once down, is summed over. This allows us to save a considerable number of sum signs, without compromising on the readability of the formulas. Traditionally basis vectors carry a lower (covariant) index and dual basis vectors an upper (contravariant) index.  \nA tensor is said to be simple if it can be written as the tensor product of some elements of the underlying vector spaces: T = v (1) ⊗ . . . ⊗ v ( q ) ⊗ ϕ (1) ⊗ . . . ⊗ ϕ ( p ) . This is not true for most tensors; indeed, in addition to the bilinearity, this is one of the properties that separates tensors from mere Cartesian products of vectors. However, any tensor can be written as a linear combination of simple tensors, e.g. as in Eq. (A4).  \nFor every vector space W there is a unique bilinear map W ⊗ W ∗ → K , w ⊗ φ ↦→ φ ( w ) called a natural pairing, where the dual vector maps the primal vector to a scalar. One can apply this map to any pair of matching primal and dual spaces in a tensor. It is called a contraction of the corresponding upper and lower indices. For example, if we happen to have W 1 = V 1 we may contract the corresponding indices on T :  \nC 1 , 1 ( T ) = T i 1 ...i p j 1 ...j q η (1) j 1 ( e (1) i 1 ) e (2) i 2 ⊗ . . . ⊗ e ( p ) i p ⊗ η (2) j 2 ⊗ . . . ⊗ η ( q ) j q = T k i 2 ...i p k i 2 ...j q e (2) i 2 ⊗ . . . ⊗ e ( p ) i p ⊗ η (2) j 2 ⊗ . . . ⊗ η ( q ) j q , (A5)  \nsince the defining property of a dual basis is η (1) j 1 ( e (1) i 1 ) = δ j 1 i 1 . Hence the contraction eliminates the affected indices ( k is summed over), lowering the tensor order by (1 , 1).  \nWe can see that an order-(1 , 0) tensor is simply a vector, an order-(0 , 1) tensor is a dual vector, and can define an order-(0 , 0) tensor to correspond to a plain scalar. But what about general, order-( p, q ) tensors? How should they be understood? Using contraction, they can be immediately reinterpreted as multilinear maps from vectors to vectors:  \nT ' : V 1 ⊗ . . . ⊗ V q → W 1 ⊗ . . . ⊗ W p , T ' ( v (1) ⊗ . . . ⊗ v ( q ) ) = T i 1 ...i p j 1 ...j q e (1) i 1 ⊗ . . . ⊗ e ( p ) i p × η (1) j 1 ( v (1) ) × . . . × η ( q ) j q ( v ( q ) ) , (A6)  \nwhere we tensor-multiply T and the vectors to be mapped together, and then contract the corresponding indices. However, this is not the only possible interpretation. We could just as easily see them as mapping dual vectors to dual vectors:  \nT '' : W ∗ 1 ⊗ . . . ⊗ W ∗ p → V ∗ 1 ⊗ . . . ⊗ V ∗ q , T '' ( ϕ (1) ⊗ . . . ⊗ ϕ ( p ) ) = T i 1 ...i p j 1 ...j q ϕ (1) ( e (1) i 1 ) × . . . × ϕ ( p ) ( e ( p ) i p ) × η (1) j 1 ⊗ . . . ⊗ η ( q ) j q . (A7)  \nEssentially we may move any of the vector spaces to the other side of the arrow by taking their dual:  \nW ⊗ V ∗ ∼ = K → W ⊗ V ∗ ∼ = V → W ∼ = V ⊗ W ∗ → K ∼ = W ∗ → V ∗ , (A8)  \nwhere all the arrows denote linear maps. Any and all input vectors are mapped to scalars by the corresponding dual basis vectors in expansion (A4), whereas all input dual vectors map the corresponding primal basis vectors to scalars.  \nIf we expand the input vectors v ( k ) in Eq. (A6) using the same bases as when expanding the tensor T, we obtain the following equation for the expansion coefficients:  \nT ' ( v (1) ⊗ . . . ⊗ v ( q ) ) i 1 ...i p = T i 1 ...i p j 1 ...j q v (1) j 1 · · · v ( q ) j q . (A9)  \nThis is much less cumbersome than Eq. (A6), and contains the same information. This leads us to adopt the abstract index notation for tensors, in which the indices no longer denote the components of the tensor in a particular basis, but instead signify the tensor's order. Tensor products are denoted by simply placing the tensor symbols next to each other. Within each term, any repeated index symbol must appear once up and once down, and denotes contraction over those indices. Hence, x a denotes a vector (with one contravariant index), ω a a dual vector (with one covariant index), and T ab c an order-(2 , 1) tensor with  \ntwo contravariant and one covariant indices. S ab cde x c y d P e a denotes the contraction of an order-(2 , 3) tensor S , an order-(1 , 1) tensor P , and two vectors, x and y , resulting in an order-(1 , 0) tensor with one uncontracted index, b .  \nIn many applications, for example in differential geometry, the vector spaces associated with a tensor are often copies of the same vector space V or its dual V ∗ , which means that any pair of upper and lower indices can be contracted, and leads to the tensor components transforming in a very specific way under basis changes. This specific type of a tensor is called an order-( p, q ) tensor on the vector space V . However, here we adopt a more general definition, allowing { V k } k and { W k } k to be all different vector spaces."}