Fermat's Library | q-2020-08-07-305 annotated/explained version.

Mapping graph state orbits under local complementation

Jeremy C. Adcock

, Sam Morley-Short

, Axel Dahlberg

, and Joshua W. Silverstone

Quantum Engineering Technology (QET) Labs, H. H. Wills Physics Laboratory & Department of Electrical & Electronic Engineering,

University of Bristol, Merchant Venturers Building, Woodland Road, Bristol BS8 1UB, UK

QuTech - TU Delft, Lorentzweg 1, 2628CJ Delft, The Netherlands

Graph states, and the entanglement they

posses, are central to modern quantum com-

puting and communications architectures. Lo-

cal complementation—the graph operation

that links all local-Cliﬀord equivalent graph

states—allows us to classify all stabiliser states

by their entanglement. Here, we study the

structure of the orbits generated by local com-

plementation, mapping them up to 9 qubits

and revealing a rich hidden structure. We pro-

vide programs to compute these orbits, along

with our data for each of the 587 orbits up to

9 qubits and a means to visualise them. We

ﬁnd direct links between the connectivity of

certain orbits with the entanglement proper-

ties of their component graph states. Fur-

thermore, we observe the correlations between

graph-theoretical orbit properties, such as di-

ameter and colourability, with Schmidt mea-

sure and preparation complexity and suggest

potential applications. It is well known that

graph theory and quantum entanglement have

strong interplay—our exploration deepens this

relationship, providing new tools with which to

probe the nature of entanglement.

1 Introduction

Graph states provide a language of entanglement be-

tween qubits and are at the core of modern quantum

computing and communication architectures across

all qubit platforms

1–7

. Graph states are a sub-

set of stabiliser states. Some stabiliser states are

local-Cliﬀord (LC) and every stabiliser state is local-

Cliﬀord equivalent to at least one graph state. Graph

states which are LC equivalent are related by repeated

application of a simple graph operation, local comple-

mentation

11,12

. Hence all sets of LC-equivalent sta-

biliser states can be completely described by sets, or

‘classes’, of graphs. Note that states which are LC

equivalent are also local unitary equivalent up to at

most 27 qubits

, with a lower bound of 8 qubits

Since local operations cannot change the type of en-

tanglement a state possesses, graph states provide a

Jeremy C. Adcock: jeremy.adcock@bristol.ac.uk

way to classify all stabiliser states by the entangle-

ment they posses.

Graph state entanglement is well studied

11–15

, with

each of the ∼1.6×10

non-isomorphic graph states up

to 12 qubits classiﬁed into ∼1.3×10

LC-inequivalent

classes

16,17

. There is a polynomial time algorithm to

compute the LC unitary relating two graph states (if

there is one)

18,19

. In contrast, the problem of de-

termining if a target graph state can be generated

from an input graph state using LC operations, lo-

cal Pauli measurements and classical communication

(LC+LPM+CC) is np-complete for both labelled

14,20

and unlabelled graphs

. It is also known that count-

ing single-qubit LC-equivalent graph states is #p-

complete

. Due to this hardness, exploration have

been limited to n ≤ 12 qubits. Ref. 17 supplies tables

containing information on every entanglement orbit

for n ≤ 12 as supplementary material. This includes

a canonical member graph state for each orbit, as well

as quantities relating to that state, and other classi-

fying information. For example, the minimum edge

number of a graph state in the class is given, along

with bounds on its Schmidt measure and the number

of graph states in the class.

Recently we showed that local complementation

can be used to generate graph states more eﬃ-

ciently

. However, little is known about the struc-

ture of the orbits that are generated by local com-

plementation. These orbits are themselves graphs, in

which each orbit vertex represents a graph state and

edges between them are induced by local complemen-

tation of diﬀerent graph state vertices (see Fig. 1).

Here, we refer to the object that links graphs via lo-

cal comeplemtation as their ‘orbit’, and we refer to

those component graphs as ‘graph states’. These or-

bits, which are wildly complex, give a fresh perspec-

tive for the study of stabiliser entanglement and graph

states, while providing new tools for optimising quan-

tum protocols.

Where previous work has ‘catalogued’ each class of

graph states and provided a set of graphs for each

class, in this work we focus on understanding the

structure of how each graph state is related to the

others via local complementation, by ’mapping’ the

space in which they live. To do so we generate the or-

bit of each of the 587 entanglement classes up to n ≤ 9

qubits. We also provide

‘graph state compass’ a

new tool to generate the orbit generated by local com-

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 1

arXiv:1910.03969v2 [quant-ph] 7 Jul 2020

plementation given an input graph state, along with

all of the data generated in this study and the code

used to generate the plots found in this manuscript

We compute graph-theoretical properties of these or-

bits and link these to properties of the member graph

states, while observing strong correlations between or-

bit complexity and known entanglement metrics. We

also identify promising applications of local comple-

mentation in both quantum secret sharing and compi-

lation of measurement-based protocols. By mapping

these orbits we expose the exquisite structure of graph

state orbits and present them as promising avenues for

further study.

2 Graph state orbits

Graph states are quantum states with a one-to-

one correspondence to mathematical graphs

11,12

. A

graph, G = (V, E), is a combinatoric object deﬁned

by a set of edges E between a set of vertices V . The

corresponding graph state is written:

|Gi =

(i,j)∈E

|+i

⊗|V |

. (1)

Here, |+i = (|0i + |1i)/

√

2 and CZ = |00ih00| +

|01ih01| + |10ih10| − |11ih11|. Connected n-vertex

graphs have genuine n-partite entanglement.

Remarkably, graph states can be LC-equivalent,

despite having diﬀerent constructions via nonlocal

Controlled-Z (CZ) gates

11,12

. Speciﬁcally, graphs are

LC-equivalent if and only if they can be transformed

into one another by successive applications of local

complementation.

Local complementation of a vertex α, LC

, applied

to a graph, G(V, E), acts to complement the neigh-

bourhood of the vertex α. That is, in the neighbour-

hood of α, it removes edges if they are present, and

adds any edges are missing (see Fig. 1a). More for-

mally:

(G(V, E)) :→ G(V, E

), (2)

where

= E ∪ K

(α)

− E ∩ K

(α)

= E∆K

(α)

. (3)

Here, K

(α)

is the set of edges of the complete graph

on the vertex set N

(α), the neighbourhood of α, and,

∆ is the symmetric diﬀerence. On graph states, the

following local unitary implements local complemen-

tation

11,12

−iX

i∈N

(α)

(4)

Where U

|Gi = |LC

(G)i. Repeated application

of local complementation is guaranteed to hit ev-

ery member of a entanglement class of LC-equivalent

graph states, given any member of that class as a

starting point

11,12

. This deﬁnes graph (and therefore

stabiliser) entanglement classes, each with their own

orbit under local complementation. Though these

classes have been catalogued

up to n = 12, to our

knowledge the structure of their orbits as not yet been

investigated.

All n-vertex graphs can be locally complemented in

n diﬀerent ways, generating up to n diﬀerent graphs.

Each of these can be locally complemented further,

generating up to n −1 new graphs (local complemen-

tation is self inverse). We can repeatedly local com-

