Mapping graph state orbits under local complementation
Jeremy C. Adcock
1
, Sam Morley-Short
1
, Axel Dahlberg
2
, and Joshua W. Silverstone
1
1
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
2
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-Clifford 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
find 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-Clifford (LC) and every stabiliser state is local-
Clifford 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
8
, with a lower bound of 8 qubits
9
.
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
12
non-isomorphic graph states up
to 12 qubits classified into ∼1.3×10
6
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
15
. It is also known that count-
ing single-qubit LC-equivalent graph states is #p-
complete
22
. 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 effi-
ciently
23
. 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 different 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
24
‘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
25
.
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 defined
by a set of edges E between a set of vertices V . The
corresponding graph state is written:
|Gi =
Y
(i,j)∈E
CZ
ij
|+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 different constructions via nonlocal
Controlled-Z (CZ) gates
11,12
. Specifically, 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:
LC
α
(G(V, E)) :→ G(V, E
0
), (2)
where
E
0
= E ∪ K
N
G
(α)
− E ∩ K
N
G
(α)
= E∆K
N
G
(α)
. (3)
Here, K
N
G
(α)
is the set of edges of the complete graph
on the vertex set N
G
(α), the neighbourhood of α, and,
∆ is the symmetric difference. On graph states, the
following local unitary implements local complemen-
tation
11,12
:
U
LC
α
=
p
−iX
α
O
i∈N
G
(α)
p
iZ
i
(4)
Where U
LC
α
|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 defines graph (and therefore
stabiliser) entanglement classes, each with their own
orbit under local complementation. Though these
classes have been catalogued
17
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 different ways, generating up to n different 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 find 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
i
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 different 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 different faces of the cube by
90
◦
. 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
26
. Indeed,
a Rubik’s cube has ∼4.3×10
19
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 aficionados are known, call 26 ‘god’s number’.
In our analogy, the many states of the toy are our
graph states, and rotating the different faces of the
cube corresponds to local complementation of differ-
ent graph vertices. As evidenced by the ratio of its
cardinality to its diameter (∼10
18
), 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
f
2. neighbourhood
3. complement
4. output
a
1. input
{1,2,3,4,5,6}
{1,2,3,4,5}
b
c
d
e
Local complementation
6
1
2
3
4
5
6
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
3
(GHZ entanglement of four qubits). Here, L
i
and C
i
denote the orbit induced by local complementation
for entanglement class i. c. The orbit C
3
, where isomorphic graph states are considered equal. d. The orbit L
4
(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
4
. f. The orbit C
19
. Graph state vertices are labelled descending clockwise from noon
(see b). We use directed edges when drawing C
i
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
i
when isomor-
phic graphs are considered equal (unlabelled graph
states), and L
i
otherwise (labelled graph states). By
examining our dataset, we observe that C
i
contain
on average
1
/8 as many graph states as their partner
L
i
orbits for n < 9 qubits. This greatly reduces the
computational resources needed to map and analyse
them. We note that all C
i
are subgraphs of L
i
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
i
.
We find that there are typically more than one L
i
orbit (for fixed i), as most C
i
orbits do not con-
tain every isomorphism of it’s member graph states
(e.g. Fig. 1d)—the entanglement possessed is dis-
tributed in different ways between the parties. These
equivalent orbits are themselves isomorphic, and to-
gether the set of L
i
(for fixed i orbits) contains every
isomorphism of their component graph states. For ex-
ample, there are three equivalent orbits of L
4
(one of
which is shown in Fig. 1), each containing different
isomorphisms of their component graph states. Some
entanglement classes have only one L
i
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
|L
i
| = n+1 graph states (vertices) and are themselves
a ‘star’ graph (see Section 3 and Fig. 1b).
As in L
i
orbits, edges of a C
i
orbit are undirected.
However, as a guide to the eye we display directed
edges for C
i
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
th
entanglement class, L
i
containing a graph state |Gi, is a graph exploration
problem. Here, we use an exhaustive breadth-first 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
i
, which contains |L
i
|
graph states requires O(n|L
i
|
2
) 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
i
orbit). Linear
savings can be made by noting that local complemen-
tation is self inverse, and has no effect when applied
to a vertex of degree 1.
We use this method to explore the L
i
for n ≤ 8 and
C
i
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
C
i
makes heavy use of GraphIsomorphism, calling
it up to n|C
i
| times. However, since |C
i
| |L
i
|, and
our graph states are of modest size, exploring C
i
up
to 9 qubits required less computational time than ex-
ploring L
i
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
i
entanglement classes have not been studied in detail
before. Usually, most isomorphisms of a graph state
are not contained within a given C
i
orbit. Hence,
knowledge of C
i
, 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
efficiency of L
i
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
i
|
2
compar-
isons (and hence calls to GraphIsomorphism) need
be made (where ˜n = |E
i
|/|C
i
| is the mean number
of non-symmetric vertices on the graph states of C
i
.
In practice, the AutomorphismGroup is computed
in order to solve GraphIsomorphism
27
. Hence a
linear speedup is achieved. By examining our set of
computed orbits, we find 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
i
orbits
of 3-7 qubits and display them in Table 2. Definitions
of these quantities can be found in Appendix Section
1.
Accepted in Quantum 2020-06-29, click title to verify. Published under CC-BY 4.0. 4