# Full text of "Multi-party entanglement in graph states"

## See other formats

Multi-party entanglement in graph states M. Hein 1 ' 2 , J. Eisert 3 ' 4 , and H.J. Briegel 1 - 2 ' 5 1 Theoretische Physik, Ludwig-MaximUians-Universitiit, Theresienstrafie 37, D-80333 Miinchen, Germany 2 lnstitut fur Theoretische Physik, Universitat Innsbruck, Technikerstrafie 25, A-6020 Innsbruck, Austria 3 lnstitut ftir Physik, Universitat Potsdam, Am Neuen Palais 10, D-14469 Potsdam, Germany 4 Blackett Laboratory, Imperial College London, Prince Consort Road, London SW7 2BW, UK and 5 Institute for Quantum Optics and Quantum Information of the Austrian Academy of Sciences, A-6020 Innsbruck, Austria (Dated: February 1, 2008) Graph states are multi-particle entangled states that correspond to mathematical graphs, where the vertices of the graph take the role of quantum spin systems and edges represent Ising interactions. They are many-body spin states of distributed quantum systems that play a significant role in quantum error correction, multi-party quan- tum communication, and quantum computation within the framework of the one-way quantum computer. We characterize and quantify the genuine multi-particle entanglement of such graph states in terms of the Schmidt measure, to which we provide upper and lower bounds in graph theoretical terms. Several examples and classes of graphs will be discussed, where these bounds coincide. These examples include trees, cluster states of dif- ferent dimensions, graphs that occur in quantum error correction, such as the concatenated [7,1,3]-CSS code, and a graph associated with the quantum Fourier transform in the one-way computer. We also present general transformation rules for graphs when local Pauli measurements are applied, and give criteria for the equivalence of two graphs up to local unitary transformations, employing the stabilizer formalism. For graphs of up to seven vertices we provide complete characterization modulo local unitary transformations and graph isomorphisms. PACS numbers: 03.67.-a, 42.50.-p, 03.65.Ud I. INTRODUCTION In multipartite quantum systems one can in many cases identify constituents that directly interact with each other, whereas other interactions play a minor role and can largely be neglected. For example, next-neighbor interactions in cou- pled systems are often by far dominant. Such quantum sys- tems may be represented by a graph 0101, where the vertices correspond to the physical systems, and the edges represent interactions. The concept of a graph state - which abstracts from the actual realization in a physical system - is based on this intuition. A graph state, as it is used in this paper, is a special pure multi-party quantum state of a distributed quantum system. It corresponds to a graph in that each edge represents an Ising interaction between pairs of quantum spin systems or qubits Sill 13. Special instances of graph states are codewords of various quantum error correcting codes | 7], which are of cen- tral importance when protecting quantum states against de- coherence in quantum computation |8|. Other examples are multi-party GHZ states with applications in quantum commu- nication, or cluster states of arbitrary dimensions, which are known to serve as a universal resource for quantum computa- tion in the one-way quantum computer I9l ll0ll . Yet, not only the cluster state itself is a graph state. But also the pure state that is obtained from this universal resource after the appropri- ate steps have been taken to implement operations taken from the Clifford group. This resource is then no longer universal, but the specific resource for a particular quantum computation a. In this paper we address the issue of quantifying and char- acterizing the entanglement of these multi-particle entangled states of arbitrary number of constituents. The aim is to ap- ply the quantitative theory of multi-particle entanglement to the study of correlations in graph states. The underlying mea- sure of entanglement is taken to be the Schmidt measure ITU , which is a proper multi-particle entanglement monotone that is tailored to the characterization of such states. As holds true for any known measure of multi-particle entanglement, its computation is exceedingly difficult for general states, yet for graph states this task becomes feasible to a very high ex- tent. We start by presenting general transformation rules of graphs when local Pauli measurements are applied locally on physical systems represented by vertices. We present various upper and lower bounds for the Schmidt measure in graph the- oretical terms, which largely draw from the stabilizer theory. These bounds allow for an evaluation of the Schmidt measure for a large number of graphs of practical importance. We dis- cuss these rules for the class of 2-colorable graphs, which is of special practical importance in the context of entanglement purification £§]. For this class we give bounds to the Schmidt measure, that are particularly easy to compute. Moreover, we provide criteria for the equivalence of graph states under local unitary transformations entirely on the level of the underlying graphs. Finally, we present several examples, including trees, cluster states, states that occur in the context of quantum error correction, such as the CSS code, and the graph that is used to realize the Quantum Fourier Transformation (QFT) on three qubits in the one-way quantum computer. The vision behind this is to flesh out the notion of entanglement as an algorithmic resource, as it has been put forward in Ref. 0. The paper is structured as follows. We start by introduc- ing the notion of graph states of multi-qubit systems: we set the notation concerning graph theoretical terms, and proceed by showing how graph states are in correspondence to graphs. Then, we recapitulate relevant properties of the Schmidt mea- sure as a measure of multi-particle entanglement. In Sec.lIIII we then state general upper and lower bounds that are formu- lated in the language of graph theory. We also investigate the 2 equivalence class for connected graphs up to seven vertices under local unitaries and graph isomorphisms. These state- ments are the main results of the paper. They are proved in Sec. IIVI We proceed by discussing the above mentioned ex- amples, where we use the developed methods. Finally, we summarize what has been achieved, and sketch further inter- esting steps of future research. This paper is concerned with entanglement in multi -particle distributed quantu m sy stems, with some resemblance to Refs. OHQtHEIljEQjl- However, here we are less in- terested in the connection between quantum correlations and quantum phase transition, but rather in the entanglement of graph states that have definite applications in quantum infor- mation theory. Entangled states associated with graphs have also been studied in Refs. fisl I20L EH where bounds on shared bipartite entanglement in multipartite quantum systems have been studied, in order to find general rules for sharing of entanglement in a multipartite setting. It should, however, be noted that the way in which we represent entangled states by mathematical grap hs is entirely different from the way this is done in Refs. 118, Furthermore, in the present paper, we are not only concerned with bipartite entanglement between two constituents or two groups of constituents, but with multi-particle entanglement between many constituents. In turn, the interaction that gives rise to the entangled graph states is more specific, namely the one corresponding to an Ising interaction. Finally, as discussed above, graph states provide an interesting class of genuine multipartite entangled states that are relatively easy to survey even in the regime of many parties. Since the graph essentially encodes a prepara- tion procedure of the state, we will mainly examine the ques- tion of how the entanglement in a graph state is related to the topology of its underlying graph. II. GRAPHS, GRAPH STATES, AND THE SCHMIDT MEASURE A. Graphs At the basis of our analysis lies the concept of a graph (Jj, A graph is a collection of vertices and a description of which vertices are connected by an edge. Each graph can be rep- resented by a diagram in a plane, where each vertex is rep- resented by a point and each edge by an arc joining two not necessarily distinct vertices. In this pictorial representation many concepts related to graphs can be visualized in a trans- parent manner. In the context of the present paper, physical systems will take the role of vertices, whereas edges represent an interaction. Formally, an (undirected, finite) graph is a pair G=(V,E) (1) of a finite set V C N and a set E C [V] 2 , the elements of which are subsets of V with two elements each (]]]. The el- ements of V are called vertices, the elements of E edges. In the following we will only consider simple graphs, which are graphs, that contain neither loops (edges connecting vertices with itself) nor multiple edges. When the vertices a,b G V are the endpoints of an edge, they are referred to as being adjacent. The adjacency relation gives rise to an adjacency matrix Tq associated with a graph. If V = {ai, aw}, then Tg is a symmetric N x iV-matrix, with elements (r G )y = 1, if {en, a,j} g E, otherwise. (2) We will make repeated use of the neighborhood of a given vertex a £ V. This neighborhood N a C V is defined as the set of vertices b for which {a, b} G E. In other words, the neighborhood is the set of vertices adjacent to a given vertex. A vertex a G V with an empty neighborhood will be called isolated vertex. For the purpose of later use, we will also introduce the con- cept of a connected graph. An {a, 6}-path is an ordered list of vertices a = 01, 0,2, . . . , a n -i, a n = b, such that for all i, ai and a.i + i are adjacent. A connected graph is a graph that has an {a, 6}-path for any two a, b G V. Otherwise it is referred to as disconnected. When a vertex a is deleted in a graph, together with the edges incident with a, one obtains a new graph. For a subset of vertices V c V of a graph G = (V, E) let us denote with G — V the graph that is obtained from G by deleting the set V' of vertices and all edges which are incident with an element of V'. In a mild abuse of notation, we will also write G — E' for the graph that results from a deletion of all edges e G E', where E' C E C [V] 2 is a set of edges. For a set of edges F C [V] 2 we will write G + F = ( V, E U F) , and GAF = (V, EAF), where EAF = (E U F) - (E n F) (3) is the symmetric difference of E and F. Note that the sym- metric difference corresponds to the addition modulo 2 or the componentwise XOR if the sets are considered as binary vec- tors. Moreover, with E(A,B) = {{a,b} G E : a G A,b G B, a ^ b} (4) we denote the set of edges between sets A, B C V of vertices. B. Graph states With each graph G = (V, E) we associate a graph state. A graph state is a certain pure quantum state on a Hilbert space Hv = (C 2 )® 17 . Hence, each vertex labels a two-level quan- tum system or qubit - a notion that can be extended to quan- tum systems of finite dimension d |@] ■ To every vertex a G V of the graph G = (V, E) is attached a Hermitian operator K, («) >) n b€N a Jb) In terms of the adjacency matrix this can be expressed as K, (a) ' n ( a bev (5) (6) 3 As usual, the matrices , , af^ are the Pauli matrices, where the upper index specifies the Hilbert space on which the operator acts. Kq is an observable of the qubits associated with the vertex a and all of its neighbors b G N a . The N = | V\ operators {K^} a e y are independent and they commute. Using standard terminology of quantum mechanics, they define a complete set of commuting observables of the system of qubits associated with the vertex set V. Thus, they have a common set of eigenvectors, the graph states which form a basis of the Hilbert space TLy- For our present pur- poses, it is sufficient to choose one of these eigenvectors as a representative of all graph states associated with G. We de- note by \G) the common eigenvector of the Kq associated with all eigenvalues equal to unity, i.e., K^\G) = \G) (7) for all a G V. Note that any other common eigenvector of the set K { q ] with some eigenvalues being negative are obtained from \G) by simply applying appropriate a z transformations at those vertices a, for which Kq gives a negative eigen- value. In the context of quantum information theory, the finite Abelian group u4 a) w> (8) enerated by the set {K^jaev is a ls° called the stabilizer of the graph state vector \ G). If the number of independent operators in Sg is less than |V|, then the common eigenspaces are degenerate and can, for certain graphs G, be used as quan- tum error correcting codes, the so-called graph codes Q. In this case G also describes a certain encoding procedure. The graph state \G) can also be obtained by applying a se- quence of commuting unitary two-qubit operations [/( a ' b ) to the state corresponding to the empty graph: \G) = U {a ' b} (a.b)eE (9) where E denotes the set of edges in G. The unitary two-qubit operation on the vertices a, b, which adds or removes the edge {a, b}, is given by Tj(a,b) = p(«| g, l( 6) + p(o) g a (b) = jj{a,b^ (1Q) and is simply a controlled a z on qubits a and b, i.e. Tj(a,b) 10 10 10 -1 Here, P (a) 1±<7 (a) (ID denotes the projector onto the eigenvector \z, ±) of with eigenvalue ±1 (similarly for and cry ). J7( a - b ) as in Eq. JlOi is the unitary two-qubit operation which removes or adds the edges. This is easily seen by noting that for c G V — {a, b}, Kq commutes with JJ^ a,b \ whereas Tj(a.b) JpW a?) id a) , z,+ a z ,(o) (12) because of cr K P Z:± = P z , T a x . Since [/( a ' b ) = C/( fa ' a \ simi- larly u(a , b)K (b) u(a , b) i = a (a) R G (13) holds, so that the transformed stabilizer corresponds to a graph G', where the edge {a, 6} is added modulo 2. Up to the local cr 2 -rotations, this corresponds to the Ising interaction. An equivalence relation for graphs is inherited by the corre- sponding equivalence of state vectors. We will call two graphs G = (V, E) and G' = (V, E') LU -equivalent, if there exists a local unitary U such that |G) = U\G'). (14) Locality here refers to the systems associated with vertices of G = (V,E) and G' = (V,E'). Note that LU-equivalence is different from equivalence of graphs in the graph theoretical sense, i.e., permutations of the vertices that map neighbored vertices onto neighbored vertices. C. Schmidt measure Graph states are entangled quantum states that exhibit com- plex structures of genuine multi-particle entanglement. It is the purpose of the present paper to characterize and quan- tify the entanglement present in these states that can be rep- resented as graphs. Needless to say, despite considerable research effort there is no known computable entanglement measure that grasps all aspects of multi-particle entanglement in an appropriate manner, if there is any way to fill such a phrase with meaning. Several entanglement measures for multi-particle systems have yet been suggested and their prop- erties studied ei mum mm. We will for the purposes of the present paper use a measure of entanglement that is tailored for characterizing the degree of entanglement present in graph states: this is the Schmidt measure as introduced in Ref . Illlll . Any state vector \ip) G Tt^ ® ... of a composite quantum system with N components can be represented as IV>> = X>Nv x> > *» — ® |^ (15) 7 = 1 where & G C for i = 1, ...,R, and G U {n) for n = 1, TV. The Schmidt measure associated with a state vector |^) is then defined as £ s (|V»=log 2 (r), (16) 4 where r is the minimal number R of terms in the sum of Eq. d!5t over all linear decompositions into product states. It can be extended to the entire state space (and not only the extreme points) via a convex roof extension. This paper will merely be concerned with pure states. More specifically, we will evaluate the Schmidt measure for graph states only. It should be noted, however that the Schmidt measure is a general entanglement monotone with respect to general local operations and classical communication (LOCC), which typi- cally leave the set of graph states. In the multipartite case it is useful to compare the Schmidt measure according to different partitionings, where the com- ponents 1, JV are grouped into disjoint sets. Any sequence (Ai, An) of disjoint subsets A4 C V with [L=i ^ = {1, N} will be called a partition of V. We will write (Ai,...A N ) < (B\, B M ), (17) if (A\, ...An) is a finer partition than (Bi, ...,Bm). which means that every Ai is contained in some Bj. The latter is then a coarser partition than the former. Among the properties that are important for the rest of the paper are the following: (i) Es vanishes on product states, i.e., Es(\ip)) = is equivalent to IV) = <8 -® IV W )- (18) (ii) Es is non-increasing under stochastic local operations with classical communication (SLOCC) Jill l28ll . Let L,( N > be operators acting on the Hilbert spaces WW satisfying (iW)tL« < 1, and set L = L« ® ... ® LW, then E s ( WL ™ )1/a ) < £ S (|V>)). This can be abbreviated as the statement that if IV) — >SLOCC W) (19) then^sd^')) < E s (\ip)). Similarly IV) — lu IV) (20) implies that Esi\ip')) = Es(\ip)) holds, where < — >lu denotes the interconversion via local unitaries. More- over, for any sequence of local projective measurements that finally completely disentangles the state vector \tp) in each of the measurement results, we obtain the upper bound E s (\1>)) < log 2 (m), (21) where m is the number of measurement results with non-zero probability. (iii) Es is non-increasing under a coarse graining of the partitioning. If two components are merged in order to form a new component, then the Schmidt measure can only decrease. If the Schmidt measure of a state vector |V) is evaluated with respect to a partitioning (A±, ...,An), it will be appended, e (M,...,An) { ^ (22) in order to avoid confusion. The non-increasing prop- erty of the Schmidt measure then manifests as E ( s Al '-' AN) (\i>)) > E s Bu - BM \\i))) (23) if {Ax,...,A N ) < (B 1 ,...,B M ). For a graph G = (V, E), the partitioning where (A\, Am) = V will be referred to as finest partitioning. If no upper index is appended to the Schmidt measure, the finest partition- ing will be implicitly assumed. (iv) Es is sub-additive, i.e. for the partitionings (Ai, A N ) and (Bi, ...,B M ) of two different Hilbert spaces, over which |Vi) and | ^2 ) are states, 4 Ai -^ jv ' Bi "- Bm) (ivi) ® iv 2 )) < E { s Ai '-' An) (IV-i)) + Ef"-' BM) (|^ 2 » . (24) Moreover, for any state vector | (j>) that is a product state with respect to the partitioning (B±, ...,Bm), we have that e (a u ...,An,b u ...,b u ) ^ ^ ^ = E (Ai -- An) (|V)) . (25) (v) For any bipartition (A, B), E s (\ip)) = log 2 (rank(tr A [|V)(V|])). (26) Moreover Eg is additive within a given bipartitioning, i.e., if A = Ax U A 2 and B = B\ U B 2 , then 4 A ' B) (iVi)®iv 2 )) = 4 Ai ' Si) (ivi)) + 4 A2 ' S2) (|V 2 ». (27) The Schmidt measure is a measure of entanglement that quantifies genuine multi-particle entanglement. Yet, it is a coarse measure that divides pure states into classes, each of which is associated with the logarithm of a natural number or zero. But more detailed information can be obtained by considering more than one split of the total quantum system. As stated in property (ii) the Schmidt measure is a multi- particle entanglement monotone fiUl . The fact that it is a non-continuous functional on state space is a weakness when considering bipartite entanglement (where it merely reduces to the logarithm of the Schmidt rank for pure states) and in those few-partite cases where other measures are still feasible to some extent. However, for the present purposes it turns out to be just the appropriate tool that is suitable for characteris- ing the multi-particle entanglement of graph states associated with potentially very many vertices. Moreover, it should be noted that for general pure states of multipartite quantum systems the Schmidt measure is - as any other measure of multipartite entanglement - exceedingly dif- ficult to compute. In order to determine the Schmidt measure Eg, one has to show that a given decomposition in Eq. ( II 51 with R is minimal. The minimization problem involved is, as such, not even a convex optimization problem. Since E$ is 5 discrete, the minimization has to be done by ruling out that any decomposition in R — 1 product terms exists. According to a fixed basis {|0) (a) , |l) (a) } for each of the N qubit sys- tems, the decomposition in Eq. Jl 5I > can be written as £ 6 (aW^W+^ll)^))®... ®(af ) |0)W+/3f ) |l)W). (28) Not taking normalization into account, which would increase the number of equations while decreasing the number of pa- rameters, Eq. dl5> can therefore be rewritten as a system of nonlinear equations in the variables £j, , £ (D with i = 1, ...,R and a = 1, N. In this way one would essen- tially arrive at testing whether a system of 2 N polynomials in (2N + 1) x 2 Es complex variables has common null spaces. This illustrates that the determination of the Schmidt measure for a general state can be a very difficult problem of numerical analysis, which scales exponentially in the number of parties N as well as in the degree of entanglement of the state itself (in terms of the Schmidt measure E$). Remember, however, that the graph states themselves rep- resent already a large class of genuine multipartite entangled states that are relatively easy to survey even in the regime of many parties. A numerical analysis 12911 seems still unrealis- tic in this regime, at least until simpler procedures or generic arguments are found. In the following, we will provide lower and upper bounds for the Schmidt measure of graph states in graph theoretic terms, which will coincide in many cases. Be- cause of the complexity of the numerical reformulation given above, we will omit the computation of the exact value for the Schmidt measure in those cases, where lower and upper bounds do not coincide. We will now turn to formulating gen- eral rules that can be applied when evaluating the Schmidt measure on graph states for a given graph. in. GENERAL RULES FOR THE EVALUATION OF THE DEGREE OF ENTANGLEMENT FOR GRAPH STATES In this section we will present general rules that give rise to upper and lower bounds for the Schmidt measure, that render the actual evaluation of the Schmidt measure feasible in most cases. We will also present rules that reflect local changes of the graph. We will first merely state the bounds, the proofs can then be found in Sec. IIVI For clarity, we will state the main results in the form of propositions. In Sec.|V]we will then apply these rules, and calculate the Schmidt measure for a number of graphs. A. Local Pauli measurements It is well known that any unitary operation or projective measurement associated with operators in the Pauli group can be treated within the stabilizer formalism |@], and therefore be efficiently simulated on a classical computer l30ll . Moreover, since any stabilizer code (over a finite field) can be written as a graphical quantum code fl l3lll . any measurement of oper- ators in the Pauli group turns a given graph state into a new one. More precisely, consider a graph state vector \G) which is stabilized by Sq = {{KQ^} a ^v) an d on which a Pauli measurement is performed. The transformed stabilizer S 1 of the new graph state vector U\G') = P\G) (29) after the projective measurement associated with the projector P is up to local unitaries U a stabilizer Sg> according to a new graph G'. Here and in the following, we will consider unit rays corresponding to state vectors only, and for simplicity of notation, we will write \t/j) = for Hilbert space vectors, if \ip) and \ijj') are identical up to a scalar complex factor, disregarding normalization. We obtain S' = US G ,tf = ({UKg ) tf} aeV ). (30) It will be very helpful to specify into which graph G is mapped under such a measurement, without the need of for- mulating the measurement as a projection applied on Hilbert space vectors. This is the content of the following proposition. Let a S V denote the vertex corresponding to the qubit of which the observable Oz , a^ 1 or a^ 1 is measured. Corre- sponding to this measurement we define unitaries u\ a ± : t/j;j = i, u { z a l = n ° { "\ (3D u { y a i = n i 6) ) 1/2 < u it= n H fc) ) 1&) b£N a beN a and, depending furthermore on a vertex bo G N a , beN a - m - {b } u£i = (--r) 1/2 n ^- c*) b£N bo -N a -{a} Proposition 1 (Local Pauli measurements) Let G = (V, E) be a graph, and let \G) be its graph state vector. If a measure- ment of ai a \ o~y a \ or di"' on the qubit associated with vertex a £ V is performed, then the resulting state vector, depending on the outcome ±1, is given by PQ\G) = \i,±)^®uQ\G'), i = x,y,z. (35) The resulting graph is given by qi = [ G~ {a}, forof>, ~ \ GAE(N a ,N a )-{a} 7 fora { y a) , and for o~i by G' = GAE(N bo ,N a )AE(N bo nN a ,N bo nN a ) AE({b },N a -{bo})-{a}, (37) 6 Px,±&z = Py,±°~z = Pz,±O z = <7 z Px,t> CT z P y ,zf, °zPz,±, P*,±(-i°*) 1/2 = Px,±(i°y) 1/2 = Px,±(-i°y) 1/2 = Px,±(i<T,) 1/2 = {-iVzY' 2 Py, T , (ia y ) 1/2 Pz,±, (-w v f' 2 P z ,±, (ia z )^ 2 P y ,±, Py,±(-i^) 1/2 = Py,±(^y) 1/2 = Py,±(- ia v) 1/2 = Py,±{™*) y2 = {-i<j z y 2 p x , ± , (iay)^ 2 Py, ± , I ■ \l/2 D {-lay) Py,±, (i^) 1/2 Px, T , p, I± H«T,) 1/a = P,,±(i(T y )V» = P,, ± (i(T,) 1/a = (-iff.) 1/a P„±, (i<7 y ) 1/2 P,, ± , (-icr H ) 1/2 P,. ± , (^) 1/2 P,±, No. 1 No. 2 No. 3 TABLE I: The relevant commutation relations for Pauli projections and Clifford operators. for any bo £ N a , if a € V is not an isolated vertex. If a is an isolated vertex, then the outcome of the o~ x -measurement is +1, and the state is left unchanged. A similar set of rules has been found independently by Schlingemann |4|]. Note that in case of a measurement of a y , the resulting graph can be produced as well by simply replacing the sub- graph G[iV a ] by its complement G[N a ] c . An induced sub- graph G[A] of a graph G = (V, E) with A C V is the graph that is obtained when deleting all vertices but those contained in A, and the edges incident to the deleted vertices. For a measurement of a x , like the resulting graph G', the local uni- tary U x ± depends on the choice of bo- But the resulting graph states arising from different choices of bo and b' Q will be equiv- alent up to the local unitary Uy \j\ (see Sec. MI El . Note also that the neighborhood of bo in G' is simply that of a in G (ex- cept from bo). For a sequence of local Pauli measurements, the local unitaries have to be taken into account, if the mea- sured qubit is affected by the unitary. For the sake of com- pleteness we therefore summarize the necessary commutation relations in Table H] which denote the transformation of the measurement basis, if a subsequent measurement is applied to a unitarily transformed graph state. Figure ^ shows two subsequent applications of the rather complicated a x -measurement. We will give a simplified ver- sion of this rule in Sec. IIII El Apart from the trivial case of a o x -measurement at an isolated vertex, both measurement re- sults ±1 of a local Pauli measurement are attained with proba- bility 1/2 and yield locally equivalent graph state vectors \G') and \G"). Therefore, we have E S {\G')) < E S (\G)) < E S (\G')) + 1 (38) FIG. 1: Example for a a x -measurement at vertex 1 in graph No. 1, which is followed by a a z -measurement at vertex 2: In graph No. 1 a a x -measurement is performed at the vertex 1. For the application of the rule in Eq. 1371 . vertex 2 was chosen as the special neighbor bo, yielding graph No. 2 up to a local unitary U. (i) (2)U/2 According to Eq. i2l\ . for any measurement sequence of a x , dy or a z that yields an empty graph, the number of local As stated in Table Q the subsequent a z -measurement on the new graph state is therefore essentially another a x -measurement, now at vertex 2 with a single neighbor bo — 5. The final graph is then graph No. 3. measurements in this sequence gives an upper bound on the Schmidt measure of the corresponding graph state. In the fol- lowing we will call the minimal number of local Pauli mea- surements to disentangle a graph state its Pauli persistency (see Ref. H). Since each a z measurement deletes all edges incident to a vertex, any subset V' C V of vertices in a graph G, to which any edge of G is incident, allows for a disentan- gling sequence of local measurements. In graph theory those vertex subsets are called vertex covers. Proposition 2 (Upper bound via persistency) The Schmidt measure of any graph state vector \G) is bounded from above by the Pauli persistency. In particular, the Schmidt measure is less than or equal to the size of the minimal vertex cover of the corresponding graph G. For graphs with many edges a combination of o~ z and a y will give better bounds than restricting to a z measurements only. For example, due to Eq. ( I36> . any complete graph (in which all vertices are adjacent) can be disentangled by just one a y -measurement at any vertex. As we will show, this cor- responds to the fact that these graph states are LU-equivalent to the GHZ-type graph states, in which every vertex is adja- cent to the same central vertex (see Fig. |2j. B. Schmidt measure for bipartite splits For a bipartition (A,B) of the graph G = (V,E) let Gab = (V, Eab) denote the subgraph of G which is induced by the edges Eab = E(A, B) between A and B. Moreover, Tab will denote the \ A\ x | B \ -off-diagonal submatrix of the adjacency matrix Tq according to G, which represents the edges between A and B: (39) 7 and similarly (r!/S fl )= r - (4 °» Proposition 3 (Bi-partitioning) The partial trace with re- spect to any partition A is t^[|G>(G|] = ^| Y, U(z)\G-A)(G-A\U(zy (41) where F2 denotes the integer field {0, 1} with addition and multiplication modulo 2. The local unitaries are defined as uw = n f n ^) a ■ a£A \b£N a / Therefore, the Schmidt measure of a graph state vector \G) with respect to an arbitrary bipartition ( A, B) is given by the rank of the submatrix Tab of the adjacency matrix Tq, E S (\G)) > E^ B \\G)) = log 2 (rank(fr A [|G)<G|])) = rank F2 (r A B) = -rank F2 (r GAB ). (43) From Eq. J4U one may as well compute that the reduced entropy of \G) according to the bipartition (A, B) and the Schmidt rank coincide, if the base-2- logarithm is taken, with respect to 2. This simply expresses the fact that, for a non empty graph, \G) is the "maximally" (A, _B)-entangled state vector with 2 s Schmidt coefficients. If one maximizes over all bipartitionings (A, B) of a graph G = (V, E), then according to Eq. \22>\ one obtains a lower bound for the Schmidt measure with respect to the finest partitioning. No. 1 No. 2 No. 3 No. 4 2 12 12 12 1 4 5 4 5 4 5 FIG. 2: A single a y -measurement at an arbitrary vertex in the complete graph No. 7 suffices to disentangle the corresponding state. Similarly, a single a z -measurement at the central vertex in graphs No. 1-6 or a single a x -measurement at the non-central vertices is a disentangling measurement. This is due to the fact that all graphs (No. 1-7) are locally equivalent by local unitaries, which transform the measurement basis correspondingly. Note that the Schmidt rank of a graph state is closely re- lated to error correcting properties of a corresponding graph code. Let A be a partition, according to which |G) has max- imal Schmidt rank. Then, according to Ref. |7J|, choosing a subset X C A, the graph code, which encodes an input on vertices X in output on vertices Y = V — X according to G, detects the error configuration E = A — X, i.e., any errors occurring on only one half of the vertex set E can be cor- rected. In particular, all strongly error correcting graph codes in Ref. Qj must have Schmidt measure V\/2. Proposition 4 (Maximal Schmidt rank) A sufficient crite- rion for a bipartite split (A, B) to have maximal Schmidt rank is that the graph Gab contains no cycles, and that the smaller partition contains at most one leaf with respect to the sub- graph Gab- If Gab is not connected, then it is sufficient that the above criterion holds for every connected component of Gab- A leaf is a vertex of degree 1, i.e., a vertex to which exactly one edge is incident UJ. It is finally important to note that the maximum Schmidt measure with respect to all bipartite 8 partitions is essentially the quantity considered in Ref. l32ll in the context of an efficient simulation of a quantum algorithm on a classical computer. If this quantity has the appropriate asymptotic behaviour in the number n of spin systems used in the computation, then an efficient classical algorithm simulat- ing the quantum dynamics can be constructed. Note finally that, as an immediate corollary of the above considerations, the degree of entanglement depends only on the area of the boundary between distinguished regions of reg- ular cluster states, i.e., graph states where in a regular cubic lattice nearest neighbors are connected by an edge. If one considers periodic boundary conditions, one may distinguish a cuboid forming part A from the rest of the graph B, and ask for the bipartite entanglement. It follows immediately that since the interior regions may be completely disentan- gled, the degree of entanglement is linear in the number of vertices forming the boundary of the two regions. The cor- ners are then counted just as one maximally entangled pair of two-spin systems. C. Deleting edges and vertices For graphs with a large number of vertices or edges, it is useful to identify bounds for the Schmidt measure when local changes to the graph are applied. As an example we give two rules, that bound the changes to the Schmidt measure if an edge or a vertex is deleted or added. Proposition 5 (Edge rule) By deleting or adding edges e = {a, b} between two vertices a,b G V of a graph G the Schmidt measure of the resulting graph G' — G ± {e} can at most decrease or increase by one, i.e., \E s (\G'))-Es(\G))\<l. (44) Proposition 6 (Vertex rule) If a vertex a ( including all its in- cident edges) is deleted, the Schmidt measure of the resulting graph G' = G — {a} cannot increase and will at most de- crease by one, i.e., E S (\G')) < E S (\G)) < E S (\G')) + 1. (45) D. Bounds for 2-colorable graphs Graphs may be colorable. A proper 2-coloring of a graph is a labeling V — ► {1, 2}, such that all adjacent vertices are associated with a different element from {1, 2}, which can be identified with two colors. In graph theory these graphs are also called 'bipartite graphs', since the set of vertices can be partitioned into two disjoint sets, such that no two vertices within the same set are adjacent. It is a well known fact in graph theory that a graph is 2-colorable iff it does not contain any cycles of odd length. As has been shown in Ref. ]5j], for every graph state corre- sponding to a 2-colorable graph, a multi-party entanglement purification procedures exists: Given any 2-colorable graph state vector \G) on \ V\ qubits, by means of LOCC operations a general mixed state p on \V\ particles can be transformed into a mixed state, which is diagonal in a basis of orthogonal states that are LU-equivalent to \G). Given that the initial fi- delity is sufficient, an ensemble of those states then can be pu- rified to \G). Thus 2-colorable graph states provide a reservoir of entangled states between a large number of particles, which can be created and maintained even in the presence of deco- herence/noise. For the class of these graph states the lower and upper bounds to the Schmidt measure can be applied. Proposition 7 (2-colorable graphs) For 2-colorable graphs G = (V, E) the Schmidt measure is bounded from below by half the rank of the adjacency matrix of the graph, i.e., E S {\G))> ^rank W2 (T G ) (46) and from above by the size of the smaller partition of the cor- responding bipartition. In particular, for a 2-colorable graph, E S (\G))<[^\. IfTg is invertible, then equality holds in Eq. \47\ . (47) Note that any graph G, which is not 2-colorable, can be turned into 2-colorable one G' simply by deleting the appropriate vertices on cycles with odd length. Since this corresponds to a z measurements, by Eq. j38l >. £s(|G» < E S (\G')) + M < L |V ~ M| J + A/ < L^J • («) where AI denotes the number of removed vertices. Moreover note that the number of induced cycles with odd length cer- tainly bounds AI from above. We also note that whereas local a x - or a z -measurements in 2-colorable graphs will yield graph states according to 2- colorable graphs, a y -measurements of 2-colorable graphs can lead to graph states which are not even locally equivalent to 2-colorable graphs. It is certainly true that a 2-colorable graph remains 2-colorable after application of the a z -measurement rule Eq. 1361 . since after deletion of a vertex in a 2-colorable graph the graph still does not contain any cycles of odd length. Now let G be a 2-colorable graph with the bipartition A of sinks and B of sources, in which the observable a x is mea- sured at vertex a € A. Then, the set E(N bo DN a , N bo DN a ) in Eq. d37l > is empty and -E^iV^ , N a ) only consists of edges be- tween A and B. Moreover, after adding all edges of the last set (modulo 2) to the edge set of the graph G, the measured vertex a G A, as well as its special neighbor bo G B, are isolated, so that in the last step of adding E({bo}, N a — {bo}) the vertex b simply gets all neighbors N a — {b } C B in G. So after ap- plication of this rule the new graph G" has the 2-coloring with partitions A' = A - {a} U {b } and B' = B - {b a }. A coun- terexample to a corresponding assertion for a y -measurements is provided in Fig. [3] The resulting graph even has no locally equivalent representation as a 2-colorable graph. This is be- cause the corresponding equivalence class No. 8 in Table HJ has no 2-colorable representative. 9 No. 1 No. 2 No. 20 No. 21 No. 22 No. 23 FIG. 4: List of connected graphs with up to six vertices that are not equivalent under LU transformations and graph isomorphisms. E. Equivalence classes of graph states under local unitaries Each graph state vector | G) corresponds uniquely to a graph G. However, two graph states can be LU-equivalent, leading to two different graphs. Needless to say, this equivalence re- lation is different from the graph isomorphisms in graph the- ory. We have examined the graph states of all non-isomorphic (connected) graphs with up to seven vertices ll33ll . More pre- cisely, from the set of all possible graphs with seven vertices FIG. 5: List of connected graphs with seven vertices that are not equivalent under LU transformations and graph isomorphisms. (2W « 2 x 10 6 possibilities), we have considered the sub- set of all connected graphs on up to seven vertices which are non-isomorphic with respect to graph isomorphisms, i.e., per- mutations of the vertices that map neighbored vertices onto neighbored vertices. Of the 995 isomorphism classes of cor- responding graph states, 45 classes have turned out to be not invariant under local unitary operations (with respect to the finest partitioning). Moreover, within each of these classes all graph states are equivalent modulo local unitaries and ad- ditional graph isomorphisms, which corresponds to the ex- change of particles. If we exclude the graph isomorphisms as, e.g., in quantum communication scenarios, the number of inequivalent classes of graph states would even be larger. In Fig. |4]and[5]we give a list of simple representatives of each 10 equivalence class. To test for local equivalence we have only considered local unitaries within the corresponding local Clifford group. But by considering the Schmidt rank with respect to all possible bipartitions, the corresponding lists of Schmidt ranks for each representative turned out to be different even if we allow arbi- trary permutations of the vertices. This shows that the found sets of locally invariant graph states are maximal. No. 1 with local unitaries of the form 1/2 r (a) No. 5 No. 6 No. 7 No. 8 (49) b£N a This rule was independently found by Van den Nest l35il and Glynn 1 36], who showed also that a successive applica- tion of this rule suffices to generate the complete orbit of any graph state under local unitary operations within the Clifford group l37ll . Figure [6] shows an example of how to repeat- edly apply this rule in order to obtain the whole equivalence class of a graph state. Note that the set of graphs in Fig. [6] do not exhaust the entire class associated with graph No. 4 in Fig. |4] . In Fig. we show another set of graphs that is a proper subset of the class No. 4 in Fig. |4] No graph in Fig. [6] is locally equivalent to any graph in the equivalence class represented in Fig. though both belong to the same equivalence class when considering both, local unitary trans- formations and graph isomorphisms, as depicted in Fig.|4] For No. 3 No. 4 1 1 • •- 4 2 4 2 No. 7 No. 8 FIG. 6: An example for an successive application of the LU-rule, which exhibits the whole equivalence class associated with graph No. 1 . The rule is successively applied to that vertex of the predeces- sor, which is written above the arrows of the following diagram: 3 2 3 1 3 No. 1 — > No. 2 — > No. 3 — No. 4 — > No. 5 — No. 6 13 4 1 2 — > No. 7 — * No. 8 No. 9 — • No. 10 — » No. 11 No. 9 1 No. 10 Having this enormous reduction in mind, it is desirable to find simple rules in purely graph theoretic terms, giving at least sufficient conditions for two graph states to be equiv- alent by means of local unitaries. The subsequent rule im- plies such a simplification: The inversion of the subgraph G[N a ] >— > G[N a ] c , induced by the neighborhood N a of any vertex a € V, within a given graph, gives a LU-equivalent graph state. In graph theory this transformation r a : G t— > T a (G), where the edges set E 1 of T a (G) is obtained from the edge set E of G by E' = EAE(N a ,N a ), is known as local complementation 13411 . With this notation the corresponding rule for graph states can be stated as follows: Proposition 8 (LU-equivalence) Let a s V be an arbitrary vertex of two graphs G = {V,E), then |r(G)) = U a (G) \G) FIG. 7: An example of an equivalence class which is a proper subset of class No. 4 in Fig.|4] is an invariant under any partition A the Schmidt rank E. arbitrary local unitaries, which is formulated in purely graph theoretic terms. Considering the list of Schmidt ranks with respect to all partitions, one therefore obtains a set of invari- ants for graphs under local complementations r, which was already considered in graph theory, known as the connectiv- ity function l34ll . For the equivalence classes in Fig. [6] and Fig- El f° r example, the corresponding lists of Schmidt ranks or connectivity functions do not coincide, implying that the corresponding set of graph states are not equivalent neither under local Clifford group operations nor under general local unitaries. We note that the Schmidt rank list does not provide a complete set of invariants that would characterize all equiv- alence classes under local Clifford group operations. For the 11 Petersen graph 13811 shown in Fig.[8]and the isomorphic graph, which is obtained by exchanging the labels at each end of the five "spokes", no local Clifford operation exists (i.e., sequence of local complementations) that transforms one graph into the other, although the Schmidt rank lists for both graphs coin- cide. For a complete set of invariants the polynomial invari- ants in Ref. l39il can be considered. For example the number of elements I a (G) in the stabilizer of the graph state vector \G), that act non-trivially exactly on the vertices in A, cor- responds to homogeneous polynomial invariants of degree 2. Moreover one can show that Ib(G) 2 (w-4 A ' Ae) ) (50) BCA Therefore, the list of invariants Ia{G) with respect to all partitions A essentially contains the same information for graph states as the Schmidt rank list. But, as discussed in Refs. |39j|40|], by considering more invariants corresponding to homogeneous polynomials of different degrees one can (in principle) obtain finite and complete sets of invariants for lo- cal Clifford operations, as well as for arbitrary local unitaries. IV. PROOFS In this section we prove the statements that for clarity of presentation have been summarized in the previous section without proof. Proof of Proposition^} As already mentioned in Sec. lIIIEl with the LU-rule at hand one could derive the graph G' after an x- or y-measurement from the z-measurement rule, which can be directly proven by disentangling the Ising interactions Tj(a,b) m Eq Q Here we will instead take another starting point for the proof, namely a well-known result from stabilizer theory that we will then apply to the specific question at hand. Consider a subspace of <D" which is stabilized by ({9i}iei), 9i e V n , (54) where V n denotes the Pauli group on n qubi ts and / is an index set. It is well known (see, e.g., Ref. that the pro- jected subspace P g .± corresponding to a measurement of an operator g £ V n in the Pauli group (i.e., g is a product of Pauli matrices) with outcome ±1 is stabilized by (i) ({gi}i£i), if g commutes with all stabilizer generators 9i- FIG. 8: The Petersen graph. The depicted labeled graph is not LU- equivalent to the graph which is obtained from it by exchanging the labels at each end of the five "spokes", i.e., the graph isomorphism which permutes the vertices 1, 2, 3, 4, and 5 with 6, 7, 8, 9, and 10, respectively. Finally, the LU-rule can be used to derive the x- and y-measurement rule from the simple z-measurement rule: With commutation relations similar to those in Table II] it is easy to see, that P£l = U bo (G)p(%Ut o (G) and P£l U a (G)P ( z a lW a (G) holds, where b is a neighbor of a. With the notion of local complementation at hand, we can then rewrite the resulting states in Proposition \l\ after the Pauli measurement in the simplified form: P { Z %\G) pli\G) Pi%\G) \z,±)^ ®U ( z %\G-a), (51) \y,±)^®u(%\T a (G)-a), (52) \x, ±) (a) ® U { x %\n ( T „ o Tbo (G) - o)>(53) where the local unitaries u\ a l are defined as for Proposition^ (ii) ({±. 9 } U {g k9j : jel'- {k}} U { 9j \j £ I' c }} for some k £ I' otherwise. I' denotes the non-empty index set of the generators gi that do not commute with g, and I' c = I\I' is the complement of We now turn to the specific case of graph state vectors \G) and measurements of ai^ , a y or aT' at vertex a € V. Then each generator Kq^ is associated with an element a € V, and for a given g, the list I' of generators that do not commute with g is a subset of V. For the measurements considered here, only case (ii) is relevant, as long as ai^ is not measured at an isolated vertex a. In the latter situation, which corresponds to case (i), (a) #-(<*) _ _(a) (55) and Oz is n °t contained in any Kq) for b a. Then the state is left unchanged and with probability 1 the result +1 is obtained. In case (ii), in turn, the possible measurement results ±1 are always obtained each with probability 1/2. Let us start with identifying the resulting state vector and graph after measur- ing ai a \ The index set I' then is given by I' — {a}, and the state vector Pj°2|G) is stabilized by ({±4*)}U{K%> : beV-{a}}). (56) Multiplying ±0^ to the elements Kg for b <E V — {a}, according to the neighbors b £ N a in G, yields b>eN b -{a} 12 which is up to the sign the stabilizer generator according to the vertex b in G — {a}. Since the stabilizer generators Kq corresponding to vertices b outside N a U {a} in G coincide with those in G — {a}, the stabilizer may as well be seen generated by {±<rW} U {±K$l {a} :beN a } U {K§l {a} :beV-{a}- N a } . (58) Hence, we have shown the validity of Eq. d35l > for the case of a positive a z measurement result. In the other case the sign can be corrected for, as the stabilizer can be written as ( U z .- ({-a<»»} U {K%>_ {a} : b e V G . {a} }) ) , (59) which corresponds to the state vector \z t -) la) ®u£>_\G-{a}). (60) (a) Here, it has been used that U z commutes exactly with the generators n b£N< a\ ' anti- (61) In a similar manner, the case of a measurement of ay can be treated. The index set I' is given by /' = N a U {a} and, if k = a is chosen, the new stabilizer is given by where ;{±aW}U0 1 U&}, G 1 = {K^K^ : b G N a }, {K^> : ceV-N a - {a}}. (62) (63) (64) For Qi one computes n b'eN b AN a -{a,b] (&') ±a^ V<% U b) I] ° { A U i%' \ b'£N b AN a -{a,b} J (65) _ ± _(a)rr(a) ^( b hj( a ) f — 31(7 j/ L/ v,±- n -G' U !/,± ) where G' denotes the graph with the edge set E 1 = EoAE{N a , N a ) and the unitaries Uy°± are defined as in Eq. ( I32i . Because the elements in Q2 commute with Uy±, we arrive at the result for measurements of a y a \ Finally, in the case of measurements of Ox, we identify /' as I' = N a . If some 60 € N a is chosen, the new stabilizer is given by ( {±ai a \K^} u & u & u g 3 u g 4 >, (66) where, because of the following argumentation the finer dis- section is chosen, Q x = {K^Kf : beN a nN bo }, (67) £2 = {K^ o) K^ :beN a -N ba - {b }}, (68) £3 = {K^ : beN bo -N a -{a}}, (69) (70) g± = {K^ : ceV-N a - N bo }. Instead of Kq, the generator ± n b£N a r (6) U ( x a) ± ( <4 6 °) TT „W 1 rr( a >l n ^ I ^ a i( 71 ) 6GJV„-{6o} can be chosen, where is defined as above. Instead of Kq°^Kq^ in £1, we choose, for b £ N a and b £ N bo , b'eN b AN a AN bo n b'eW 6 AAr a AN bo u{b } b '£N b AN a AN bo K a ) I ^(o) t where the second equality holds, because 60 ^ N b AN a AN bo and ( = F* cr i b °' ) ) 1 ^ 2 therefore anti-commutes only with o'i'' ''. Moreover, the positive sign of +cri b ' ) is due to b g" iV a — •^bo — {^o}i as we H as 6 ^ N bo — N a — {a}, since in both cases ± the term ai^ of ulf± commutes with o4 . For K { q o) K { q ] of g 2 one computes, for b^ N bo ,b ^ N b AN bo , b£N a -N bo - {b }, U X U X n b'£N b AN bo = ( (Ti^)4 bo) (T^) n ^ ) °- f \ J>' ez AT, A /\r. / = ui% 4 b) n b'GAf b AAf b0 CT (b') I K (»)t .r.± (72) b'£N b AN bo U{b } Instead of Kfc' in g 3 we choose, for 6 iV a , 6 ^ N b AN a , b£N bo -N a - {a}, ±a^K^K^ = ±a^ J] ^ b'eiV 6 AAf a \ b'eN a AN b / u ( sU b) n 4 b,) )u^.o3) \ b>EN b AN a / 13 Moreover, note that Kq ^ in Q± is not changed by U^ a ±., since c e V — (N a U N bo ) . To summarize, the new neighborhoods iV£ are N a - {b } if & = b , N b AN a AN ba U {6 } if beN bo f}N a , N b AN ba U {60} if 6 e N a — N ba - {6 },(74) N b AN a if & G iV bo - N a - {a}, N b if b€V G -N a -N bo . A comparison shows that these neighborhoods correspond ex- actly to the graph G obtained from Eq. d37i . This concludes the proof. rj Proof of Proposition^ This statement follows immediately from Eq. i2li in property (ii) of the Schmidt measure, and the fact that the different measurement results are obtained with probability 1/2. rj Proof of Proposition^ To show Eq. J41i . the partial trace over A can be taken according to the basis of A given by | z ) = ®|*,(-i)">w aeA (75) This corresponds to successive local a z -measurements of all vertices in A, yielding measurement outcomes ±1. Accord- ing to Sec. 1111 Al after measurement of 0% the state of the remaining vertices is the graph state vector \G — {a}) in the case of the outcome +1 , and J] a^\G-{a}), ceN a if the outcome is —1. This can be summarized as (76) (77) \c£N a where z a € {0, 1} denotes the measurement result ±1. Since the following measurements commute with the previous local unitaries, the final state vector according to the result z = {z a )aeA S is n n (^) Za \*)®\G-A) aeA c£N a n n (4 c) ) rcaZa \z)®\G-A) aeA ceV no* )' <e a |r G -BZ> n(^ 6) ) \G-A), (78) beB where the computation with respect to z is done in F^ (i.e., modulo 2) and = S ab . Therefore, we arrive at the resulting state state vector associated with the result z as ( _ 1)W r G _ BZ ) |z) q TJ ^( 6) y e |r ^ Z> |G _ A y (?9) beB Because the possible measurement results are attained with probability 1/2, this proves the validity of Eq. J41> with local unitaries as in Eq. J42I - i.e., (M aeA \beN a n beB Jb) (e"\r A B*) (80) To show the validity of Eq. J43> . note that for any zi, Z2 G ¥2, the state vectors U(?i)\G - A) and U(z 2 )\G - A) are orthogonal if and only if «7(z 1 -z 2 ) = C/(z 2 )tC/(z 1 )^l, (81) since ricev °* anti-commutes with the stabilizer for any graph state and for any ^ V' C V, and therefore takes it into its orthogonal complement. Hence, log 2 (rank(tr A [|G)(G|])) = log 2 (dim span {U(z)\G - A) : z e F^}) , (82) as for every z e F^ exactly those z' £ F^ yield the same U(z') = U{z), for which z' - z e {z e F2 ■■ U(z) = 1} holds. This gives (83) log 2 (rank(tr A [|G}(G|])) \A\ - log 2 |{z e F2 : (e b |r AB z) = F2 V6 e B}\ \A\- dimker F2 (r AB ) = rank Fa (T AB ). (84) FIG. 9: A sufficient condition for a graph to have maximal Schmidt rank. Proof of Proposition^ To see this, assume to the contrary that Gab contains no cycles but that the Schmidt rank is not maximal. Then, denote with A' C A any subset for which the corresponding columns n( a ) in Tab might add to modulo 2, £ aeA' » (85) 14 Obviously, every vertex b G B' = {J aeA ' N a must have an even number of distinct neighbours in A'. For the moment let the single leaf a\ be contained in A' and ax, h, a 2 , b n -i, a„, (86) be a {ai,a„}-path with maximal length that alternately crosses the sets A' and B' (starting in a\ and ending in A' as depicted in Fig. [9}. Because a„ is necessarily a vertex of degree more than 1 in Gab and by construction also in Ga'B', it must have a neighbor b n ^ b n -i in B'. If b n = b t for some i = 1, ...,n — 2, a contradiction is found. Otherwise & n itself must have a neighbor a n +i 7^ a n in A', because &„ has even degree in Ga'B' ■ Now either a n+ i = ai for some i = 1 , . . . , n — 2 or the path fli) &i) Q2: b n _i, a n , b n , a n+ i (87) is a longer path in G a>b' - both yielding to contradictions with the previous assumptions. If the single leaf a\ is not contained in A', or if A contains no leaves, the previous argumentation still holds, because now any a £ A' must have a degree more than one, if one allows ai £ A' to be arbitrary. The sufficient criterion for the con- nected components of Gab then follows from the additivity of Es within the given bipartition (A, B), as formulated in Eq. i27\ , after deleting all edges within G[A] and G[5], which is proper (A, i?)-local unitary operation. m A B FIG. 10: The situation before and after the LOCC simulation for adding or deleting an edge {a\ , 61 }: the graph state vector \G) can be transformed by (A, B)-local operations and classical communication with probability 1 into the state vector |G'), where the edge between the partitions Ai and B\ is added or deleted. This is possible if one allows for an additional maximally entangled state | | between A2 and B2 ■ After the LOCC operation the resource is consumed, i.e., the state of (A2, B2) is a pure product state | | . Proof of Proposition^ Let G = (V U {ai, &i}, -E 1 ) be a graph. The set 1/ is the set of all vertices of the graph G except the two vertices a and b between which an edge is sup- posed to be deleted or added. Let V also denote the sequence of partitions in the finest partitioning of G and A\ = {ai}, B\ = {bi}. G' denotes the resulting graph, which differs from G in the edge {ai,&i}. As has been shown in Refs. ll42ll43ll44ll . the unitary operation corresponding to the Ising interaction, see Eq. il OK can be implemented with LOCC with unit probability. The necessary and sufficient resources are one maximally entangled pair of qubits and one bit of classical communication in each direction (see Fig. II 01 . The vertices <22 and 62 correspond to the qubits that carry the entanglement \ip) resource required to implement the Ising interaction with LOCC. With A2 = {02} and B2 = {^2} we can conclude that E { ^ AuBl) (\G)) + l = E { /' AuBl \\G))+E ( s A2 ' B2 \\^)) > E^' Al ' BuM ' B2 \\G)^\iP)), (88) due to sub-additivity and E^> Al ' BuM ' B2 \\G)®\ip}) > E { ^ A - B \\G)® IV-)), (89) due to the non-increasing property under coarse graining of the partition A = A\ U A 2 and B = B x U B 2 . As the Schmidt measure is an entanglement monotone, LOCC simulation of the Ising interaction yields E^' Al ' Bl \\G))+l > ^ A ' S) (I G ')® I0> (a2) ®k) (h2) ) = E^ AuBl \\G')), (90) where it has been used that local additional systems can al- ways be appended without change in the Schmidt measure. The state vector |(/>)( Q2 ) ® |cj)( b2 ) corresponds to the state vec- tor of the additional system after implementation of the Ising gate. Since the Ising interaction gives rise to both a deletion or the addition of an edge, we have arrived at the above state- ment. Note that the whole argumentation also holds if a\ and b\ are vertices in some coarser partitions A\ and B\ of G. In this case the same simulation with LOCC of the Ising inter- action can be used, but in the estimations now with respect to coarser partitions. rj Proof of Proposition]^ If a vertex s G Vis deleted from a graph G = (V, E), the corresponding graph state vector G— {a}) is according to Proposition^up to local unitaries the graph state that is obtained from a measurement of at the vertex a. According to Eq. dl9l the Schmidt measure cannot increase, and because of Eq. (13 8i it can at most decrease by one. rj Proof of Proposition^ To see this, we can write the adja- cency matrix Tq according to the partitions of sources A and sinks B. Then, for Tq in Eq. d39l r G[ Aj - r G[B] - 0, (9i) 15 and the number of linearly independent columns/rows in Tq is twice that of Hence, a lower bound is 4^ fl >(|G)) = L>nk F2 (r G )J. If r<3 is invertible, then E S (\G)) > L^J (92) (93) holds. On the other hand, each of the partition A and B is a vertex cover of G and Eg ( | G) ) is therefore bound from above by the size of the smaller partition, which must be less than LM/2J. Proof of Proposition^ Let c G V — N a , then For b S iV a , one computes K, (c) G' ■ □ (94) 0? } ) 4 b) (- (a) 1 * ,» n r(*>') = 4 a) n ^ ■ ^ n °p b'eN a b"£N b AN a = K { a) ■ K%) . Therefore, (UK^U^) ceV = (4 c ») c£ y, which had to be shown. (95) (96) □ V. EXAMPLES In this section the findings of the previous two sections will be applied to evaluating the Schmidt measure for a number of important graph states. Upper and lower bounds will be in- vestigated, and in most of the subsequently considered cases, these bounds coincide, hence making the computation of this multi-particle entanglement measure possible. b'eN b -{a} FIG. 11: The graph No. 1 represents a tree. Its bipartitioning (A, B), for which in graph No. 2 the vertices in A are depicted by large boxes B, is neither a minimal vertex cover nor yields maximal partial rank. Instead the set of vertices A, represented by large boxes H in graph No. 3, is a minimal vertex cover with maximal partial rank. Here, the edges within in the set A are drawn by thin lines in order to illustrate the resulting graph Gaa c between A and its complement, as considered in Sec. HIIBl Example 1: The Schmidt measure of a tree is the size of its smallest vertex cover. Proof: A tree is a graph that has no cycles. We claim that a minimal vertex cover A of G can be chosen, such that the graph Gab between A and its complement B = A c fulfils the sufficient criterion in Proposition|4]for maximal Schmidt rank. To see this, let A be a minimal vertex cover. If a connected component C\ of Gab has more than one leaf ainAflCi, then this can be transferred to another (possibly new) com- ponent C2, by simply exchanging the leaves in A with their unique neighbors b in B. One again obtains a vertex cover of the same (hence minimal) size. Note that by this exchange the new complement B' receives no inner edges with respect to G, since each of the exchanged vertex of A only had one neighbor in B. Two distinct leaves and in A cannot be adjacent to the same vertex 6 6 B. Otherwise, taking b instead of both ci2 and as in A would yield a vertex cover with fewer vertices. Moreover, two distinct leaves 02 and 0,3 of A n C\ are neces- sarily transferred to different connected components Ci and C3 of Gab, because otherwise any two elements a! 2 and a' 3 of N a2 n A and iV 03 fl A are connected by an (A, i?)-path, which together with an (A, B)-path between and 03 and the edges {0,2, a' 2 } and {03, a' 3 } would form a cycle of G. Starting with a component C[ apart from one leaf a\, all other leaves ai, a& can be transferred in this way to differ- ent components C' 2l C' k . Let us fix these vertices, including their unique neighbors 61, bk, for the following reduction 16 of the number of leaves in the components C' 2 ,...,C' k in the sense that only vertices which differ from oi, a^, bi, b^, are considered for a subsequent transfer. Since G is free of cycles, similar to the above argument, none of the remain- ing leaves is transferred to a component which was already obtained by previous transfer. In a similar manner, for all re- maining components C the minimal vertex cover can be trans- formed into a new one A', for which CD A' contains only one leaf without affecting components which were already con- sidered in the transfer process. That shows the validity of our claim. r-i 5 678 5678 1 2 3 4 1 2 3 4 FIG. 12: An example for the (4, 5, 3)-cluster state and its resulting graph Gaa" between A and its complement as considered in Sec. HIIBl Here the vertices in A are depicted by small boxes ■ . Figure^2gi ves an example for a tree for which the Schmidt measure does not coincide with the size of the smaller bipar- tition, the upper bound according to Proposition^ Example 2: The Schmidt measure of a ID-, 2D-, and 3D- cluster state is Es{\G))=\^\. (97) Proof: To see this, we only consider the 3D case, since the former can be reduced to this. Moreover note that the 3D- cluster does not contain any (induced) cycles of odd length. Therefore, it is 2-colorable and because of Eq. j47L we only have to provide a bipartite split with Schmidt rank [|1^|/2J. For this we choose a Cartesian numbering for the vertices starting in one corner, i.e., (a;, y, z) with x = 1, X, y = 1,...,Y andz = 1,...,Z. Let us first assume that X is an even integer. Then let A = (J even A x denote the partition consisting of vertices in planes A x with even x, and y and z being unspecified. The graph GaA" consists of Y x Z parallel linear chains, which alternately cross A and A c (see Fig. I12i. Since \A\ — (X/2) x Y x Z, we have to show that for no subset A' C A Eq. ( I85> holds. This easily can be done, inductively showing, that vertices in A x cannot be be contained in A' for all even x = 2 , . . . , X, if Eq. J85i shall be satisfied. For x = 2 this holds, because for every a G A' n A2 there is a unique adjacent leaf b G A' n A±. Moreover, since b is a leaf, n a = 1 can only hold for one a € A', Therefore, E < ^f 2 0. (98) a£A' For even x > 2 note that, because G is a tree, any two a\ , a 2 <E A x have disjoint neighborhoods in i.e., N ai n N a2 n A x - X = 0. (99) In order to fulfill Eq. J85I . any occurrence of a G A 1 PI A x can therefore only be compensated by some a' G A x ^2, which is impossible by the inductive presumption. 17 FIG. 13: An example for the (7, 5, 5)-cluster state and its resulting graph Gaa" between A and its complement as considered in Sec. 1111 Bl Here the vertices in A are depicted by small boxes i. The picture gives a rotated view on the cluster considered in the proof for the case, that X, Y, and Z are odd integers: The front plane, consisting of the vertices 1 until 35, is the y-z-plane Ax in the proof. In the case where X, Y as well as Z are odd integers, the previous construction will yield a graph Gaa c consisting of separate linear chains on .4 U (100) x=l,...,X-l ending in the plane Ax (see Fig. II 31 . In this case we add every second row Ax y , y = 2, Z — 1, to the partition A as well as of the last row Axz every second vertex, giving the 18 i ,> , x . T x Z . .X xY x z , 14 = LyJ x y x z + L^— J = L 2 Jao } The inductive argument from above now still holds for all ver- tices in A, except from the y-z-plane A x and can be continued by a similar argument now considering the rows Ax y instead of planes. Note that the results could as well be obtained by simply applying the sufficient criterion in Proposition|4]to the stated bipartitioning (A, B). However, this inductive proof may be of interest also for other graph classes. rj Example 3: The Schmidt measure of an entangled ring with an even number \V\ of vertices is given by |V|/2. No. 1 No. 2 FIG. 14: Graph No. 1 is an entangled ring on 18 vertices. Graph No. 2 represents the resulting graph between the partitions A, whose vertices are depicted by boxes, and the partition B, whose vertices are depicted by discs. Proof: This is a 2-colorable graph, which gives on the one hand the upper bound of \V\/2 for the Schmidt measure. On the other hand, by choosing the partitions A = {1,2} and B = {3, 4} on the first four vertices, which are increased (for \V\ > 4) alternately by the rest of the vertices, yielding the partitioning with .4 B {1,2,5,7,. {3,4,6,8,. ,2k ,2k- 5,. 6,. ;\V\-1} ;\V\}, (102) (103) one obtains a bipartitioning (A, B), which has maximal Schmidtrank Eg B ^ = \V\/2 according to Proposition|4](see Fig.ua. □ Example 4: All connected graphs up to seven vertices. We have computed the lower and upper bounds to the Schmidt measure, the Pauli persistency, and the maximal par- tial rank, for the non equivalent graphs in Figs. |4] and |5] They are listed in Table ITU where we have also included the rank index. By the rank index, we simply compressed the information contained in the Schmidt rank list with respect to all bipartite splittings, counting how many times a cer- tain rank occurs in splittings with either two or three ver- tices in the smaller partition. For example, the rank index RI 3 = (20, 12,3) of graph number 29 means that the rank 3 occurs 20 times in all possible 3-4-splits, the rank 2 twelve times, and the rank 1 only three times. (Note, that here we No. ]LUclass| \v\ \E\ E S Rh Rh 2 - col 1 1 2 1 1 yes 2 2 3 2 1 yes 3 2 4 3 1 (0,3) yes 4 4 4 3 2 (2,1) yes 5 2 4 4 1 (0,10) yes 6 6 5 4 2 (6,4) yes 7 10 5 4 2 (8,2) yes 8 3 5 5 2 < 3 (10,0) no 9 2 6 5 1 (0,0,10) (0,15) yes 10 6 6 5 2 (0,6,4) (8,7) yes 11 4 6 5 2 (0,9,1) (8,7) yes 12 16 6 5 2 (0,9,1) (11,4) yes 13 10 6 5 3 (4,4,2) (12,3) yes 14 25 6 5 3 (4,5,1) (13,2) yes 15 5 6 6 2 (0,10,0) (12,3) yes 16 5 6 6 3 (4,6,0) (12,3) yes 17 21 6 6 3 (4,6,0) (14,1) yes 18 16 6 6 3 (6,4,0) (15,0) yes 19 2 6 9 3 < 4 (10,0,0) (15,0) no 20 2 7 6 1 (0,0,35) (0,21) yes 21 6 7 6 2 (0,20,15) (10,11) yes 22 6 7 6 2 (0,30,5) (12,9) yes 23 16 7 6 2 (0,30,5) (14,7) yes 24 10 7 6 2 (0,33,2) (15,6) yes 25 10 7 6 3 (12,16,7) (16,5) yes 26 16 7 6 3 (12,20,3) (16,5) yes 27 44 7 6 3 (12,21,2) (17,4) yes 28 44 7 6 3 (16,16,3) (18,3) yes 29 14 7 6 3 (20,12,3) (18,3) yes 30 66 7 6 3 (20,13,2) (19,2) yes 31 10 7 7 2 (0,34,1) (16,5) yes 32 10 7 7 3 (12,22,1) (16,5) no 33 21 7 7 3 (12,22,1) (18,3) no 34 26 7 7 3 (16,18,1) (18,3) yes 35 36 7 7 3 (16,19,0) (19,2) no 36 28 7 7 3 (20,14,1) (18,3) no 37 72 7 7 3 (20,15,0) (19,2) no 38 114 7 7 3 (22,13,0) (20,1) yes 39 56 7 7 3 < 4 (24,10,1) (20,1) no 40 92 7 7 3 < 4 (28,7,0) (21,0) no 41 57 7 8 3 < 4 (26,9,0) (20,1) no 42 33 7 8 3 < 4 (28,7,0) (21,0) no 43 9 7 9 3 (28,7,0) (21,0) yes 44 46 7 9 3 < 4 (32,3,0) (21,0) no 45 9 7 10 3 < 4 (30,5,0) (20,1) no TABLE II: The number of vertices | | and edges \E\, Schmidt mea- sure Es, rank index Rh and Rh (for splits with 2 or 3 vertices in the smaller partition), number of non-isomorphic but LU equivalent graphs |LUclass|, and the 2-colorable property 2 — col for the graph classes in Fig.|4]and|5|. 19 use log 2 of the actual Schmidt rank.) Similarly, because of RI 2 = (18, 3) the rank 2 (1) occurs 18 (3) times in all 2-5- splits of the graph number 29. For connected graphs the Schmidt rank cannot occur for any bipartite splitting (A, B), since this would correspond to an empty graph Gab- Because the rank index is invariant under permutations of the partitions according to graph iso- morphisms it provides information about whether two graph states are equivalent under local unitaries plus graph isomor- phisms as treated in Sec. 1111 El But note that graph number 40, 42 and 44 are examples for non-equivalent graphs with the same rank index. Nevertheless, comparing the list of Schmidt ranks with respect to all bipartitions in detail shows that no permutation of the vertex set exists (especially none which is induced by a proper graph isomorphism on both sides), which would cause a permutation of the corresponding rank list, such that two of the graphs could be locally equivalent. In Table ||l]we have also listed the sizes of the corresponding equiv- alence classes under LU and graph isomorphisms, as well as whether 2-colorable representatives exist. For 295 of 995 non- isomorphic graphs the lower and upper bound differs and that in these cases the Schmidt measure also non-integer values in log 2 {l, ...,2' y l} are possible. As has been discussed in Sec. Ill CI in this paper we omit the computation of the exact value for the Schmidt measure. Moreover note that only graph number 8 and 19 have max- imal partial rank with respect to all bipartite splits. Entan- glement here is distributed symmetrically between all parties, which makes it "difficult" to disentangle the state by few mea- surements. From this one can understand why the gap be- tween the lower and upper bound occurs in such cases. As discussed in Sec. MI Bl of all graph codes with less than seven vertices only these two are candidates for strongly error de- tecting graph codes introduced in Ref. 0. Example 5: Concatenated [7, 1, 3]-CSS-code. The graph G depicted in Figll5lrenresents an encoding pro- cedure for the concatenated [7, 1, 3]-CSS-code. The corre- sponding graph state has Schmidt measure 28. For encoding, the qubit at the vertex o can be in an arbitrary state. With the rest of the vertices (initially prepared in the state corre- sponding to \x, +)), it is then entangled by the 2-qubit unitary jj(a,b)^ introduced in Eq. ( 1101 . Encoding the state at vertex o then means to perform era- -measurements at all vertices of the inner square, yielding the corresponding encoded state on the 7 2 = 49 "outer" vertices. The encoding procedure may alter- natively be realized by teleporting the bare qubit, initially lo- cated on some ancillary particle, into the graph by performing a Bell measurement on the ancilla and the vertex o of the graph state vector \G'). Here \G') denotes the graph state vector ob- tained from \G) by seven a x -measurements at all vertices of the inner square except o. In this sense G' represents the re- source for the alternative encoding procedure. It has maximal Schmidt measure 25, whereas the corresponding and 1 code words have Schmidt measure 24. They can be obtained with probability 1/2 from \G') by a a z -measurement at the vertex FIG. 15: Resource graph state for the concatenated [7, 1,3]-CSS code. Example 6: Quantum Fourier Transform (QFT) on three qubits. The graph No. 1 in Fig.^]is a simple example of an en- tangle d grap h state as it occurs in the one-way computer of Refs. o flOll . This specific example represents the initial re- source (part of a cluster) required for the quantum Fourier transform QFT on 3 qubits |3J. It has Schmidt measure 15, where the partition A = {2, 4, 7, 9, 11, 13, 15, 18, 20, 22, 24, 26, 28, 30, 32} (104) is a minimal vertex cover with maximal Schmidt rank. In the process of performing the QFT, all vertices except the output vertices 5, 16, 33 are measured locally. During this process, the entanglement of the resource state (with respect to ev- ery partitioning) can only decrease. Similar as with the graph state vector \G') obtained from Fig.^J graph No. 2 represents the input-independent resource needed for the essential (non- Clifford) part of the QFT protocol @|. It has Schmidt measure 5, where the partition A = {2, 9, 10, 11, 15} now provides a minimal vertex cover with maximal Schmidt rank. VI. SUMMARY, DISCUSSION, AND OUTLINE OF entanglement that one encounters in graph states. Such graph FURTHER WORK states capture the intuition of an interaction pattern between quantum systems, with important applications in quantum er- In this paper we have developed methods that allow for a qualitative and quantitative description of the multi-particle 20 No. 1 21 22 23 24 25 26 27 28 29 30 31 32 33 17 8 9 18 10 19 11 12 13 20 * * 14 15 16 No. 2 FIG. 16: The graph associated with the QFT on 3 qubits in the one-way quantum computer is represented in graph No. 1, where the boxes denote the input (left) and output (right) vertices. Graph No. 2 is obtained from the first after performing all Pauli measurements according to the protocol in Ref. jj], except from the a x -measurements at the input vertices. More precisely, it is obtained from graph No. 1 after <j y -measurements on the vertices 22, 23, 24, 26, 27, 28, 30, 31, 32 and a x -measurements on the vertices 2, 4, 7, 9, 11, 13, 15, 18, 20 have been performed. ror correction, quantum communication, and quantum com- putation in the context of the one-way quantum computer. The Schmidt measure is tailored for a comparably detailed account on the quantum correlations grasping genuine multi-particle entanglement, yet it turns out to be computable for many graph states. We have presented a number of general rules that can be applied when approaching the problem of evalu- ating the Schmidt measure for general graph states, which are stated mostly in graph theoretical terms. These rules have then been applied to a number of graph states that appear in quan- tum computation and error correction. Also, all connected graphs with up to seven vertices have been discussed in detail. The formalism that we present here abstracts from the actual physical realisation, but as has been pointed out in several in- stances, a number of well-controllable physical systems such as neutral atoms in optical lattices serve as potential candi- dates to realize such graph states EslEtill . In this paper, the Schmidt measure has been employed to quantify the degree of entanglement, as a generalization of the Schmidt rank in the bipartite setting. This measure is sufficiently coarse to be accessible for systems consisting of many constituents and to allow for an appropriate discussion of multi-particle entanglement in graph states. The approach of quantifying entanglement in terms of rates of asymptotic reversible state transformations, as an alternative, appears un- feasible in the many-partite setting. The question of the min- imal reversible entangling generating set (MREGS) in multi- partite systems remains unresolved to date, even for quantum systems consisting of three qubits, and despite considerable research effort 1471 14811 . These MREGS are the (not necessar- 21 ily finite) sets of those pure states from which any other pure states can be asymptotically prepared in a reversible manner under local operations with classical communication (LOCC). Hence, it seems unrealistic to date to expect to be able to char- acterize multi-particle entanglement by the rates that can be achieved in reversible asymptotic state transformations, analo- gous to the entanglement cost and the distillable entanglement under LOCC operations in bipartite systems. In turn, such a description, if it was to be found, could well turn out to be too detailed to capture entanglement as an algorithmic resource in the context of error correction or the one-way quantum com- puter, where, needless to say, distributed quantum systems with very many constituents are encountered. For future investigations, a more feasible characterization of LU equivalence would open up further possibilities. A step that would go significantly beyond the treatment of the present paper would be to consider measurements corresponding to observables not contained in the Pauli-group. Unfortunately, in this case the stabilizer formalism is no longer available, at least not in the way we used it in this paper. Such an ex- tension would, however, allow for a complete monitoring of the entanglement resource as it is processed during a quantum computation in the one-way computer, where also measure- ments in tilted bases play a role. Finally, taking a somewhat different perspective, one could also extend the identification of edges with interactions to weighted graphs, where a real positive number associated with each edge characterizes the interaction strength (e.g., the in- teraction time). With such a notion at hand, one could study the quantum correlations as they emerge in more natural sys- tems. One example is given by a Boltzmann system of parti- cles, where each particle follows a classical trajectory but car- ries a quantum degree of freedom that is affected whenever two particles scatter. With techniques of random graphs, it would be interesting to investigate what kind of multi-particle correlations are being built up when the system starts from a prescribed initial state, or to study the steady state. The answer to these questions depends on the knowledge of the interaction history. A hypothetical observer who is aware of the exact distribution in classical phase space (Laplacian de- mon perspective) would assign a definite graph corresponding to a pure entangled state to the ensemble. An observer who lacks all or part of this classical information about the parti- cles' trajectories would describe the state by a random mixture of graphs and corresponding quantum states. One example of this latter situation would be a Maxwell demon scenario in which one studies the bipartite entanglement as it builds up between two parts of a container. VII. ACKNOWLEDGEMENTS We would like to acknowledge fruitful discussions with D. Schlingemann, M. Van den Nest, P. Aliferis, as well as with H. Aschauer, W. Dur, and R. Raussendorf. For valuable hints on connections to known results in graph theory |[§4| and multi- linear algebra l29ll we would like to thank G. Royle, K. Aude- naert and the referee. This work has been supported by the Deutsche Forschungsgemeinschaft (Schwerpunkt QIV), the Alexander von Humboldt Foundation (Feodor Lynen Grant of JE), the European Commission (IST-2001-38877/-39227, IST-1999-1 1053), and the European Science Foundation. [1] D.B. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, 2001). [2] R. Diestel, Graph Theory (Springer, Heidelberg, 2000). [3] R. Raussendorf, D.E. Browne, and H.J. Briegel, Phys. Rev. A 68, 022312 (2003). [4] D. Schlingemann, Quant. Inf. Comp. 2, 307 (2002); Quant. Inf. Comp. 4, No 4, 287-324 (2004). [5] W. Dur, H. Aschauer, and HJ. Briegel, Phys. Rev. Lett. 91, 107903 (2003). [6] M. Grassl, A. Klappenecker, and M. Rotteler, Graphs, Quadratic Forms, and Quantum Codes, in Proc. 2002 IEEE International Symposium on Information Theory, Lausanne, Switzerland (2002), page 45. [7] D. Schlingemann and R.F. Werner, Phys. Rev. A 65, 012308 (2002). [8] D. Gottesman, Stabilizer Codes and Quantum Error Correc- tion, PhD thesis (CalTech, Pasadena, 1997). [9] H.J. Briegel and R. Raussendorf, Phys. Rev. Lett. 86, 910 (2001). [10] R. Raussendorf and HJ. Briegel, Phys. Rev. Lett. 86, 5188 (2001) . [11] J. Eisert and H.J. Briegel, Phys. Rev. A 64, 022306 (2001). [12] T.J. Osborne and M.A. Nielsen, Phys. Rev. A 66, 032110 (2002) . [13] A. Osterloh, L. Amico, G. Falci, and R. Fazio, Nature 416, 608 (2002). [14] J.I. Latorre, E. Rico, and G. Vidal, Quantum Inf. Comput. 4, 048 (2004). [15] K. Audenaert, J. Eisert, M.B. Plenio, and R.F. Werner, Phys. Rev. A 66, 042327 (2002). [16] M.M. Wolf, F. Verstraete, and J.I. Cirac, Phys. Rev. Lett. 92, 087903 (2004). [17] J.K. Stockton, J.M. Geremia, A.C. Doherty, and H. Mabuchi, Phys. Rev. A 67, 022112 (2003). [18] K.M. O'Connor and W.K. Wootters, Phys. Rev. A 63, 052302 (2001). [19] F. Verstraete, M. Popp, and J.I. Cirac, Phys. Rev. Lett. 92, 027901 (2004). [20] M. Plesch and V. Buzek, Phys. Rev. A 67, 012322 (2003); Phys. Rev. A 68, 012313 (2003). [21] P. Giorda and P. Zanardi, Phys. Rev. A 68, 062108 (2003). [22] M.G Parker and V. Rijmen, The Quantum Entanglement of Binary and Bipolar Sequences, Sequences and Their Ap- plications, SETA'01, Discrete Mathematics and Theoretical Computer Science Series, Springer, 2001, Ed.: THelleseth, P.V.Kumar and K.Yang. [23] V. Coffman, J. Kundu, and W.K. Wootters, Phys. Rev. A 61, 052306 (2000). [24] M.B. Plenio and V. Vedral, J. Phys. A 34, 6997 (2001). [25] D. Meyer and N. Wallach, J. Math. Phys. 43, 4273 (2002). 22 [26] T.-C. Wei and P.M. Goldbart, Phys. Rev. A 68, 042307 (2003). [27] H. Barnum and N. Linden, J. Phys. A 34, 6787 (2001). [28] W. Diir, G. Vidal, and J.I. Cirac, Phys. Rev. A 62, 062314 (2000). [29] For a more detailed discussion of numerical issues we refer to: L. De Lathauwer, Signal Processing based on Multilinear Al- gebra, PhD thesis (Dept. of Electrical Engineering ESAT, K.U. Leuven, 1997), ESAT-SISTA/TR 1997-74, where the problem of finding the minimal linear decomposition of a pure state (rank- TV tensors) into product states (product of rank-1 tensors) is discussed in the context of the 'Canonical Decomposition' or 'Parallel Factors' problem. [30] This is the content of the so-called Gottesman-Knill theorem as it is stated in Ref. |4l|] (Theorem 10.7). [31] D. Schlingemann, Quant. Inf. Comp. 2, 307 (2002). [32] G. Vidal, Phys. Rev. Lett. 91, 147902 (2003). [33] Similar classifications for self-dual additive codes over GF{4) have been provided independently, e.g., for TV < 7 in: G. Hohn, Mathematische Annalen 327, pp. 227-255 (2003), for AT < 9 in: D.G. Glynn, TA. Gulliver, J.G Maks, and M. K. Gupta, The geometry of additive quantum codes, submitted to Springer- Verlag (2004), and for A < 12 in: L. E. Danielsen and M.G. Parker, E-print math.CO/0504522 [34] A. Bouchet, Discrete Math. 114, 75 (1993). [35] M. Van den Nest, J. Dehaene, and B. De Moor, Phys. Rev. A 69, 022316 (2004); Phys. Rev. A 70, 034302 (2004). [36] D.G. Glynn, On self-dual quantum codes and graphs, Submit- ted to Electronic Journal of Combinatorics, Preprint (2002). [37] An alternative proof in terms of isotropic systems has already been provided in l34ll . [38] This counter example is due to: D. Fon-Der-Flaass, Local equivalence of transversals in matroids, Electr. J. Comb. 3(1) (1996). [39] H. Aschauer, J. Calsamiglia, M. Hein and H.J. Briegel, Quant. Inf. Comp. 4, 383 (2004). [40] M. Van den Nest, J. Dehaene, and B. De Moor, Phys. Rev. A 71, 022310 (2005); E-print quant-ph/0410165 E-print quant-ph/0411115 [41] MA. Nielsen and I.L. Chuang, Quantum Computation and In- formation (Cambridge University Press, Cambridge, 2000). [42] D. Gottesman, The Heisenberg Representation of Quantum Computers, in Proceedings of the XXII International Collo- quium on Group Theoretical Methods in Physics, eds. S.P. Cor- ney et al, (Cambridge, MA, International Press, 1999). [43] J. Eisert, K. Jacobs, P. Papadopoulos, and M.B. Plenio, Phys. Rev. A 62, 052317 (2000). [44] D. Collins, N. Linden, and S. Popescu, Phys. Rev. A 64, 032302 (2001). [45] D. Jaksch, H.-J. Briegel, J.I. Cirac, C.W. Gardiner, and P. Zoller, Phys. Rev. Lett. 82, 1975 (1999). [46] L.-M. Duan, E. Dernier, and M.D. Lukin, Phys. Rev. Lett. 91, 090402 (2003). [47] C.H. Bennett, S. Popescu, D. Rohrlich, JA. Smolin, and A.V. Thapliyal, Phys. Rev. A 63, 012307 (2001). [48] N. Linden, S. Popescu, B. Schumacher, and M. Westmoreland, quant-ph/99 12039 E.F. Galvao, M.B. Plenio, and S. Virmani, J. Phys. A 33. 8809 (2000): S. Wu and Y. Zhang. Phys. Rev. A 63, 012308 (2001); A. Acin, G. Vidal, and J.I. Cirac, Quant. Inf. Comp. 3, 55 (2003).