plement graphs until we ﬁnd no new ones, concluding

that all graphs in the class have been found. By per-

forming every local complementation on every graph

in the class, the orbit is mapped (see Section 2.3). We

will denote these orbits L

for entanglement class i,

canonically indexed as in ref. 17.

This orbit is itself naturally represented as a

graph—its vertices are graph states and the edges that

link them are local complementations on the graph

state’s vertices (see Fig. 1). Edges of the orbits are la-

belled with a vertex index indicating which local com-

plementation links the two graph states on the orbit

vertices. Since local complementation is self-inverse,

these edges are undirected. Some simple examples of

orbits are shown in Figs. 1b,d.

2.1 A quantum Rubik’s cube

Local complementation orbits have an entertaining

analogy with the popular puzzle toy, the Rubik’s cube.

Each face of a Rubik’s cube is a diﬀerent colour, which

is itself separated into 3 × 3 = 9 individual squares.

This is the cube’s solved state. The toy has 6 basic

moves, which rotate the diﬀerent faces of the cube by

◦

. By applying these six moves in a random combi-

nation, a random state of the cube is generated. The

challenge is then to return the cube to its solved state.

For a mathematician, the challenge is to understand

the cube’s symmetry, and solve it in the general case.

Using about one billion seconds (35 years) of CPU

time, the Rubik’s cube Cayley graph—the orbit of

the states of the cube–has been computed

. Indeed,

a Rubik’s cube has ∼4.3×10

states and its orbit has

diameter 26. That is, any Rubik’s cube can always be

solved in 26 90

◦

moves or less (20 moves if both 90

◦

and 180

◦

rotations are allowed). ‘Cubers’, as Rubik’s

cube aﬁcionados are known, call 26 ‘god’s number’.

In our analogy, the many states of the toy are our

graph states, and rotating the diﬀerent faces of the

cube corresponds to local complementation of diﬀer-

ent graph vertices. As evidenced by the ratio of its

cardinality to its diameter (∼10

), the orbit of the

Rubik’s cube is highly dense (though each vertex only

has six edges). Each of the ∼1.3 million entanglement

classes of 12 qubits has its own unique orbit—each of

them is another Rubik’s cube (with 12 rather than

6 moves). Note there are factorially many entangle-

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 2

2. neighbourhood

3. complement

4. output

1. input

{1,2,3,4,5,6}

{1,2,3,4,5}

Local complementation

Figure 1: local complementation and the orbits it induces. Orbit edges are labelled with the vertex that undergoes local

complementation. a. A guide to local complementation. The neighbourhood of qubit α is complemented to yield the output

graph. b. The orbit L

(GHZ entanglement of four qubits). Here, L

and C

denote the orbit induced by local complementation

for entanglement class i. c. The orbit C

, where isomorphic graph states are considered equal. d. The orbit L

(cluster

state entanglement of four qubits). This is one of three equivalent orbits, which together contain every isomorphism of the

contained graph states. e. The orbit C

. f. The orbit C

. Graph state vertices are labelled descending clockwise from noon

(see b). We use directed edges when drawing C

orbits as only one isomorphism of the graph states can be drawn on an orbit.

ment classes as n is increased. God’s number (the

orbit diameter) for local complementation orbits de-

pends on the class. Using about a week of CPU time

on a standard desktop computer, we compute the di-

ameter of local complementation is maximally 9 for

9-qubit graph states. That is, any two LC-equivalent

graph states are at most 9 local complementations

distant from one another).

2.2 Isomorphic graph states

Graphs which are identical under relabelling of their

vertices are said to be isomorphic. Graph states which

are isomorphic share the same variety of entangle-

ment. This is an important feature for the imple-

mentation of protocols where qubit relabelling is non-

trivial—this includes most quantum information pro-

cessing and communication scenarios. Here we con-

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 3

sider both cases. We denote orbits C

when isomor-

phic graphs are considered equal (unlabelled graph

states), and L

otherwise (labelled graph states). By

examining our dataset, we observe that C

contain

on average

/8 as many graph states as their partner

orbits for n < 9 qubits. This greatly reduces the

computational resources needed to map and analyse

them. We note that all C

are subgraphs of L

for all

i. This subgraph is formed by merging all orbit ver-

tices corresponding to isomorphic graph states. This

can be seen by observing that isomorphic graph states

have isomorphic neighbourhoods in L

We ﬁnd that there are typically more than one L

orbit (for ﬁxed i), as most C

orbits do not con-

tain every isomorphism of it’s member graph states

(e.g. Fig. 1d)—the entanglement possessed is dis-

tributed in diﬀerent ways between the parties. These

equivalent orbits are themselves isomorphic, and to-

gether the set of L

(for ﬁxed i orbits) contains every

isomorphism of their component graph states. For ex-

ample, there are three equivalent orbits of L

(one of

which is shown in Fig. 1), each containing diﬀerent

isomorphisms of their component graph states. Some

entanglement classes have only one L

orbit, which

contains every isomorphism of the graph states. For

example, the classes which contain the ‘star’ and fully-

connected graph states. These orbits are composed of

| = n+1 graph states (vertices) and are themselves

a ‘star’ graph (see Section 3 and Fig. 1b).

As in L

orbits, edges of a C

orbit are undirected.

However, as a guide to the eye we display directed

edges for C

orbits when those edges are labelled, as

this allows the reader to identify which graph vertex

undergoes local complementation to reach the output

graph (see Fig. 1c,e,f).

2.3 Orbit exploration

Mapping the orbit of the i

entanglement class, L

containing a graph state |Gi, is a graph exploration

problem. Here, we use an exhaustive breadth-ﬁrst ex-

ploration to traverse the entire orbit, cataloguing each

graph state (vertices of the orbit) along with how lo-

cal complementation links them (edges of the orbit).

We start with a single graph state G, taken from ref.

17, in our catalogue, and perform each possible local

complementation on it. In doing so, we discover up

to n new orbit vertices and up to n new orbit edges.

Then we perform every possible local complementa-

tion on those output graph states and catalogue the

outputs by comparing them to graph states which we

have already found. This is repeated until every local

complementation has been performed on every graph

state in the catalogue (and no new graph states or

edges are found).

To map an n-qubit orbit, L

, which contains |L

graph states requires O(n|L

) local complementa-

tions and graph comparisons. By ‘graph compari-

son’, we mean evaluating if two graphs are equal, (or

whether they are isomporphic for a C

orbit). Linear

savings can be made by noting that local complemen-

tation is self inverse, and has no eﬀect when applied

to a vertex of degree 1.

We use this method to explore the L

for n ≤ 8 and

for n ≤ 9, that is, up to graph state entanglement

class i = 146 and i = 586 respectively. The largest of

these orbits contains 3248 and 8836 graph states, re-

spectively. GraphIsomorphism is a costly routine,

belonging to the complexity class np. Exploration of

makes heavy use of GraphIsomorphism, calling

it up to n|C

| times. However, since |C

|  |L

|, and

our graph states are of modest size, exploring C

to 9 qubits required less computational time than ex-

ploring L

up to 8 qubits.

