En anglemen in eigh -qubi g aph s a es
Adán Cabello a,∗, An onio J. López-Ta ida a, Pila Mo eno a, José R. Po illo b
a Depa amen o de Física Aplicada II, Uni e sidad de Se illa, E-41012 Se illa, Spain
b Depa amen o de Ma emá ica Aplicada I, Uni e sidad de Se illa, E-41012 Se illa, Spain
abs ac
Any 8-qubi g aph s a e belongs o one o he 101 equi alence classes unde local uni a y ope a ions wi hin he Cli o d g oup. Fo each o hese classes we
ob ain a ep esen a i e which equi es he minimum numbe o con olled-Z ga es o i s p epa a ion, and calcula e he Schmid measu e o he 8-pa i e spli ,
and he Schmid anks o all bipa i e spli s. This esul s in o an ex ension o 8 qubi s o he classifica ion o g aph s a es p oposed by Hein, Eise , and B iegel
[M. Hein, J. Eise , H.J. B iegel, Phys. Re . A 69 (2004) 062311].
1. In oduc ion
G aph s a es [1,2] a e a ype o n-qubi pu e s a es ha play
se e al undamen al oles in quan um in o ma ion heo y. In quan-
um e o -co ec ion, he s abilize codes which p o ec quan um
sys ems om e o s [3] can be ealized as g aph codes [4,5].In
measu emen -based (o one-way) quan um compu a ion [6],g aph
s a es a e he ini ial esou ces consumed du ing he compu a ion.
Mo eo e , some g aph s a es a e uni e sal esou ces o quan um
compu a ion [7]. In quan um simula ion, g aph s a es allow us o
demons a e ac ional b aiding s a is ics o anyons in an exac ly
sol able spin model [8]. G aph s a es ha e been used in mul i-
pa i e pu ifica ion schemes [9]. The Cli o d g oup has been used
o en anglemen dis illa ion p o ocols [10]. G aph s a es na u ally
lead o G eenbe ge –Ho ne–Zeilinge (GHZ) o all- e sus-no hing
p oo s o Bell’s heo em [11–16], which can be con e ed in o Bell
inequali ies which a e maximally iola ed by g aph s a es [17–22].
Some specific g aph s a es a e essen ial o se e al quan um com-
munica ion p o ocols, including en anglemen -based quan um key
dis ibu ion [23], elepo a ion [24], educ ion o communica ion
complexi y [25], and sec e sha ing [26,27].
In addi ion o all hese applica ions, g aph s a es also play a
undamen al ole in he heo y o en anglemen . Fo n⩾4qubi s,
he e is an infini e amoun o di e en , inequi alen classes o
n-qubi pu e en angled s a es. The g aph s a e o malism is a use-
*Co esponding au ho .
E-mail add ess: [email p o ec ed] (A. Cabello).
ul abs ac ion which pe mi s a de ailed (al hough no exhaus i e)
classifica ion o n-qubi en anglemen o n⩾4qubi s.
Fo all hese easons, a significan expe imen al e o is de-
o ed o he c ea ion and es ing o g aph s a es o an inc easing
numbe o qubi s. On one hand, he e a e expe imen s o n-qubi
n-pho on g aph s a es up o n=6[28–32]. On he o he hand, he
combina ion o wo echniques, hype -en anglemen (i.e., en angle-
men in se e al deg ees o eedom, like pola iza ion and linea
momen um) [33–39] and he sou ces o 4, 5, and 6-pho on en an-
glemen using pa ame ic down-con e sion [29,40–45] allows us
o c ea e 6-qubi 4-pho on g aph s a es [46,47],8-qubi 4-pho on
g aph s a es [46], and e en 10-qubi 5-pho on g aph s a es [46].
The use o 4-pho on sou ces o p epa ing 8-qubi g aph s a es
is pa icula ly sui able due o he high isibili y o he esul ing
s a es.
The classifica ion and s udy o he en anglemen p ope ies o
g aph s a es ha e been achie ed, up o 7 qubi s, by Hein, Eise ,
and B iegel (HEB) in [1] (see also [2]). This classifica ion has been
use ul o iden i y new wo-obse e all- e sus-no hing p oo s [16],
new Bell inequali ies [21,22], and has s imula ed he p epa a ion
o se e al g aph s a es [46].Themainpu poseo hisLe e is o
ex end he classifica ion in [1,2] o 8-qubi g aph s a es.
Up o 7 qubi s, he e a e 45 classes o g aph s a es ha a e no
equi alen unde one-qubi uni a y ans o ma ions. Wi h 8 qubi s,
he e a e 101 new classes. All hese classes ha e been ob ained by
a ious esea che s (see, e.g., [48]). The pu pose he e is o classi y
hem acco ding o se e al ele an physical p ope ies o quan um
in o ma ion heo y.
The Le e is o ganized as ollows. In Sec ion 2we define qubi
g aph s a es and local complemen a ion, which is he main clas-
si ying ool. To es ablish an o de be ween he equi alence classes
we will use he c i e ia p oposed in [1,2]. These c i e ia a e in o-
duced in Sec ion 3. In Sec ion 4we p esen ou esul s. In Sec ion 5
we p esen he conclusions and poin ou some pending p oblems.
2. Basic concep s
2.1. G aph s a e
An-qubi g aph s a e |Gis a pu e s a e associa ed o a g aph
G=(V,E)consis ing o a se Vo n e ices and a se Eo edges
connec ing some o he e ices. Each e ex ep esen s a qubi .
The g aph Gp o ides bo h a ecipe o p epa ing |Gand a ma h-
ema ical cha ac e iza ion o |G.
The ecipe o p epa ing he s a e is he ollowing. Fi s , p e-
pa e each qubi in he s a e |+ = (|0+|1)/√2. Then, o each
edge connec ing wo qubi s, iand j, apply he con olled-Zga e
be ween qubi s iand j, i.e., he uni a y ans o ma ion CZ=
|0000|+|0101|+|1010|−|1111|.
The ma hema ical cha ac e iza ion o |Gis he ollowing. The
g aph s a e |Gassocia ed o he g aph Gis he only n-qubi s a e
which ulfills
gi|G=|G, o i=1,...,n,(1)
whe e gia e he gene a o s o he s abilize g oup o he s a e,
defined as he se {sj}2n
j=1o all p oduc s o he gene a o s. Speci -
ically, giis he gene a o ope a o associa ed o he e ex i,de-
fined by
gi:= X(i)
j∈N(i)
Z(j),(2)
whe e N(i)is he neighbo hood o he e ex i, i.e., hose e ices
which a e connec ed o i, and X(i)(Z(i)) deno es he Pauli ma ix
σx(σz)ac ingon hei h qubi .
2.2. Local complemen a ion
Fo ou pu poses, he key poin is ha local complemen a ion
(LC) is a simple ans o ma ion which lea es he en anglemen
p ope ies in a ian .
Two n-qubi s a es, |φand |ψha e he same n-pa i e en an-
glemen i and only i he e a e none-qubi uni a y ans o ma-
ions Ui, such ha |φ=n
i=1Ui|ψ. I hese one-qubi uni a y
ans o ma ions belong o he Cli o d g oup, hen bo h s a es a e
said o be local Cli o d equi alen . The one-qubi Cli o d g oup
is gene a ed by he Hadama d ga e H=(|00|+|01|+|10|−
|11|)/√2 and he phase ga e P=|00|+i|11|.
Van den Nes , Dehaene, and De Moo ound ha he succes-
si e applica ion o a ans o ma ion wi h a simple g aphical de-
sc ip ion is sufficien o gene a e he comple e equi alence class
o g aph s a es unde local uni a y ope a ions wi hin he Cli o d
g oup (he ea e simply e e ed as class o o bi ) [49].Thissimple
ans o ma ion is LC.
On he s abilize , LC on he qubi iinduces he map Y(i)→
Z(i),Z(i)→ −Y(i)on he qubi i, and he map X(j)→ −Y(j),
Y(j)→ X(j)on he qubi s j∈N(i)[2]. On he gene a o s, LC on
he qubi imaps he gene a o s gold
jwi h j∈N(i) o gnew
jgnew
i.
G aphically, LC on he qubi iac s as ollows: One picks ou
he e ex iand in e s he neighbo hood N(i)o i; i.e., e ices
in he neighbo hood which we e connec ed become disconnec ed
and ice e sa.
I has been shown by Van den Nes , Dehaene, and De Moo ha
o a pa icula class o qubi g aph s a es local uni a y equi alence
implies local Cli o d equi alence [50]. Mo eo e , nume ical e-
sul s show ha local Cli o d equi alence coincides wi h local uni-
a y equi alence o qubi g aph s a es associa ed wi h connec ed
g aphs up o n=7 e ices[1,2]. I should be no ed, howe e , ha
no all local uni a y ans o ma ions be ween g aph s a es can be
ep esen ed as successi e LCs. A coun e example wi h n=27 is de-
sc ibed in [51].
Using LC, one can gene a e he o bi s o all LC-inequi alen n-
qubi g aph s a es. Fo a small n, he numbe o o bi s has been
well known o a long ime (see, e.g., [48]). Specifically, o n=8,
he e a e 101 LC-inequi alen classes.
3. C i e ia o he classifica ion
Following HEB, he c i e ia o o de ing he classes a e:
(a) numbe o qubi s, (b) minimum numbe o con olled-Zga es
needed o he p epa a ion, (c) he Schmid measu e, and (d) he
ank indexes. Fo ins ance, class No. 1 is he only one con ain-
ing wo-qubi g aph s a es, class No. 2 is he only one con aining
h ee-qubi g aph s a es [1,2]. Classes No. 3 and No. 4 bo h ha e
n=4 qubi s and equi e a minimum o |E|=3 con olled-Zga es.
Howe e , class No. 3 has Schmid measu e ES=1, while class
No. 4 has ES=2.
3.1. Minimum numbe o con olled-Z ga es o he p epa a ion
Di e en membe s o he same LC class equi e a di e en
numbe o con olled-Zga es o hei p epa a ion s a ing om
he s a e |+=(|0+|1)/√2 o each qubi . The fi s c i e ion o
ou classifica ion is he minimum numbe o con olled-Zga es
equi ed o p epa ing one g aph s a e wi hin he LC class. This co -
esponds o he numbe o edges o he g aph wi h he minimum
numbe o edges wi hin he LC class, |E|. We will p o ide a ep e-
sen a i e wi h he minimum numbe o edges o each LC class.
3.2. Schmid measu e
The Schmid measu e was in oduced by Eise and B iegel as
a ool o quan i ying he genuine mul ipa i e en anglemen o
quan um sys ems [52] (see also [53]). Any s a e ec o |ψ∈
H(1)⊗···⊗H(N)o a composi e quan um sys em wi h Ncom-
ponen s can be ep esen ed as
|ψ=
R

