Skip to main content

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).