In real-world applications, the physical location of

qubits is important—isomorphic graph states can not

be considered equal. However, to our knowledge, C

entanglement classes have not been studied in detail

before. Usually, most isomorphisms of a graph state

are not contained within a given C

orbit. Hence,

knowledge of C

, or at least its members, may be cru-

cial for measurement-based quantum protocols.

Local complementing symmetric vertices of an in-

put graph state will result in the same output graph

state. This observation can be used to improve the

eﬃciency of L

orbit exploration. The sets of vertices

which result in isomorphic graphs under local comple-

mentation can be found by computing the automor-

phism group of each graph state—vertices that are

exchanged in an automorphism result in isomorphic

graphs. For example, in the four-vertex ring graph,

all vertices are equivalent and so only a single com-

plementation is required, whereas for the four-vertex

line graph, there are two non-equivalent vertices, the

‘inner’ and ‘outer’ vertices. Hence, by computing the

automorphism group of each graph state as it is dis-

covered, and only local complementing the reduced

subset of graph state vertices that are not equivalent,

a saving can be made. Here, only ˜n|C

compar-

isons (and hence calls to GraphIsomorphism) need

be made (where ˜n = |E

|/|C

| is the mean number

of non-symmetric vertices on the graph states of C

In practice, the AutomorphismGroup is computed

in order to solve GraphIsomorphism

. Hence a

linear speedup is achieved. By examining our set of

computed orbits, we ﬁnd this technique reduces the

number of calls to GraphIsomorphism by at least

half for n ≤ 9.

3 Results

We compute a variety of graph properties of C

orbits

of 3-7 qubits and display them in Table 2. Deﬁnitions

of these quantities can be found in Appendix Section

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 4

5 6 9 11 14

9 11 14

8 14 17

Number of edges in graph state

Distance

Graph state index

Figure 2: Local complementation orbit L

. a. The orbit L

. b. The adjacency matrix of L

. c. The distance matrix of

. The adjacency matrix of a graph, A, has a row and column for each of the graph’s vertices. For each edge (i, j) present

in graph we write Γ

= n, where n is the lowest index of a local complementation that links them. Otherwise Γ

= 0.

Similarly, the distance matrix, D, gives the distance between two vertices: D

is equal to the minimum number of edges that

must be traversed to get from vertex i to vertex j. Regions of corresponding to isomorphic graph states are demarcated.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 5

For example we display the Schmidt measure, E

which is known to be a useful entanglement monotone

for graph states

11,28

, encoding the strength of error

correcting codes built from the state

. We also com-

pute the graph state’s rank-width

14,21

, rwd(G), which

plays a fundamental role the complexity of graph

state properties: any graph state property which is

expressible in so-called monadic second-order logic

(a higher-order logical system) can be computed in

time O(f(rwd(G))|V (G)|

), where f is an exponen-

tial function

. These properties are therefore known

as ‘ﬁxed-parameter tractable’, as they are polynomial

for graphs with ﬁxed rank-width. This includes the

vertex minor problem, deciding whether a graph can

be generated from another with only LC+LPM+CC

operations. It is also known that to be a universal re-

source for quantum computation, lattice graph states

must have unbounded rank-width as they increase in

size

. The rank-width of every graph state with

n ≤ 9 qubits is available in our online resource

. We

also provide a host of other graph theoretical proper-

ties of the orbit and their graph states, for example

their chromatic number, their diameter, and the size

of their automorphism group.

As per the canonical indexing of graph state en-

tanglement classes, we list the minimum degree of

each orbit: the smallest number of edges of any of

the orbit’s graph states. Using only CZ gates, this

is the minimum number gates needed to produce

Orbit type Correlation

coeﬃcient

Value

r(max(d

), |C

|) 0.62 ± 0.03

r(max(d

), E

) 0.77 ± 0.02

r(χ

, E

) 0.67 ± 0.02

r(χ

, E

) 0.81 ± 0.04

r(χ

, χ

) 0.032 ± 0.04

r(max(d

), |L

|) 0.60 ± 0.05

r(max(d

), E

) 0.93 ± 0.02

r(χ

, E

) 0.70 ± 0.05

r(χ

, E

) 0.44 ± 0.11

r(χ

, χ

) −0.09 ± 0.09

– r(E

, rwd) 0.62 ± 0.03

– r(E

, |e|) 0.78 ± 0.02

– r(E

, χ

) −0.17 ± 0.02

Table 1: Summary of the correlations observed. Here, E

is the Schmidt measure of the orbit, d

are the distances

between graph states in the orbit, χ is the chromatic number

of the orbit, χ

is the chromatic index of the orbit, χ

is the

lowest chromatic index of a graph state in the orbit, rwd

is the rank-width of the orbits’ graph states and |e| is the

minimum number edges of any graph state in the orbit. ‘–’

indicates that the tested property depends only on the set of

graph states in the orbit, and not the orbit structure.

the entanglement class from |+i, . We also provide

the graph state’s minimum chromatic index (mini-

mal edge colouring number), which corresponds to the

minimum number of time steps required to generate

a state in that entanglement class using only CZs

Here, we assume CZs can be performed between each

qubit arbitrarily, and note that interspersing CZs with

LCs can reduce the number of CZs required.

We ﬁnd correlations between orbit parameters and

compute their Pearson correlation coeﬃcients, −1 <

r(x, y) < 1, for orbit parameters x, y. Here, r = 1

implies there is exact linear correlation in the data,

r = −1 indicates an exact negative linear correla-

tion, and r = 0 implies no linear correlation what-

soever. To quantify entanglement of graph states,

we examine the Schmidt measure, a well-studied en-

tanglement monotone with many convenient relation-

ships to graph states

11,16,28

. For example, it is known

that and any graph state that corresponds to a maxi-

mum distance separable (MDS) error correcting code

must have Schmidt measure at least

|V |/2. MDS

codes are optimal error correcting codes in that they

are able to correct the greatest number of errors for a

given number of logical and physical qubits—that is,

they saturate the singleton bound.

We observe that the graph state Schmidt mea-

sure, E

, correlates strongly with orbit diameter

(r(max(d

), E

) = {0.77 ± 0.02, 0.93 ± 0.02}),

where the ﬁrst value is for C

and the second is for

. Interestingly, orbit diameter correlates more sig-

niﬁcantly with Schmidt rank than with orbit size

(r(max(d

), |O

|) = {0.62 ± 0.03, 0.60 ± 0.05}).

This indicates that more entangled states are likely

to have large, sparse orbits. Here, if the Schmidt

measure is not known, we take the average value of

the bounds, which are rarely loose. Furthermore,

orbit chromatic number, χ

, and Schmidt measure,

have high correlation coeﬃcients of r(χ

, E

) =

{0.67 ± 0.02, 0.70 ± 0.05}. Interestingly, orbit chro-

matic number, χ

, does not correlate with minimum

graph state chromatic index, χ

, which is the number

of CZ time steps needed to prepare that entanglement

class (r(χ

, χ

) = {0.032 ± 0.04, −0.09 ± 0.09}).

Meanwhile, orbit chromatic index, χ

, and Schmidt

measure, E

, correlate diﬀerently, depending on

whether isomorphic graph states are considered equal

(r(χ

, E

) = {0.81 ±0.04, 0.44 ±0.11} for n ≤ 8 and

n ≤ 7 respectively). Chromatic index indicates gives a

lower bound on the maximum degree in the orbit, that

is, the maximum number of graph states that a single

graph of the orbit is at most χ

. Hence classes with

high Schmidt measure tend to have at least one graph

state that can produce many diﬀerent graphs states

by local complementation. In most cases, χ

= n be-

cause the n available local complementations produce

diﬀerent (but potentially isomorphic graphs). Hence

little information can be gained from the chromatic

index of L

orbits, χ

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 6

Class |Q| |e| E

rwd |C

| |E

|/|C

| χ

Tree hd

i max(d

) |aut| 2D Loop E. H.

3 4 3 1 1 2 2 1 2 3 2 1 X 1 1 1 X X 7 7

4 4 3 2 1 4 5 1.25 2 2 2 2 X 1.67 3 1 X X 7 7

5 5 4 1 1 2 2 1 2 4 2 1 X 1 1 1 X X 7 7

6 5 4 2 1 6 9 1.5 2 3 2 2 7 1.8 3 2 X X X X

7 5 4 2 1 10 19 1.9 2 2 3 3 7 2.04 3 1 X X 7 X

8 5 5 2 < 3 2 3 3 1 3 3 2 2 X 1.33 2 1 X X 7 7

9 6 5 1 1 2 2 1 2 5 2 1 X 1 1 1 X X 7 7

10 6 5 2 1 6 9 1.5 2 4 2 2 7 1.8 3 2 X X X X

11 6 5 2 1 4 5 1.25 2 3 2 2 X 1.67 3 1 X X 7 7

12 6 5 2 1 16 34 2.13 2 3 3 3 7 2.25 3 3 7 X 7 X

13 6 5 3 1 10 20 2 2 3 3 3 7 2.04 3 1 X X 7 X

14 6 5 3 1 25 58 2.32 2 2 3 4 7 2.51 5 2 7 X X 7

15 6 6 2 1 5 8 1.6 2 3 3 3 7 1.7 3 1 X X 7 7

16 6 6 3 1 5 9 1.8 3 3 3 3 7 1.7 3 1 X X 7 7

17 6 6 3 2 21 47 2.24 3 3 3 5 7 2.32 4 0 7 X 7 X

18 6 6 3 2 16 29 1.81 2 2 3 6 7 2.22 4 0 7 X 7 7

19 6 9 3 < 4 2 2 2 1 3 3 2 1 X 1 1 1 X X 7 7

20 7 6 1 1 2 2 1 2 6 2 1 X 1 1 1 X X 7 7

21 7 6 2 1 6 9 1.5 2 5 2 2 7 1.8 3 2 X X X X

22 7 6 2 1 6 9 1.5 2 4 2 2 7 1.8 3 2 X X X X

23 7 6 2 1 16 34 2.13 2 4 3 3 7 2.25 3 3 7 X 7 X

24 7 6 2 1 10 19 1.9 2 3 3 3 7 2.04 3 1 X X 7 X

25 7 6 3 1 10 20 2 2 4 3 3 7 2.04 3 1 X X 7 X

26 7 6 3 1 16 35 2.19 2 3 3 3 7 2.25 3 3 7 X 7 X

27 7 6 3 1 44 114 2.59 2 3 3 4 7 2.84 5 3 7 X X X

28 7 6 3 1 44 118 2.68 2 3 3 4 7 2.84 5 3 7 X X X

29 7 6 3 1 14 30 2.14 2 3 3 4 7 2.34 5 1 X X 7 X

30 7 6 3 1 66 191 2.89 2 2 3 5 7 3.05 6 2 7 X 7 X

31 7 7 2 1 10 20 2 2 4 3 3 7 2.04 3 1 X X 7 X

32 7 7 3 1 10 21 2.1 3 4 3 3 7 2.04 3 1 X X 7 X

33 7 7 3 2 21 47 2.24 3 4 3 5 7 2.31 4 0 7 X 7 X

34 7 7 3 1 26 68 2.62 2 3 3 4 7 2.50 4 3 7 X 7 X

35 7 7 3 2 36 98 2.72 3 3 3 5 7 2.54 4 1 7 X 7 X

36 7 7 3 1 28 70 2.5 3 3 3 4 7 2.62 5 3 7 X 7 X

37 7 7 3 2 72 206 2.86 3 3 3 5 7 3.06 5 2 7 X 7 X

38 7 7 3 2 114 336 2.94 2 3 3 6 7 3.29 6 2 7 X X X

39 7 7 3 < 4 2 56 157 2.80 3 3 4 6 7 2.85 5 1 7 X 7 X

40 7 7 3 < 4 2 92 271 2.95 3 3 3 7 7 3.02 7 1 7 7 7 7

41 7 8 3 < 4 2 57 164 2.88 3 3 3 6 7 2.79 5 1 7 X 7 X

42 7 8 3 < 4 2 33 80 2.42 3 3 5 7 7 2.43 5 0 7 X 7 X

43 7 9 3 2 9 16 1.78 2 3 3 5 7 1.81 3 1 X X 7 7

44 7 9 3 < 4 2 46 109 2.37 3 3 5 7 7 2.81 5 0 7 X 7 X

45 7 10 3 < 4 2 9 16 1.78 3 4 3 4 7 1.97 4 0 X X 7 7

Table 2: A selection of properties of C

(see Appendix Figure 11 for a table showing a representative graph state from each

class of n < 9 qubits). Here, |Q| is the number of qubits of the orbit’s graph states, |e| is smallest number of edges of any

graph state member of C

. Each class’s Schmidt measure, E

, is written a < b to compactly express lower (a) and upper (b)

bounds, when an exact value is not known

11,17

. rwd is the class’s rank-width, |C

| is the size of the orbit, |E

| is the number of

edges on the orbit, χ

is the minimum chromatic number of the graph states in the class, χ

is the minimum chromatic index

of the graph states in the class (which corresponds to the minimum number of CZ gates required to prepare them), χ

the orbits chromatic number, χ

is the orbits chromatic index, ‘Tree’ is whether the orbit is a tree (excluding self-loops), d

are the distances between vertices of the orbit (therefore hd

i is the mean distance between any two vertices and max(d

)

the diameter of the orbit), |aut| is the size of the automorphism group of the orbit, ‘2D’ is whether the orbit is planar, ‘Loop’

is whether the orbit has any self-loops, ‘E.’ (‘H.’) is whether the graph has a cycle in which each edge (vertex) of the orbit is

visited precisely once. Deﬁnitions of all of these quantities can be found in Appendix Section 1. Properties of L

orbits may

diﬀer to their C

partner.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 7

, however, is much more varied and correlates well

with Schmidt rank. This can be understood as C

orbits consider only the topological properties of the

graph states.

We note that Schmidt measure, E

correlates well

with rank-width, rwd, and minimum edge count, |e|,

(r(E

, rwd) = 0.62 ± 0.03, r(E

, |e|) = 0.78 ±

0.02), but not with graph state chromatic index, χ

(r(E

, χ

) = −0.17 ± 0.02). Interestingly, Schmidt

measure, E

, (and therefore orbit chromatic index,

), strongly correlates with minimum edge count,

|e|, (the total number of CZs required to prepare an

entanglement class) but not with graph state chro-

matic index, χ

, (the number of CZ time steps re-

quired to prepare an entanglement class). Resources

for quantum computation are often lattices, and hence

have constant CZ preparation complexity (in terms of

time steps), though their rank-width must grow faster

than logarithmically

. We also note that there exist

eﬃcient entanglement puriﬁcation protocols for graph

states which have a chromatic number χ

= 2 (those

which are two-colourable)

. We note that all of the

correlations we observe with r >

/2 appear to come

from to be well behaved distributions, with no ‘cate-

strophic failures’ observed.

Some properties of a entanglement class’ graph

states can be deduced from properties of their orbit.

For example, class no. 40 has is the only orbit up to

seven qubits which has no self-loops. This implies that

none of its member graph states have a vertex of de-

gree 1 (leaves). Increasing qubit number, we observe

that 9% of orbits with n ≤ 10 qubits do not have self-

loops. It follows that the number of CZ gates needed

to generate any member of these classes is at least n.

Local complementation commutes when the neigh-

bourhoods of the two indices are disjoint. This cre-

ates a cycle in the graph state’s orbit. Hence it can

be deduced that orbits which are trees only contain

graph states in which all vertices are at most distance

two from one another, since they must share part of

their neighbourhood with every other qubit. We note

that only Greenberger-Horne-Zeilinger (GHZ) entan-

glement gives rise to L

orbits that are trees (for

n ≤ 8), and these contain only two non-isomorphic

graph states. Meanwhile there is one 3-vertex orbit

and three 4-vertex C

orbits which are trees for n ≤ 10

qubits. These are connected in a line, and contain

self-loops (see Fig. 1e).

Interestingly, some C

orbits are isomorphic to

other orbits, C

(i 6= j). Fig. 3a shows a table of

the most commonly found orbits, their size, and their

frequency in our dataset. Furthermore, Fig. 3c dis-

plays which orbits are isomorphic to one another in

the form of a matrix.

Figs. 1c and 1f are examples of isomorphic C

orbits

with vastly diﬀerent entanglement properties, that is,

perfect correlation (GHZ entanglement) and an op-

timal error correcting code

. In contrast, there are

no L

orbits that are isomorphic for n ≤ 8. That is,

only if the graph states are local Cliﬀord equivalent

are their L

orbits isomorphic. It is unclear which

properties of a graph state lead to isomorphic orbits,

however we note that graphs which share an isomor-

phic orbit often—but not always—have a similar con-

nectivity. Fig. 3b displays a set of similar but distinct

graph states whose orbits are isomorphic

A simple example of isomorphic orbits comes from

n-qubit GHZ entanglement, which always contain the

n-qubit ‘star’ graph. In a star graph, there are only

two diﬀerent local complementation operations. That

is, local complemenation can be applied to the centre

qubit or to one of the leaves. Applying local com-

plementation to the leaves does nothing, while apply-

ing local complementation to the centre qubit yields

the fully connected graph state. Applying local com-

plementation to qubit α of the fully-connected state

yields a star graph state where the center of the star is

qubit α. Hence these orbits contain only the star and

the fully-connected graph states. L

orbits have all n

of the isomorhpisms of the star graph state connected

to the fully-connected graph state, and are themselves

in an n+1 vertex star formation (see Fig. 1b), while C

orbits have only two members for all n (see Fig. 1c).

The proportion of all graphs which are asymmet-

ric tends towards zero as the number of vertices

tends towards inﬁnity

, (∼50% of unlabelled 9-

vertex graphs) However, the majority of the orbits we

compute are symmetric (75% of 9-qubit orbits have

a non-empty automorphism group), including orbits

containing thousands of graph states. A study of the

symmetries of the orbits, which is quantiﬁed by the

size of the orbit’s automorphism group, |aut|, is left

for future research.

Many of the computed parameters, such as Schmidt

measure, rank-width and automorphism group have

exponential complexity with system size. The rank-

width, while exponential in nature, can be computed

exactly

, while the Schmidt measure requires a non-

convex, nonlinear optimisation, and so is more chal-

lenging. We rely on previously computed

16,17

bounds

of the Schmidt measure, while computing the rank-

width using the software ‘SAGE’

. Though our

graph states are small, there is an exponential number

of entanglement classes as qubit number is increased.

Further, many of the graph metrics discussed, such

as graph colouring (chromatic number and chromatic

index) belong to complexity class NP. As such, they

become challenging to compute on dense orbits with

thousands of vertices. For this reason we computed

the chromatic index only for n ≤ 8 and n ≤ 7

for C

and L

orbits respectively. All graph colour-

ing computations were performed with the software

‘IGraph/M’

34,35

Due to their connectivity and scale, the majority

of orbits we explored are far too complex to view di-

rectly, as we did in Fig. 1. We can instead represent

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 8

Legend

Orbit

No. iso.

orbits

Entanglement class

1 9

20 46

147

10 9 8

7 6

44 6

16 10

44 10 16

Loops included

Entanglement class

147

9 20 46

147

Loops removed

No. 6 No. 10

No. 21 No. 22

No. 47 No. 48 No. 148

No. 149

No. 151

Figure 3: Isomorphism of local complementation orbits. a. The ﬁve most common orbits up to class 150, considering orbit

self-loops and not. b. Canonical, minimum-edge representatives of the orbits C

for i = 6, 10, 21, 22, 47, 48, 148, 149, 151,

each of which are isomorphic to one another (an order-six ring with three adjacent self-loops, see a). c. Isomorphism of orbits

. I

= 1 if orbit C

and C

are isomorphic. Entries are coloured by isomorphism. Regions of equal qubit number are

demarcated. d. Isomorphism of C

orbits with self-loops removed.

them with matrices. Fig. 2 shows the adjacency ma-

trices and distance matrices of class L

. We order the

matrix by isomorphism, edge count, and then lexico-

graphically by their lexicographically sorted edgelists.

Further, we demarcate regions of the plot which cor-

respond to graph states that have the same number

of edges and that are isomorphic to one another for

and L

respectively. In both cases, the adjacency

matrices show structure related to these regions.

There is variety and scale in the 587 C

orbits and

147 L

orbits we have computed which cannot be re-

produced in a single article. A curated selection of

orbits is displayed in Appendix Section 2, and the full

data set is available online.

4 Discussion

It is likely that future quantum information proces-

sors will have restricted two-qubit gate topology, due

to the qubit’s physical locations and proximity. Since

single-qubit operations are commonly faster or higher-

ﬁdelity than two-qubit gates, local complementation

may be used to improve a device’s speed or ﬁdelity

For a prescriptive method, the relationship between

orbits by nonlocal CZ gates must be known. A com-

plete map of this type would describe how all n-qubit

graph states are related to one another, and provide

a look up table for optimal transformations between

them. From here, the addition of vertex deletion

would give a complete map of graph states under

LC+LPM+CC operations (the vertex minor prob-

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 9

lem). A doubly-exponential problem, computation of

these maps appears to be infeasible for even modest

n. For small graphs, however, such a map may be

enlightening—the exploration is left for future work.

Knowledge of the orbits of local complementation

may also enable in quantum secret sharing and quan-

tum networks

7,36

. A graph state may be distributed

between separated parties, each of whom can perform

local operations and communicate with their neigh-

bours (according to the graph state structure). This

allows diﬀerent quantum protocols to be implemented

using a resource which has already been distributed

spatially. If the parties only have knowledge of their

own neighbourhood, and each party performs local

complementation at random, the shared state can be

scrambled. Numerically, we ﬁnd the stationary distri-

butions generated by random walks on the orbits ap-

pear to tend towards uniform as orbit size increases,

implying this ‘scrambling’ is eﬀective. This could be

formalised further by investigating mixing rates.

Local complementation allows the entanglement

of a resource state to be utilised diﬀerently in

measurement-based protocols

36–38

. That is, a re-

source state can be transformed into any other state

from its entanglement class, and used according to its

shape. Though practically this simply corresponds to

changing the protocol measurement bases, consider-

ing LC-equivalent graph states as a new state pre-

serves the standard language of measurement-based

protocols (measurement in the X-Y plane and Z di-

rections). Generally, local complementation has merit

in applications where qubits are in inequivalent spa-

tial locations—it illustrates the many functions of a

given entanglement.

In some quantum computer architectures, such as

those for linear optical quantum computing

, perco-

lated resource states are generated probabilistically.

These states have a randomly generated structure,

and hence some are more powerful than others, for

example they may have more favourable connectivity

for pathﬁnding

or loss tolerance

41,42

, which may be

optimised by local complementation. Though the en-

tanglement class of any useful resource state will be

too large to compute directly, it may be possible to

develop heuristics for using local complementation to

optimise local regions of the resource. These heuris-

tics may be explored and veriﬁed with the algorithm

of ref. 19. In this sense, optimisation via local com-

plementation can be seen as a step in the compilation

of a protocol or algorithm given a speciﬁc hardware.

Our library of orbits, including the code used to

generated the plots in this manuscript (Mathemat-

ica) is available online

and comprises 35 MB com-

pressed. We also provide

a new software tool,

‘graph state compass’, which computes the orbit of

any input graph state (python). Exploration up to

n = 12, where representative graph states of each or-

bit are known, is feasible if a compiled language and

parallelism are employed. Extending the database

further is a signiﬁcant computational challenge, as,

though an exact scaling is not known, the num-

ber of graph state entanglement classes grows super-

exponentially for n ≤ 12 qubits

Our exploration opens new lines of enquiry in

the study of graph states and their entanglement.

For example, what can be learned from the symme-

tries of an orbit? Is it possible to completely map

LC+LPM+CC operations beyond 12 qubits? What

new applications are possible utilising knowledge of

LC orbits?

Stabiliser state entanglement is—and will continue

to be—at the core of quantum information protocols.

The resource we provide gives a new handle to inves-

tigate the rich relationship between graph theory, sta-

biliser state entanglement, and applications of quan-

tum information.

References

[1] Raussendorf, R. Measurement-based quantum

computation with cluster states. International

Journal of Quantum Information 7, 1053–1203

(2009).

[2] Veldhorst, M., Eenink, H., Yang, C. & Dzurak,

A. Silicon cmos architecture for a spin-based

quantum computer. Nature Communications 8,

1766 (2017).

[3] Lekitsch, B. et al. Blueprint for a microwave

trapped ion quantum computer. Science Ad-

vances 3, e1601540 (2017).

[4] Alexander, R. N. et al. One-way quantum

computing with arbitrarily large time-frequency

continuous-variable cluster states from a single

optical parametric oscillator. Physical Review A

94, 032327 (2016).

[5] Asavanant, W. et al. Time-domain multiplexed

2-dimensional cluster state: Universal quan-

tum computing platform. Science366, 373-376

(2019).

[6] Barends, R. et al. Superconducting quantum cir-

cuits at the surface code threshold for fault tol-

erance. Nature 508, 500 (2014).

[7] Markham, D. & Sanders, B. C. Graph states for

quantum secret sharing. Physical Review A 78,

042309 (2008).

[8] Ji, Z., Chen, J., Wei, Z. & Ying, M. The

LU-LC conjecture is false. arXiv preprint

arXiv:0709.1266 (2007).

[9] Cabello, A., López-Tarrida, A. J., Moreno, P. &

Portillo, J. R. Entanglement in eight-qubit graph

states. Physics Letters A 373, 2219–2225 (2009).

[10] Anders, S. & Briegel, H. J. Fast simulation of

stabilizer circuits using a graph-state representa-

tion. Physical Review A 73, 022334 (2006).

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 10

[11] Hein, M., Eisert, J. & Briegel, H. J. Multiparty

entanglement in graph states. Physical Review A

69, 062311 (2004).

[12] Van den Nest, M., Dehaene, J. & De Moor, B.

Graphical description of the action of local Clif-

ford transformations on graph states. Physical

Review A 69, 022316 (2004).

[13] Hein, M. et al. Multiparty entanglement in graph

states. arXiv preprint quant-ph/0602096 (2006).

[14] Dahlberg, A. & Wehner, S. Transforming graph

states using single-qubit operations. Phil. Trans.

R. Soc. A 376, 20170325 (2018).

[15] Dahlberg, A., Helsen, J. & Wehner, S. The

complexity of the vertex-minor problem. arXiv

preprint arXiv:1906.05689 (2019).

[16] Danielsen, L. E. & Parker, M. G. On the classi-

ﬁcation of all self-dual additive codes over GF(4)

of length up to 12. Journal of Combinatorial The-

ory, Series A 113, 1351–1367 (2006).

[17] Cabello, A., Danielsen, L. E., Lopez-Tarrida,

A. J. & Portillo, J. R. Optimal preparation

of graph states. Physical Review A 83, 042314

(2011).

[18] Bouchet, A. An eﬃcient algorithm to recognize

locally equivalent graphs. Combinatorica 11,

315–329 (1991).

[19] Van den Nest, M., Dehaene, J. & De Moor, B.

Eﬃcient algorithm to recognize the local cliﬀord

equivalence of graph states. Physical Review A

70, 034302 (2004).

[20] Dahlberg, A., Helsen, J. & Wehner, S. How to

transform graph states using single-qubit opera-

tions: computational complexity and algorithms.

arXiv preprint arXiv:1805.05306 (2018).

[21] Van den Nest, M., Dür, W., Vidal, G. &

Briegel, H. Classical simulation versus universal-

ity in measurement-based quantum computation.

Physical Review A 75, 012337 (2007).

[22] Dahlberg, A., Helsen, J. & Wehner, S. Count-

ing single-qubit cliﬀord equivalent graph states is

#p-complete. arXiv preprint arXiv:1907.08024

(2019).

[23] Adcock, J. C., Morley-Short, S., Silverstone,

J. W. & Thompson, M. G. Hard limits on the

postselectability of optical graph states. Quan-

tum Science and Technology 4, 015010 (2019).

[24] Morley-Short, S., Graph state compass (2018).

[25] Data and code to accompany this manuscript:

(2020).

[26] Rokicki, T., Kociemba, H., Davidson, M. & De-

thridge, J. The diameter of the Rubik’s cube

group is twenty. SIAM Review 56, 645–670

(2014).

[27] McKay, B. D. & Piperno, A. Practical graph iso-

morphism II. Journal of Symbolic Computation

60, 94–112 (2014).

[28] Eisert, J. & Briegel, H. J. Schmidt measure as a

tool for quantifying multiparticle entanglement.

Physical Review A 64, 022306 (2001).

[29] Schlingemann, D. & Werner, R.F. Quantum

error-correcting codes associated with graphs.

Physical Review A 65, 012308 (2001).

[30] Dür, W., Aschauer, H. & Briegel, H.-J Multipar-

ticle entanglement puriﬁcation for graph states.

Physical review letters 91, 107903 (2003).

[31] Erdős, P. & Rényi, A. Asymmetric graphs. Acta

Mathematica Hungarica 14, 295–315 (1963).

[32] Oum, S.-I. Computing rank-width exactly. Infor-

mation Processing Letters 109, 745–748 (2009).

[33] SageMath, The Sage Mathematics Software Sys-

tem. (2020).

[34] Csárdi, G. & Nepusz, T., The igraph software

package for complex network research. InterJour-

nal Complex Systems, 1695, (2006).

[35] Horvát, S., IGraph/M. (2016).

[36] Hahn, F., Pappa, A. & Eisert, J. Quantum net-

work routing and local complementation. NPJ

Quantum Information 5.1, 5-7 (2019).

[37] Joo, J. & Feder, D. L. Edge local complemen-

tation for logical cluster states. New Journal of

Physics 13, 063025 (2011).

[38] Zwerger, M., Dür, W. & Briegel, H.

Measurement-based quantum repeaters. Physical

Review A 85, 062326 (2012).

[39] Gimeno-Segovia, M., Shadbolt, P., Browne, D. E.

& Rudolph, T. From three-photon Greenberger-

Horne-Zeilinger states to ballistic universal quan-

tum computation. Physical Review Letters 115,

020502 (2015).

[40] Morley-Short, S. et al. Physical-depth architec-

tural requirements for generating universal pho-

tonic cluster states. Quantum Science and Tech-

nology 3, 015005 (2017).

[41] Rudolph, T. Physical-depth architectural re-

quirements for generating universal photonic

cluster states. APL Photonics 2, 030901 (2017).

[42] Morley-Short, S., Gimeno-Segovia, M., Rudolph,

T. & Cable, H. Physical-depth architectural

requirements for generating universal photonic

cluster states. Quantum Science and Technology

(2018).

Acknowledgements

We would like to thank Caterina Vigliar, Sam Pallis-

ter, Will McCutcheon, and John G. Rarity for their

invaluable help. We would also like to thank the

reviewers of this paper for their thorough examina-

tion of our work and for giving us inspiration to im-

prove it. The computer programs ‘IGraph/M’ and

‘SAGE’ were vital for evaluating diﬃcult to compute

properties of our extensive library of graphs. This

work was supported by EPSRC Programme Grant

EP/L024020/1, the EPSRC Quantum Engineering

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 11

Centre for Doctoral Training EP/L015730/1, and the

ERC Starting Grant ERC-2014-STG 640079. JWS

acknowledges the generous support of the Leverhulme

Trust, through Leverhulme Early Career Fellowship

ECF-2018-276.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 12

Appendix

1 Deﬁnition of quantities

In this section, we introduce and deﬁne the graph-theoretical quantites and concepts used in this paper. Firstly,

a graph, G(V, E), is composed of a set of vertices V , and a set of edges E. Edges are two-element subsets of

V . In directed graphs, the elements of E are ordered. An example graph is the (undirected) fully-connected

three qubit graph, for which V = {1, 2, 3} and E = {(1, 2), (2, 3), (1, 3)}. The following is a glossary of terms

and deﬁnitions of properties of a graph G(V, E):

– Adjacent. Two vertices v

and v

are adjacent if there is a edge e which contains v

and v

as elements.

– Walk. A walk is an alternating sequence of edges and vertices, e.g. W = v

, v

. . . v

– Path. A path is a walk where no vertex is revisited

– Cycle. A cycle is a walk in which has one repeated vertex, which is the the ﬁrst and last vertices of the

walk.

– Tree. A tree is a graph which has no cycles. Trees necesarily have bounded rank-width, and can not be

resources for universal quantum computation

– Neighbourhood. The neighbourhood of a vertex, α, of a graph, G, is written N

(α). This is the set of

vertices with which the vertex α is adjacent to.

– Leaf. A leaf is a vertex of a graph which is adjacent to precisely one other vertex. Leaves can be removed

from graph states using a Z measurement without disturbing the rest of the graph state.

– self-loop. A self-loop is an edge from a vertex to itself: e = (v

, v

– Connected. A graph is connected if there is a path from every vertex to every other vertex. Connected

graph states are globally entangled (have genuine multipartite entanglement). Every orbit induced by local

complementation is connected.

– Connected. A graph, G(V, E) is connected if every vertex of the graph is adjacent to every other vertex:

∀i, j ∈ V, (i, j) ∈ E. Fully-connected graph states have GHZ-type entanglement.

– Subgraph. The graph G

= (V

, E

) is a subgraph of G(V, E) if V

⊂ V and ∀e

∈ E

, e

∈ E. For a graph

G(V, E), the neighbourhood of a vertex α, N

(α) is a subgraph of G

– Adjacency matrix. The adjacency matrix, A, of a graph, G, has elements a

= 1 if (i, j) ∈ E. Otherwise

= 0.

– Distance. The distance, d

between vertices i and j of a graph G(V, E) is the number of edges in the

shortest path between vertex i and vertex j. In an orbit, the distance between two graph states |ψ

i and

|ψ

i is the number of local complementations needed to transform |ψ

i into |ψ

– Distance matrix. The distance matrix, D, of a graph, G, has elements d

= d

and d

= 0. Otherwise

= 0.

– Diameter. The diameter of a graph G(V, E) is the largest distance d

of that graph. This is the maximum

number of local complementations needed to transform one graph state into another within an orbit.

– Chromatic index. The chromatic index is the minimum number of colours needed to colour the edges of a

graph, so that no two edges of the same colour are adjacent. This corresponds to the preparation complexity

of a graph state using only CZs in terms of number of time steps.

– Chromatic number. The chromatic number is the minimum number of colours needed to colour the vertices

of a graph, so that no two vertices of the same colour are adjacent. This corresponds to the preparation

complexity of a graph state using only CZs in terms of number of number of CZ gates.

– Planar graph. A graph is planar if it can be drawn on a two-dimensional plane without any of its edges

crossing.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 13

– Eulerian cycle. A Eulerian cycle is a cycle on a graph which traverses every edge of that graph precisely

once.

– Hamiltonian cycle. A Hamiltonain cycle is a cycle on a graph which visits every vertex of that graph

precisely once.

– Automorphism group. The automorphism group of a graph is the set of vertex permutations (relabellings)

that transform a graph into itself. This is the set of symmetries of the graph.

– Cut-rank

. For some A ⊂ V , the cut-rank of an adjacency matrix Γ with respect to A is:

cutrk(Γ)

= rank

(Γ[A, V \ A]), (5)

where Γ[A, V \ A] is the submatrix of Γ obtained by taking rows A and columns V \ A. Here, the rank is

taken over the ﬁnite ﬁeld of order 2 (addition modulo 2). Note that the cut-rank with respect to A of a

graph G is equal to the Schmidt-rank of the state G with respect to the bipartition (A, V \ A)

. This is

used in the deﬁnition of rank decomposition, and ﬁnally rank-width below.

– Rank decomposition

. A rank decomposition is a pair R = (T, µ) where T is a subcubic tree and µ is a

bijection µ : V (g) → l : l is a leaf of T. A subcubic tree is a tree with at least two vertices where each vertex

has degree less than or equal to 3. Deleting any edge e in T splits the tree into two connected components

and therefore induces a partition (A

, B

) of the leaves. The width of an edge e of the subcubic tree is

deﬁned as the cut-rank of the corresponding partition. Furthermore, the width of the rank-decomposition

is deﬁned as the maximum width over all edges, i.e:

width

= max

e∈E(T )

cutrk

−1

(T, e)

(G). (6)

Which is used in the deﬁnition of rank-width below.

– rank-width

. Utilising the above deﬁnitions, the rank-width is as follows:

rwd

= min

width

(G) = min

(G) min

T, µ

max

e∈E(T )

cutrk

−1

(T,e)

(G). (7)

Any graph state property which is expressible in so-called monadic second-order logic (a higher-order

logical system) can be computed in time O(f(rwd(G))|V (G)|

), where f is an exponential function

. This

includes the vertex minors problem, (deciding whether a graph can be transformed into another via LC

operations, local pauli measurement and classical communication).

Below, We reproduce the deﬁnitions of some of the quantum information quantities discussed in the main text:

– Schmidt measure

. The minimum number of terms in which a quantum state can be represented by, over

all local bases. We can write an n-partite system with parties A

, . . . , A

, each with a quantum system of

dimension d

, . . . , d

as the following:

|ψi =

|ψ

(1)

i ⊗ . . . ⊗ |ψ

(n)

i. (8)

Where |ψ

(j)

i are local states in the i

subspace of i = 1 . . . R. Let r be the minimum possible R across all

possible choices of local basis |ψ

(j)

i for each of the subspaces A

(minimising basis choice j). The Schmidt

measure is then log

(r).

– Schmidt-rank-width

14,21

. Starting with the graph state |ψi, we deﬁne Schmidt-rank-width. Letting

, B

)

be the number of nonzero Schmidt coeﬃcients of |ψi with respect to the bipartition (A

, B

) of

V , the qubits of |ψi

= min

T,µ

max

e∈E(T )

log

(χ

(|ψi)) (9)

For a subcubic tree T with edge e around which a bipartition is formed (as in the deﬁnition of rank-width).

The Schmidt-rank-width of the graph state |Gi is equal to the rank-width of a graph G.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 14

2 A gallery of graph state orbits

We map over 600 orbits, most of which are vastly too large and complex to display. In this Appendix, we exhibit

a curated selection of orbits to demonstrate the variety of form they display.

Appendix Figure 1: Orbit C

145

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 15

6 7 8 9 10 11

1 3 7 12 15

Graph state index

6 7 8 9 10 11

1 3 7 12 15

Number of edges in graph state

Graph state index

Appendix Figure 2: Local complementation orbit C

. a. The orbit C

. Here, graph state vertices which produce the same

output when locally complemented are the same colour (see Section 2.3). b. The adjacency matrix of C

. c. The distance

matrix of C

. Regions in the plot correspond to graph states which have the same number of edges.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 16

Appendix Figure 3: Orbit C

196

Appendix Figure 4: Orbit C

289

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 17

9 10

132

60 132

1, 2, 3, 4, 5, 6

1, 2, 3, 4, 5

{

Distance

9 10

132

60 132

Graph state index

Number of edges in graph state

Graph state index

Appendix Figure 5: Local complementation orbit 19. a. The orbit C

. b. The adjacency matrix of L

. c. The distance

matrix of L

. Regions in the plot correspond to graph states which are isomorphic. By separating regions corresponding to

non-isomorphic graphs, we see that the orbit is composed of just two non-isomorphic graph states. These have 60 and 72

isomorphisms respectively.

10 11 11 12 13 13 14 16

120

144

264

324

384

444

504

528

120 264 324 384 444 528

10 11 11 12 13 13 16

120

144

264

324

384

444

528

120 264 324 384 444 528

Graph state index

Number of edges in graph state

Appendix Figure 6: Local complementation orbit 45. a. The adjacency matrix of L

. b. The distance matrix of L

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 18

Appendix Figure 7: Orbit C

. The adjacencies and distances matrices for for C

and L

are shown on the next page.

Appendix Figure 8: The orbit C

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 19

8 9 9 10 10 11 12 13 14 22

104

127

142

12 24 36 48 60 78 89 104 127 142

8 9 10 11 12 13 14 15 17 18 22

1 3 6 9 11 16 19 21 24 26 28

8 9 9 10 10 11 12 13 14 22

104

127

142

12 24 36 48 60 78 89 104 142

127

8 9 10 11 12 13 14 16 17 18 22

1 3 6 9 11 16 19 21 24 26 28

Distance

Number of edges in graph state

Graph state index

Appendix Figure 9: Comparison of L and C orbits for enatanglement class 78. a. The adjacency matrix of C

. b. The

distance matrix of C

. c. The adjacency matrix of L

. d. The distance matrix of L

. Regions in c and d correspond to

graph states which have the same number of edges, while regions in c and d correspond to isomorphic graph states. Each

region of c and d corresponds to a single point in a and b.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 20

10 12 13 14 15 16 17 18 19 31

111

127

143

176

6 17 33 48 65 85 99 127

152

10 12 13 14 15 16 17 18 19 31

111

127

143

176

6 17 33 48 65 85 99 127 176

152

176

Distance

Graph state index

Number of edges in graph state

Appendix Figure 10: C

247

represented by its adjacency and distance matrices. a. The adjacency matrix. This matrix takes a

value Γ

= n where n is the index of the local complementation that links orbit vertices i and j. A diﬀerent colour is used

for each n. We demarcate regions of the plot which correspond to graph states with the same number of edges, and shade

these in the same pastel shade. b. The distance matrix of C

247

. This matrix takes a value Γ

= n where n is the number of

local complementations needed to transform graph state i into graph state j. The canonical representative graph state of the

class is shown underneath.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 21

3 Representive members of all graph state entanglement classes of n < 9 qubits

Appendix Figure 11: Canonical, minimal edge count representatives from each orbit up to and including 8 qubits. These are

canonically indexed as in ref. 17.

Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 22

Comments

Products

Project