i=1
ξiψ(1)
i⊗···⊗ψ(N)
i,(3)
whe e ξi∈C o i=1,...,R, and |ψ(j)
i∈H(j), o j=1,...,N.
The Schmid measu e associa ed wi h a s a e ec o |ψis hen
defined as
ES|ψ =log2( ), (4)
whe e is he minimal numbe Ro e msin hesumo Eq.(3)
o e all linea decomposi ions in o p oduc s a es. In case o a wo-
componen sys em (N=2), he minimal numbe o p oduc e ms
is gi en by he Schmid ank o he s a e |ψ. Hence, he Schmid
measu e could be conside ed a gene aliza ion o he Schmid ank
o mul ipa i e quan um sys ems [see Eq. (9) below]. The Schmid
measu e can be ex ended o mixed s a es by means o a con ex
oo ex ension. In his Le e , howe e , we will deal only wi h pu e
s a es.
Gi en a g aph G=(V,E),apa i ion o Vis any uple
(A1,...,AM)o disjoin subse s Ai⊂V,wi hM
i=1Ai=V.Incase
M=2, we e e o he pa i ion as a bipa i ion, and deno e i
(A,B).Wewillw i e
(A1,...,AN)⩽(B1,...,BM), (5)
i (A1,...,AN)is a fine pa i ion han (B1,...,BM), which means
ha e e y Aiis con ained in some Bj. The la e is hen a coa se
pa i ion han he o me . Fo any g aph G=(V,E), hepa -
i ioning whe e (A1,...,AM)=Vsuch ha |Ai|=1, o e e y
i=1,...,M, is e e ed o as he fines pa i ion.
We mus poin ou ha ESis noninc easing unde a coa se
g aining o he pa i ioning: I wo componen s a e me ged in o -
de o o m a new componen , hen he Schmid measu e can
only dec ease. I we deno e he Schmid measu e o a s a e ec-
o |ψe alua edwi h espec oapa i ioning(A1,...,AN)as
E(A1,...,AN)
S(|ψ), meaning ha he espec i e Hilbe spaces a e
hose o he g ains o he pa i ioning, hen he noninc easing
p ope y o EScan be exp essed as
E(A1,...,AN)
S|ψ⩾E(B1,...,BM)
S|ψ,(6)
i (A1,...,AN)⩽(B1,...,BM).
Le (A,B)be a bipa i ion (i.e., A∪B=V;A∩B=∅) o a g aph
G=(V,E),wi hV={1,...,N}, and le us deno e he adjacency
ma ix o he g aph by Γ, i.e., he symme ic ma ix wi h elemen s
Γij =1,i (i,j)∈E,
0,o he wise. (7)
When we a e dealing wi h a bipa i ion, i is use ul o label he
e ices o he g aph so ha A={1,...,p},B={p+1,...,N}.
Then, we can decompose he adjacency ma ix Γin o subma i-
ces ΓA,ΓB( ha ep esen edges wi hin Aand edges wi hin B),
and ΓAB ( he |A|×|B|o -diagonal subma ix o he adjacency
ma ix Γ ha ep esen s hose edges be ween Aand B),
ΓAΓAB
ΓT
AB ΓB=Γ. (8)
The Schmid ank SRA(G)o a g aph s a e |G ep esen ed by he
g aph G=(V,E), wi h espec o he bipa i ion (A,B),isgi enby
he bina y ank [i.e., he ank o e GF(2)] o he subma ix ΓAB,
SRA(G)= ankF2(ΓAB). (9)
I ollows s aigh o wa dly om he defini ion ha SRA(G)=
SRB(G), because he di e en bipa i ions a e fixed by choosing he
smalle pa , say A, o he bipa i ion (A,B), which gi es 2N−1bi-
pa i ions.
3.3. Rank indexes
While calcula ing he Schmid ank wi h espec o all possible
bipa i ions o a gi en g aph, le us coun how many imes a ce -
ain ank occu s in all he bipa i e spli s, and hen classi y his
in o ma ion acco ding o he numbe o e ices in A, he smalle
pa o he spli unde conside a ion. The e is a compac way o
exp ess his in o ma ion, he so-called ank indexes [1,2]. The ank
index o all he bipa i e spli s wi h p e ices in he smalle pa
Ais gi en by he p- uple
RIp=νp
p,...,νp
1=νp
j1
j=p,(10)
whe e νp
jis he numbe o imes in which SRA(G)=j,wi h
|A|=p, occu s.
4. P ocedu es and esul s
The main esul s o he Le e a e summa ized in Fig. 2 and
Table 1. In he ollowing, we p o ide de ails on he calcula ions
leading o hese esul s.
4.1. O bi s unde local complemen a ion
We ha e gene a ed all LC o bi s o n=8 and calcula ed
he numbe o non-isomo phic g aphs in each LC o bi , deno ed
by |LC|. These numbe s a e coun ed up o isomo phism.
Fig. 1. The se o e ices 4, 6, and 8 is he minimal e ex co e o he g aph (le ).
The se o e ices 3, 5, 7, and 8, is a e ex co e o he g aph, bu is no minimal,
i has size 4 ( igh ).
In addi ion, o each o bi , we ha e calcula ed a ep esen a-
i e wi h he minimum numbe o edges |E|. As ep esen a i e, we
ha e chosen he one (o one o hose) wi h he minimum numbe
o edges and he minimum maximum deg ee (i.e., numbe o edges
inciden wi h a e ex). This means ha he g aph s a e associ-
a ed o his g aph equi es he minimum numbe o con olled-Z
ga es o i s p epa a ion, and he minimum p epa a ion dep h (i.e.,
i s p epa a ion equi es a minimum numbe o s eps) [54].All he
ep esen a i es o each o he 101 o bi s a e illus a ed in Fig. 2.
|LC|and |E|a e in Table 1.
4.2. Bounds o he Schmid measu e
I is a well-known ac ha o any measu e o mul ipa icle
en anglemen p oposed so a , including he Schmid measu e ES,
he compu a ion is exceedingly difficul o gene al s a es. In o de
o de e mine ES, one has o show ha a gi en decomposi ion in
Eq. (3) wi h R e ms is minimal. Fo a gene al s a e, he minimiza-
ion p oblem in ol ed can be a e y difficul p oblem o nume ical
analysis, which scales exponen ially in he numbe o pa ies Nas
well as in he deg ee o en anglemen o he s a e i sel . Ne e he-
less, his ask becomes easible i we es ic ou a en ion o g aph
s a es. HEB es ablished se e al uppe and lowe bounds o he
Schmid measu e in g aph heo e ical e ms [1,2]. These bounds
make possible o de e mine he Schmid measu e o a la ge num-
be o g aphs o p ac ical impo ance, because in many cases he
bounds p oposed a e easily compu able and, ema kably, he uppe
and lowe bounds equen ly coincide.
4.2.1. Pauli pe sis ency and size o he minimal e ex co e
Fo any g aph s a e |G, uppe bounds o i s Schmid measu e
ES(|G)a e he Pauli pe sis ency PP(G)and he size o he minimal
e ex co e VC(G),
ES|G⩽PP(G)⩽VC(G). (11)
The Pauli pe sis ency is he minimal numbe o local Pauli mea-
su emen s necessa y o disen angle a g aph s a e. Conce ning his
ques ion, HEB desc ibed g aphical ans o ma ion ules when local
Pauli measu emen s a e applied [1,2].
A e ex co e is a concep om g aph heo y: I is any subse
V⊆Vo e ices in a g aph G o which any edge o Gis inci-
den (see Fig. 1). The e o e, he minimal e ex co e o a g aph is
he smalles one, whose size is deno ed by VC(G). Acco ding o he
g aphical ules o he Pauli measu emen s, since each σzmeasu e-
men simply dele es all edges inciden o a e ex, he size o he
minimal e ex co e would equal he Pauli pe sis ency, p o ided
ha we es ic he Pauli measu emen s o σzmeasu emen s. Ne -
e heless, in g aphs wi h many edges, i.e., e y connec ed, a p ope
combina ion o σx,σy, and σzmeasu emen s could p o ide a
mo e efficien disen angling sequence, gi ing a be e uppe bound
PP(G) o he Schmid measu e. See [1,2] o de ails.
4.2.2. Maximal Schmid ank
Fo any g aph s a e |G, a lowe bound o he Schmid measu e
ES(|G)is he maximal Schmid ank,
SRmax(G)⩽ES|G.(12)
While calcula ing he Schmid ank wi h espec o all possible
bipa i ions o a gi en g aph G=(V,E), i one maximizes he
Schmid ank o e all bipa i ions (A,B)o he g aph, and akes
in o accoun he noninc easing p ope y o ES|(G)[see Eq. (6)],
hen one ob ains a lowe bound o he Schmid measu e wi h e-
spec o he fines pa i ioning. This lowe bound is he maximal
Schmid ank,
SRmax(G):=max
A⊆VSRA(G). (13)
Acco ding o he defini ion o Schmid ank, he maximal Schmid
ank o any s a e is, a mos , N
2, i.e., he la ges in ege less han
o equal o N
2.
4.2.3. Addi ion and dele ion o edges and e ices
As we men ioned in Sec ion 2.2, applying he LC- ule does no
change he Schmid measu e ES. I is in e es ing o ema k ha
o he local changes o he g aph, such as he dele ion o edges o
e ices, ha e only a limi ed e ec on ES. This ac is es ablished
by HEB [1] in wha hey call he edge/ e ex ule: On one hand, by
dele ing (o adding) an edge ebe ween wo e ices o a g aph
G he Schmid measu e o he esul ing g aph G=G±ecan a
mos dec ease (o inc ease) by 1. On he o he hand, i a e ex
(including all i s inciden edges) is dele ed, he Schmid measu e
o he esul ing g aph G=G− canno inc ease, and will a mos
dec ease by one. I ES(|G+e)deno es he Schmid measu e o he
g aph s a e co esponding o he g aph G+e, hen he p e ious
ules can be summa ized as
ES|G+e⩽ES|G+1,(14a)
ES|G−e⩾ES|G−1,(14b)
ES|G− ⩾ES|G −1.(14c)
We ha e used hese ules in wo ways: Fi s ly, as an in e nal es
o check ou calcula ions, compa ing pai s o g aphs connec ed by
a sequence o addi ion o dele ion o edges/ e ices; and secondly,
as a use ul ool ha , in some g aphs, has enabled us o go om
a bounded o a de e mined alue o he Schmid measu e, once
again by compa ison be ween a p oblema ic g aph Gand a e-
sul ing g aph G( ypically ob ained by edge o e ex dele ion) o
a known Schmid measu e.
4.2.4. Schmid measu e in some special ypes o g aphs
The e a e some special ypes o g aph s a es in which lowe
and uppe bounds o he Schmid measu e coincide (see [1]), gi -
ing di ec ly a de e mined alue o ES. Since he maximal Schmid
ank o any s a e can be a mos N
2, and es ic ing ou sel es
o s a es wi h coinciden uppe and lowe bounds o ES,i is ue
ha SRmax(G)=ES(|G)=PP(G)=VC(G)⩽N
2. This is he case
o GHZ s a es, and s a es ep esen ed by ees, ings wi h an e en
numbe o e ices, and clus e s. In ou wo k we ha e used he
ollowing esul s conce ning GHZ s a es and ees:
(a) The Schmid measu e o any mul ipa i e GHZ s a e is 1.
(b) A ee T is a g aph ha has no cycles. The Schmid measu e
o he co esponding g aph s a e |Tis he size o i s minimal
e ex co e : ES(|T)=VC(T).
The e is ano he in e es ing kind o g aphs o ou pu poses, he
so-called 2-colo able g aphs. A g aph is said o be 2-colo able when
i is possible o pe o m a p ope 2-colo ing oni :Thisisalabeling
V→{1,2}, such ha all connec ed e ices a e associa ed wi h
a di e en elemen om {1,2}, which can be iden ified wi h wo
colo s. I is a well-known ac in g aph heo y ha a necessa y and
sufficien c i e ion o a g aph o be 2-colo able is ha i does no
con ain any cycles o odd leng h. Ma hema icians call hese g aphs
bipa i e g aphs due o he ac ha he whole se o e ices can
be dis ibu ed in o wo disjoin subse s Aand B, such ha no wo
e ices wi hin he same subse a e connec ed, and he e o e e e y
edge connec s a e ex in Awi h a e ex in B.
HEB [1] p o ided lowe and uppe bounds o he Schmid
measu e ha could be applied o g aph s a es ep esen ed by 2-
colo able g aphs:
1
2 ankF2(Γ ) ⩽ES|G⩽|V|
2,(15)
whe e Γis he adjacency ma ix o he 2-colo able g aph. I Γis
in e ible, hen
ES|G =|V|
2.(16)
Besides, HEB poin ed ou ha any g aph Gwhich is no 2-co-
lo able can be u ned in o a 2-colo able one Gby simply dele ing
he app op ia e e ices on cycles wi h odd leng h p esen in G.
The iden ifica ion o his g aphical ac ion wi h he e ec o a σz
measu emen on qubi s co esponding o such e ices yields new
uppe bounds o ES(|G):
ES|G⩽ES|G+M⩽|V−M|
2+M⩽|V|+M
2,(17)
whe e Mis henumbe o emo ed e ices.Weha eused hese
new bounds in some g aphs as a ool o check ou calcula ions.
5. Conclusions, open p oblems, and u u e de elopmen s
To sum i all up, we ha e ex ended o 8 qubi s he classifica-
ion o he en anglemen o g aph s a es p oposed in [1] o n<8
qubi s. No ice ha o n=8 we ha e 101 classes, while o n<8
he e a e only 45 classes. Fo each o hese classes we ob ain a
ep esen a i e which equi es he minimum con olled-Zga es o
i s p epa a ion (see Fig. 2), and calcula e he Schmid measu e o
he 8-pa i e spli (which measu es he genuine 8-pa y en angle-
men o he class), and he Schmid anks o all bipa i e spli s
(see Table 1).
This classifica ion will help us o ob ain new all- e sus-no hing
p oo s o Bell’s heo em [16] and new Bell inequali ies. Specifically,
any 8-qubi g aph s a e belonging o a class wi h a ep esen a i e
wi h 7 edges (i.e., a ee) has a specific ype o Bell inequali y [22].
Mo e gene ally, i will help us o in es iga e he nonlocali y (i.e.,
he non-simulabili y o he p edic ions o quan um mechanics by
means o non-local hidden a iable models) o g aph s a es [21].
Ex ending he classifica ion in [1] a u he s ep sheds some
ligh on he limi a ions o he me hod o classifica ion. The c i e-
ia used in [1] o o de he classes (see Sec ion 3)al eady ailed
o dis inguish all classes in n=7. Fo ins ance, classes No. 40,
No. 42, and No. 43 in [1,2] ha e he same numbe o qubi s, equi e
he same minimum numbe o con olled-Zga es o he p epa a-
ion, and ha e he same Schmid measu e and ank indexes. The
same p oblem occu s be ween classes No. 110 and No. 111, be-
ween classes No. 113 and No. 114, and be ween classes No. 116
and No. 117 in ou classifica ion (see Table 1). Following [1,2],we
ha e placed he class wi h lowe |LC|in he fi s place. Howe e ,
his solu ion is no sa is ac o y, since |LC|is no ela ed o he en-
anglemen p ope ies o he class. On he o he hand, Van den
Nes , Dehaene, and De Moo ha e p oposed a fini e se o in-
a ian s ha cha ac e izes all classes [55]. Howe e , his se has
mo e han 2 ×1036 in a ian s al eady o n=7. The p oblem o
ob aining a minimum se o in a ian s capable o dis inguishing all
classes wi h n⩽8 qubi s will be add essed elsewhe e [56].
Ano he weak poin in he me hod is ha he p ecise alue o
ESis s ill unknown o some classes. The good news is ha , o
mos o hese classes, he alue migh be fixed i we knew he
Fig. 2. G aphs associa ed o he 101 classes on 8-qubi g aph s a es inequi alen unde local complemen a ion and g aph isomo phism. We ha e chosen as ep esen a i e
o he class he one (o one o hose) wi h minimum numbe o edges and minimum maximum deg ee (i.e., numbe o edges inciden wi h a e ex), which means ha i
equi es he minimum numbe o con olled-Zga es in he p epa a ion and minimum p epa a ion dep h.

Table 1
En anglemen o he 101 classes o 8-qubi g aph s a es. No. is he numbe o he class; i is assigned a ending o |E|,ES,andRI j; he numbe ing s a s a he poin in
which he one in Re s. [1,2] ends. |LC|is he numbe o nonisomo phic elemen s o he class. |E|is he numbe o edges o hose ep esen a i es wi h he minimum numbe
o edges. ESis he Schmid measu e (o i s lowe and uppe bounds). RI jis he ank index wi h jqubi s in he smalle bipa i ion (i.e., he numbe o bipa i e spli s in
which a ce ain ank occu s; anks appea in dec easing o de om le o igh ). 2-col indica es whe he o no a 2-colo able ep esen a i e exis s.
No. |LC||E|ESRI4RI3RI22-col No. |LC||E|ESRI4RI3RI22-col
46 2 7 1 (0,0,0,35) (0,0,56) (0,28) yes 97 154 8 4 (8,22,4,1) (42,13,1) (27,1) no
47 6 7 2 (0,0,20,15) (0,30,26) (12,16) yes 98 542 8 4 (8,22,5,0) (42,14,0) (27,1) no
48 6 7 2 (0,0,30,5) (0,45,11) (15,13) yes 99 300 8 4 (12,16,7,0) (44,11,1) (27,1) yes
49 16 7 2 (0,0,30,5) (0,45,11) (17,11) yes 100 214 8 4 (14,17,4,0) (48,8,0) (28,0) yes
50 4 7 2 (0,0,34,1) (0,48,8) (16,12) yes 101 14 9 3 (0,20,15,0) (24,32,0) (25,3) no
51 16 7 2 (0,0,34,1) (0,51,5) (19,9) yes 102 66 9 3 (0,28,7,0) (32,24,0) (25,3) no
52 10 7 3 (0,12,16,7) (16,28,12) (20,8) yes 103 66 9 3 (0,30,5,0) (36,20,0) (26,2) yes
53 16 7 3 (0,12,22,1) (16,34,6) (20,8) yes 104 6 9 3 (0,32,0,3) (32,24,0) (24,4) yes
54 44 7 3 (0,12,22,1) (16,35,5) (21,7) yes 105 57 9 3 <4 (0,30,5,0) (36,19,1) (25,3) no
55 16 7 3 (0,18,14,3) (18,33,5) (21,7) yes 106 28 9 4 (8,18,9,0) (38,18,0) (25,3) no
56 44 7 3 (0,18,14,3) (22,29,5) (23,5) yes 107 17 9 4 (8,20,6,1) (32,24,0) (24,4) no
57 10 7 3 (0,18,15,2) (18,36,2) (21,7) yes 108 72 9 4 (8,20,7,0) (36,20,0) (25,3) no
58 25 7 3 (0,18,16,1) (18,36,2) (22,6) yes 109 87 9 4 (8,20,7,0) (40,16,0) (27,1) no
59 44 7 3 (0,18,16,1) (22,31,3) (23,5) yes 110 114 9 4 (8,22,5,0) (40,16,0) (26,2) no
60 44 7 3 (0,24,9,2) (24,30,2) (23,5) yes 111 372 9 4 (8,22,5,0) (40,16,0) (26,2) no
61 26 7 3 (0,24,10,1) (28,25,3) (23,5) yes 112 70 9 4 (8,24,2,1) (40,16,0) (26,2) no
62 120 7 3 (0,24,10,1) (28,26,2) (24,4) yes 113 264 9 4 (8,24,3,0) (44,12,0) (27,1) no
63 66 7 3 (0,26,7,2) (30,24,2) (25,3) yes 114 542 9 4 (8,24,3,0) (44,12,0) (27,1) no
64 14 7 4 (8,12,12,3) (32,18,6) (24,4) yes 115 156 9 4 (12,18,5,0) (46,9,1) (27,1) no
65 25 7 4 (8,12,14,1) (32,20,4) (24,4) yes 116 174 9 4 (12,20,3,0) (46,10,0) (27,1) no
66 120 7 4 (8,14,12,1) (34,19,3) (25,3) yes 117 542 9 4 (12,20,3,0) (46,10,0) (27,1) no
67 72 7 4 (8,16,10,1) (36,17,3) (25,3) yes 118 262 9 4 (12,20,3,0) (48,8,0) (28,0) no
68 172 7 4 (8,18,8,1) (38,16,2) (26,2) yes 119 802 9 4 (14,19,2,0) (50,6,0) (28,0) no
69 10 8 2 (0,0,34,1) (0,52,4) (20,8) yes 120 117 9 4 (16,16,3,0) (50,6,0) (28,0) yes
70 10 8 2 (0,0,35,0) (0,54,2) (21,7) yes 121 10 10 3 (0,32,2,1) (32,24,0) (24,4) no
71 10 8 3 (0,12,22,1) (16,36,4) (20,8) no 122 37 10 3 (0,32,3,0) (40,16,0) (27,1) yes
72 21 8 3 (0,12,22,1) (16,36,4) (22,6) no 123 36 10 4 (8,22,5,0) (44,12,0) (26,2) no
73 10 8 3 (0,18,17,0) (18,36,2) (21,7) no 124 7 10 4 (8,24,0,3) (32,24,0) (24,4) no
74 44 8 3 (0,18,17,0) (22,32,2) (23,5) yes 125 103 10 4 (8,24,3,0) (42,14,0) (26,2) no
75 66 8 3 (0,18,17,0) (22,33,1) (24,4) no 126 46 10 4 (8,24,3,0) (44,12,0) (27,1) no
76 26 8 3 (0,20,14,1) (24,30,2) (24,4) yes 127 170 10 4 (8,26,1,0) (46,10,0) (27,1) no
77 26 8 3 (0,24,10,1) (24,31,1) (23,5) yes 128 74 10 4 (12,20,3,0) (46,10,0) (27,1) yes
78 28 8 3 (0,24,10,1) (28,27,1) (23,5) no 129 340 10 4 (12,22,1,0) (48,8,0) (27,1) no
79 44 8 3 (0,24,11,0) (28,26,2) (23,5) no 130 254 10 4 (12,22,1,0) (50,6,0) (28,0) no
80 132 8 3 (0,24,11,0) (28,27,1) (24,4) no 131 433 10 4 (14,21,0,0) (52,4,0) (28,0) no
81 114 8 3 (0,24,11,0) (30,25,1) (25,3) yes 132 476 10 4 (16,18,1,0) (52,4,0) (28,0) no
82 72 8 3 (0,26,9,0) (30,26,0) (25,3) no 133 28 10 4 <5 (12,22,0,1) (48,8,0) (28,0) no
83 72 8 3 (0,28,6,1) (32,23,1) (25,3) yes 134 9 11 3 <4 (0,30,5,0) (40,15,1) (25,3) no
84 198 8 3 (0,28,7,0) (34,22,0) (26,2) yes 135 39 11 4 (8,26,1,0) (44,12,0) (26,2) no
85 56 8 3 <4 (0,30,4,1) (34,21,1) (25,3) no 136 46 11 4 (12,20,3,0) (50,6,0) (27,1) no
86 28 8 4 (8,16,10,1) (32,22,2) (24,4) no 137 208 11 4 <5 (16,18,1,0) (52,4,0) (28,0) no
87 10 8 4 (8,16,10,1) (32,24,0) (24,4) yes 138 298 11 4 <5 (18,17,0,0) (54,2,0) (28,0) no
88 56 8 4 (8,16,10,1) (36,18,2) (26,2) no 139 24 11 4 <5 (20,10,5,0) (50,5,1) (27,1) no
89 66 8 4 (8,16,11,0) (36,18,2) (25,3) yes 140 267 11 4 <5 (20,14,1,0) (54,2,0) (28,0) no
90 72 8 4 (8,18,9,0) (34,22,0) (25,3) no 141 4 12 4 (28,0,7,0) (56,0,0) (28,0) no
91 63 8 4 (8,18,9,0) (36,20,0) (26,2) yes 142 22 12 4 <5 (14,21,0,0) (56,0,0) (28,0) no
92 66 8 4 (8,18,9,0) (38,16,2) (25,3) no 143 46 12 4 (20,12,3,0) (50,6,0) (27,1) yes
93 176 8 4 (8,18,9,0) (38,17,1) (26,2) no 144 28 13 4 (28,4,3,0) (56,0,0) (28,0) no
94 76 8 4 (8,20,6,1) (36,19,1) (25,3) no 145 7 13 4 <5 (16,18,1,0) (56,0,0) (28,0) no
95 194 8 4 (8,20,7,0) (38,18,0) (26,2) yes 146 51 13 4 <5 (24,10,1,0) (56,0,0) (28,0) no
96 352 8 4 (8,20,7,0) (40,15,1) (26,2) no
alue o he 5-qubi ing clus e s a e, which is he fi s g aph
s a e in he classifica ion o which he alue o ESis unknown
[1,2]. Un o una ely, we ha e no made any p og ess in calcula ing
ES o he 5-qubi ing clus e s a e.
Table 1 shows ha he e a e no 8-qubi g aph s a es wi h ank
indexes RIp=[νp
j]1
j=pwi h νp
j= 0i j=p, and νp
j=0i j<p,
i.e., wi h maximal ank wi h espec o all bipa i e spli s, i.e., such
ha en anglemen is symme ically dis ibu ed be ween all pa ies.
These s a es a e obus agains disen anglemen by a ew measu e-
men s. Nei he he e a e 7-qubi g aph s a es wi h his p ope y
[1,2]. This makes mo e in e es ing he ac ha he e is a single
5-qubi and a single 6-qubi g aph s a e wi h his p ope y [1,2].
Acknowledgemen s
The au ho s hank H.J. B iegel, O. Gühne, M. G assl, M. Hein,
C. San ana, and M. Van den Nes , o hei help. This wo k has
benefi ed om he use o he p og am nau y [57] o compu ing
au omo phism g oups o g aphs. A.C., A.J.L., and P.M. acknowledge
suppo om p ojec s No. P06-FQM-02243, No. FIS2008-05596,
and No. PAI-FQM-0239. J.R.P. acknowledges suppo om p ojec s
No. P06-FQM-01649, No. MTM2008-05866-C03-01, and No. PAI-
FQM-0164.
Re e ences
[1] M. Hein, J. Eise , H.J. B iegel, Phys. Re . A 69 (2004) 062311.
[2] M. Hein, W. Dü , J. Eise , R. Raussendo , M. Van den Nes , H.J. B iegel, in:
G. Casa i, D.L. Shepelyansky, P. Zolle , G. Benen i (Eds.), Quan um Compu e s,
Algo i hms and Chaos, IOS P ess, Ams e dam, 2006.
[3] D. Go esman, Phys. Re . A 54 (1996) 1862.
[4] D. Schlingemann, R.F. We ne , Phys. Re . A 65 (2002) 012308.
[5] D. Schlingemann, Quan um In . Compu . 2 (2002) 307.
[6] R. Raussendo , H.J. B iegel, Phys. Re . Le . 86 (2001) 5188.
[7] M. an den Nes , A. Miyake, W. Dü , H.J. B iegel, Phys. Re . Le . 97 (2006)
150504.
[8] Y.-J. Han, R. Raussendo , L.-M. Duan, Phys. Re . Le . 98 (2007) 150404.
[9] W. Dü , H. Aschaue , H.-J. B iegel, Phys. Re . Le . 91 (2003) 107903.
[10] J. Dehaene, M. Van den Nes , B. De Moo , F. Ve s ae e, Phys. Re . A 67 (2003)
022310.
[11] D.M. G eenbe ge , M.A. Ho ne, A. Zeilinge , in: M. Ka a os (Ed.), Bell’s The-
o em, Quan um Theo y, and Concep ions o he Uni e se, Kluwe Academic,
Do d ech , 1989, p. 69.
[12] D.P. DiVincenzo, A. Pe es, Phys. Re . A 55 (1997) 4089.
[13] V. Sca ani, A. Acín, E. Schenck, M. Aspelmeye , Phys. Re . A 71 (2005) 042325.
[14] O. Gühne, G. Tó h, P. Hyllus, H.J. B iegel, Phys. Re . Le . 95 (2005) 120405.
[15] A. Cabello, Phys. Re . Le . 95 (2005) 210401.
[16] A. Cabello, P. Mo eno, Phys. Re . Le . 99 (2007) 220402.
[17] N.D. Me min, Phys. Re . Le . 65 (1990) 1838.
[18] M. A dehali, Phys. Re . A 46 (1992) 5375.
[19] G. Tó h, O. Gühne, H.J. B iegel, Phys. Re . A 73 (2006) 022303.
[20] L.-Y. Hsu, Phys. Re . A 73 (2006) 042308.
[21] A. Cabello, O. Gühne, D. Rod íguez, Phys. Re . A 77 (2008) 062106.
[22] O. Gühne, A. Cabello, Phys. Re . A 77 (2008) 032108.
[23] A.K. Eke , Phys. Re . Le . 67 (1991) 661.
[24] C.H. Benne , G. B assa d, C. C épeau, R. Jozsa, A. Pe es, W.K. Woo e s, Phys.
Re . Le . 70 (1993) 1895.
[25] R. Cle e, H. Buh man, Phys. Re . A 56 (1997) 1201.
[26] M. ˙
Zukowski, A. Zeilinge , M.A. Ho ne, H. Wein u e , Ac a Phys. Pol. A 93
(1998) 187.
[27] D. Ma kham, B.C. Sande s, Phys. Re . A 78 (2008) 042309.
[28] P. Wal he , K.J. Resch, T. Rudolph, E. Schenck, H. Wein u e , V. Ved al, M. As-
pelmeye , A. Zeilinge , Na u e (London) 434 (2005) 169.
[29] N. Kiesel, C. Schmid, U. Webe , O. Gühne, G. Tó h, R. U sin, H. Wein u e , Phys.
Re . Le . 95 (2005) 210502.
[30] C.-Y. Lu, X.-Q. Zhou, O. Gühne, W.-B. Gao, J. Zhang, Z.-S. Yuan, A. Goebel,
T. Yang, J.-W. Pan, Na . Phys. 3 (2007) 91.
[31] C.-Y. Lu, W.-B. Gao, O. Gühne, X.-Q. Zhou, Z.-B. Chen, J.-W. Pan, Phys. Re .
Le . 102 (2009) 030502.
[32] J.K. Pachos, W. Wieczo ek, C. Schmid, N. Kiesel, R. Pohlne , H. Wein u e ,
a Xi :0710.0895 [quan -ph].
[33] P.G. Kwia , J. Mod. Op . 44 (1997) 2173.
[34] P.G. Kwia , H. Wein u e , Phys. Re . A 58 (1998) R2623.
[35] C. Cinelli, M. Ba bie i, R. Pe is, P. Ma aloni, F. De Ma ini, Phys. Re . Le . 95
(2005) 240405.
[36] T. Yang, Q. Zhang, J. Zhang, J. Yin, Z. Zhao, M. ˙
Zukowski, Z.-B. Chen, J.-W. Pan,
Phys. Re . Le . 95 (2005) 240406.
[37]J.T.Ba ei o,N.K.Lang o d,N.A.Pe e s,P.G.Kwia ,Phys.Re .Le .95(2005)
260501.
[38] M. Ba bie i, F. De Ma ini, P. Ma aloni, G. Vallone, A. Cabello, Phys. Re . Le . 97
(2006) 140407.
[39] G. Vallone, E. Poma ico, P. Ma aloni, F. De Ma ini, V. Be a di, Phys. Re . Le . 98
(2007) 180502.
[40] H. Wein u e , M. ˙
Zukowski, Phys. Re . A 64 (2001) 010102(R).
[41] M. Eibl, S. Gae ne , M. Bou ennane, C. Ku sie e , M. ˙
Zukowski, H. Wein u e ,
Phys. Re . Le . 90 (2003) 200403.
[42] S. Gae ne , M. Bou ennane, M. Eibl, C. Ku sie e , H. Wein u e , Appl. Phys.
B 77 (2003) 803.
[43] M. Bou ennane, M. Eibl, S. Gae ne , C. Ku sie e , A. Cabello, H. Wein u e ,
Phys. Re . Le . 92 (2004) 107901.
[44] P. Wal he , M. Aspelmeye , K.J. Resch, A. Zeilinge , Phys. Re . Le . 95 (2005)
020403.
[45] S. Gae ne , M. Bou ennane, C. Ku sie e , A. Cabello, H. Wein u e , Phys. Re .
Le . 100 (2008) 070504.
[46] W.-B. Gao, C.-Y. Lu, X.-C. Yao, P. Xu, O. Gühne, A. Goebel, Y.-A. Chen, C.-Z. Peng,
Z.-B. Chen, J.-W. Pan, a Xi :0809.4277 [quan -ph].
[47] W.-B. Gao, X.-C, Yao, P. Xu, O. Gühne, A. Cabello, C.-Y. Lu, Z.-B. Chen, J.-W. Pan,
unpublished.
[48] L.E. Danielsen, Da abase o Sel -Dual Quan um Codes, h p://www.ii.uib.no/
~la sed/ nco bi s/. No e ha in his Le e we a e only in e es ed in g aph
s a es associa ed o connec ed g aphs. In quan um codes, connec ed g aphs
co espond o indecomposable quan um codes (i.e., hose ha canno be ex-
p essed as he di ec sum o wo smalle codes).
[49] M. Van den Nes , J. Dehaene, B. De Moo , Phys. Re . A 69 (2004) 022316.
[50] M. Van den Nes , J. Dehaene, B. De Moo , Phys. Re . A 71 (2005) 062323.
[51] Z. Ji, J. Chen, Z. Wei, M. Ying, a Xi :0709.1266 [quan -ph].
[52] J. Eise , H.J. B iegel, Phys. Re . A 64 (2001) 022306.
[53] S. Se e ini, Phys. Le . A 356 (2006) 99.
[54] M. Mhalla, S. Pe d ix, in: 8 h Wo kshop on Quan um In o ma ion P ocessing
(QIP’05), Bos on, Janua y 2005, a Xi :quan -ph/0412071.
[55] M. an den Nes , Dehaene, B. De Moo , Phys. Re . A 72 (2005) 014307.
[56] A. Cabello, A.J. López-Ta ida, P. Mo eno, J.R. Po illo, a Xi :0904.3551 [quan -
ph].
[57] B.D. McKay, nau y Use ’s Guide (Ve sion 2.4) Depa men o Compu e Sci-
ence, Aus alian Na ional Uni e si y, Canbe a, Aus alia, 2007.