Graph-theoretic Simplification of Quantum Circuits
with the ZX-calculus
Ross Duncan
1,2
, Aleks Kissinger
3
, Simon Perdrix
4
, and John van de Wetering
5
1
University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, UK
2
Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge CB2 1UB, UK
3
Department of Computer Science, University of Oxford
4
CNRS LORIA, Inria-MOCQUA, Université de Lorraine, F 54000 Nancy, France
5
Institute for Computing and Information Sciences, Radb oud University Nijmegen
May 27, 2020
We present a completely new approach to quantum circuit optimisation,
based on the ZX-calculus. We first interpret quantum circuits as ZX-diagrams,
which provide a flexible, lower-level language for describing quantum compu-
tations graphically. Then, using the rules of the ZX-calculus, we give a simpli-
fication strategy for ZX-diagrams based on the two graph transformations of
local complementation and pivoting and show that the resulting reduced dia-
gram can be transformed back into a quantum circuit. While little is known
about extracting circuits from arbitrary ZX-diagrams, we show that the under-
lying graph of our simplified ZX-diagram always has a graph-theoretic property
called generalised flow, which in turn yields a deterministic circuit extraction
procedure. For Clifford circuits, this extraction procedure yields a new normal
form that is both asymptotically optimal in size and gives a new, smaller up-
per bound on gate depth for nearest-neighbour architectures. For Clifford+T
and more general circuits, our technique enables us to to ‘see around’ gates
that obstruct the Clifford structure and produce smaller circuits than naïve
‘cut-and-resynthesise’ methods.
1 Introduction
Quantum circuits provide a de facto ‘assembly language’ for quantum computation, in
which computations are described as the composition of many simple unitary linear maps
called quantum gates. An important topic in the study of quantum circuits is quantum
circuit optimisation, whereby quantum circuits which realise a given computation are trans-
formed into new circuits involving fewer or simpler gates. While some strides have already
been made in this area, the field is still relatively undeveloped. Most approaches to quan-
tum circuit optimisation are based on only a handful of techniques: gate substitutions,
computation of small (pseudo-)normal forms for special families of circuits [1, 29, 32],
optimisation of phase polynomials [3, 22], or some combination thereof [2, 35].
Ross Duncan: ross.duncan@strath.ac.uk
Aleks Kissinger: aleks.kissinger@cs.ox.ac.uk
Simon Perdrix: simon.perdrix@loria.fr
John van de Wetering: john@vdwetering.name
Accepted in Quantum 2020-04-27, click title to verify 1
arXiv:1902.03178v6 [quant-ph] 26 May 2020
This paper lays a theoretical foundation for a completely new quantum circuit optimi-
sation technique based on the ZX-calculus [11]. A key point of departure of our technique
is that we break the rigid structure of quantum circuits and perform reductions on a lower-
level, string diagram-based representation of a quantum circuit called a ZX-diagram. These
diagrams are more flexible than circuits, in that they can be deformed arbitrarily, and are
subject to a rich equational theory: the ZX-calculus. The core rules of the ZX-calculus
give a sound and complete [4] theory for Clifford circuits, a well-known class of circuits
that can be efficiently classically simulated. More surprisingly, it was shown in 2018 that
modest extensions to the ZX-calculus suffice to give completeness for families of circuits
that are approximately universal [24, 25] and exactly universal [9, 20, 23, 39] for quantum
computation.
Since ZX-diagrams provide a more flexible representation of a quantum computation
than a circuit, we can derive simplifications of ZX-diagrams that have no quantum circuit
analogue. However, this added flexibility comes at a price: while any quantum circuit can
be interpreted as a ZX-diagram by decomposing gates into smaller pieces, the converse is
not true. For a generic ZX-diagram corresponding to a unitary, there is no known general-
purpose procedure for efficiently recovering a quantum circuit. Hence, an important part
of our optimisation procedure is keeping enough information about the quantum circuit
structure to get a circuit back at the end. Schematically:
ZX-diagrams
Quantum circuits
simplification
circuit extraction
Until recently, this extraction step was poorly understood, and the only techniques
for doing circuit-to-circuit translation with the ZX-calculus did so without departing from
the overall structure of the original quantum circuit [19], avoiding the extraction problem
altogether. In this paper we adopt a more ambitious approach. First, building on prior
work of two of the authors [1618], we use the rules of the ZX-calculus to derive a sound,
terminating simplification procedure for ZX-diagrams. The key simplification steps involve
the graph-theoretic transformations of local complementation and pivoting [6, 30], which
allow certain generators to be deleted from ZX-diagrams one-by-one or in pairs, respec-
tively. When applied to Clifford circuits, the diagram resulting from the simplification
procedure is represented in the form of a graph-state with local Cliffords (GS-LC) [21], a
pseudo-normal form for representing Clifford circuits whose size is at most quadratic in
the number of qubits. Hence, one side effect of our simplification procedure is that it gives
a simple, graph-theoretic alternative to the normalisation of a ZX-diagram to GS-LC form
proposed by Backens [4]. For non-Clifford circuits, the simplified ZX-diagram represents
a ‘skeleton’ of the circuit we started with, consisting only of generators arising from non-
Clifford phase gates and their nearest neighbours. Although this is no longer a canonical
form, it can still be significantly smaller than the input circuit, especially when there is
a relatively low proportion of non-Clifford gates. We then show that, even though this
simplification breaks the circuit structure, it preserves a graph-theoretic invariant called
focused gFlow [8, 34], from which we can derive an efficient circuit extraction strategy. We
demonstrate the full simplify-and-extract procedure by means of a running example, which
Accepted in Quantum 2020-04-27, click title to verify 2
is also available online as a Jupyter notebook.
1
In the case of Clifford circuits, this procedure will produce circuits comparable in size
to those described by standard techniques [1, 38]. In the non-Clifford case, this can already
find more simplifications than naïvely ‘cutting’ the circuit and simplifying purely-Clifford
sections. More importantly, this paper establishes a new theoretical framework upon which
to build powerful new optimisation techniques, e.g. for important tasks such as T-count
reduction. Indeed an ancilla-free T-count reduction technique based on the framework
of this paper has recently been introduced in Ref. [27] and implemented in a tool called
PyZX [28]. At the time of publication, this new technique matched or out-performed the
state of the art on 72% of the benchmark circuits tested, in some cases decreasing the
T-count by as much as 50%.
2
The paper is organised as follows. After giving a brief introduction to the ZX-calculus
in Section 2, we will introduce graph-like ZX-diagrams in Section 3. This mild restriction
to the family of all ZX-diagrams will enable us to speak more readily about graph-theoretic
properties of the diagram, like the existence of a focused gFlow. In Section 4 we will show
that both local complementation and pivoting preserve focused gFlow. Then in Section 5
we will derive a simplification routine using these graph-theoretic notions. In Section 6
we study the properties of Clifford diagrams resulting from this simplification routine,
and show how these can be transformed into circuits. Then in Section 7 we show how
general diagrams produced by this routine can be extracted into a circuit, and give some
experimental evidence that this method performs better than only optimizing Clifford
sub-circuits. Finally, in Section 8 we conclude and discuss future work.
Note: The results in Proposition 6.1 concerning Clifford gate count and depth were added
to a version of this paper submitted for peer review in October 2019. Prior to us making
this version public, Bravyi and Maslov independently reported similar results in Ref. [7].
2 The ZX-calculus and quantum circuits
We will provide a brief overview of the ZX-calculus. For an in-depth reference see Ref. [10].
The ZX-calculus is a diagrammatic language similar to the familiar quantum circuit
notation. A ZX-diagram consists of wires and spiders. Wires entering the diagram from
the left are inputs; wires exiting to the right are outputs. Given two diagrams we can
compose them by joining the outputs of the first to the inputs of the second, or form their
tensor product by simply stacking the two diagrams.
Spiders are linear maps which can have any number of input or output wires. There
are two varieties: Z spiders depicted as green dots and X spiders depicted as red dots.
3
Written explicitly in Dirac notation, these linear maps are:
α
...
...
:= |0...0ih0...0| + e
|1...1ih1...1|
α
...
...
:= |+...+ih+...+| + e
|−...−ih−...−|
1
nbviewer.jupyter.org/github/Quantomatic/pyzx/blob/906f6db3/demos/example-gtsimp.ipynb
Note this link is read-only. To run the notebook interactively, download the file and open it in Jupyter
(with PyZX installed). The simplest way to do this is to clone or download the PyZX repostory from:
github.com/quantomatic/pyzx and find the notebook in demos.
2
The ‘PyZX-only’ T-counts from [27] were subsequently matched by parallel, independent work of
Zhang and Chen [40].
3
If you are reading this document in monochrome or otherwise have difficulty distinguishing green and
red, Z spiders will appear lightly-shaded and X spiders darkly-shaded.
Accepted in Quantum 2020-04-27, click title to verify 3
Therefore a ZX-diagram with m input wires and n output wires represents a linear map
(C
2
)
m
(C
2
)
n
built from spiders (and permutations of qubits) by composition and
tensor product of linear maps. As a special case, diagrams with no inputs and n outputs
represent vectors in (C
2
)
n
, i.e. (unnormalised) n-qubit states.
Example 2.1. We can immediately write down some simple state preparations and uni-
taries in the ZX-calculus:
= |0i + |1i |+i = |+i + |−i |0i
α
= |0ih0| + e
|1ih1| = Z
α
α
= |+ih+| + e
|−ih−| = X
α
In particular we have the Pauli matrices:
π
= Z
π
= X
It will be convenient to introduce a symbol a yellow square for the Hadamard gate.
This is defined by the equation:
=
π
2
π
2
π
2
(1)
We will often use an alternative notation to simplify the diagrams, and replace a Hadamard
between two spiders by a blue dashed edge, as illustrated below.
:=
...
...
...
...
Both the blue edge notation and the Hadamard box can always be translated back into
spiders when necessary. We will refer to the blue edge as a Hadamard edge.
Two diagrams are considered equal when one can be deformed to the other by moving
the vertices around in the plane, bending, unbending, crossing, and uncrossing wires, so
long as the connectivity and the order of the inputs and outputs is maintained. Further-
more, there is an additional set of equations that we call the rules of the ZX-calculus; these
are shown in Figure 1.
Remark 2.2. We neglect (non-zero) scalar factors in the rules in Figure 1. That is, if
we are able to prove two ZX-diagrams are equal using the rules of Figure 1, then their
associated matrices satisfy A = zB for z C\{0}. It is possible to give a presentation
of the ZX-calculus that accounts for scalar factors (see e.g. [5]), but for our purposes
it will not be necessary. This is because the inputs and outputs of our simplification
procedure are quantum circuits, which are unitary by construction. If A and B are unitary,
A = zB = |z| = 1, so neglecting scalars will (at worst) produce and output that differs
from the input by a global phase.
Let us derive two additional rules, known as the antipode rule and the π-copy rule.
Lemma 2.3. The antipode rule,
=
(a)
is derivable in the ZX-calculus.
Proof. To derive the (a) rule we take advantage of the freedom to deform the diagram as
shown below.
Accepted in Quantum 2020-04-27, click title to verify 4
β
...
...
α
...
...
=
...
...
...
α+β
(f)
α
=
π
π α
...
...
π
(π)
...
α
=
...
(c)
...
=
...
(h)
(i1)
=
=
(i2)
(b)
=
...
α α
...
Figure 1: A convenient presentation for the ZX-calculus. These rules hold for all α, β [0, 2π), and
due to (h) and (i2) all rules also hold with the colours interchanged. Note ... should be read as ‘0 or
more’, hence the spiders on the LHS of (f ) are connected by one or more wires.
==
=
=
= =
(i1) (f)
(b) (c)
The final equation is simply dropping the scalar.
Lemma 2.4. The π-copy rule,
π
=
...
(πc)
π α
π
...
π
is derivable in the ZX-calculus.
Proof. To derive the (πc) rule we use the (f ) rule first to split the π-labelled vertex, and
the (π) and (c) rules do the bulk of the work as shown below:
π
=
...
π α
π
...
π
π
...
...
π
π
(π)
α
α
π
=
(f)
π
π
π
...
(f)
=
(c)
=
Remark 2.5. The ZX-calculus is universal in the sense that any linear map can be
expressed as a ZX-diagram. Furthermore, when restricted to Clifford ZX-diagrams, i.e.
diagrams whose phases are all multiples of π/2, the version we present in Figure 1 is
complete. That is, for any two Clifford ZX-diagrams that describe the same linear map,
there exists a series of rewrites transforming one into the other. Recent extensions to
the calculus have been introduced which are complete for the larger Clifford+T family of
ZX-diagrams [24], where phases are multiples of π/4, and for all ZX-diagrams [20, 23, 39].
Quantum circuits can be translated into ZX-diagrams in a straightforward manner. We
will take as our starting point circuits constructed from the following universal set of gates:
CNOT :=
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
Z
α
:=
1 0
0 e
!
H :=
1
2
1 1
1 1
!
Accepted in Quantum 2020-04-27, click title to verify 5
We fix this gate set because they admit a convenient representation in terms of spiders:
CNOT = Z
α
=
α
H = (2)
For the CNOT gate, the green spider is the first (i.e. control) qubit and the red spider is
the second (i.e. target) qubit. Other common gates can easily be expressed in terms of
these gates. In particular, S := Z
π
2
, T := Z
π
4
and:
X
α
=
αα
=
CZ =
= =
Remark 2.6. Note that the directions of the wires in the depictions of the CNOT and
CZ gates are irrelevant, hence we can draw them vertically without ambiguity. This
undirectedness of wires is a general property of ZX-diagrams, and from hence forth we will
ignore wire directions without further comment. We will also freely draw wires entering
or exiting the diagram from arbitrary directions if the interpretation (i.e. as an input or
an output) is either irrelevant or clear from context.
For our purposes, we will define quantum circuits as a special case of ZX-diagrams.
Definition 2.7. A circuit is a ZX-diagram generated by compositions and tensor products
of the ZX-diagrams in equation (2).
Important subclasses of circuits are Clifford circuits, sometimes called stabiliser circuits,
which are obtained from compositions of only CNOT, H, and S gates. They are efficiently
classically simulable, thanks to the Gottesman-Knill theorem [1]. A unitary is local Clifford
if it arises from a single-qubit Clifford circuit, i.e. a composition of H and S gates. The
addition of T gates yields Clifford+T circuits, which are capable of approximating any
n-qubit unitary to arbitrary precision, whereas the inclusion of Z
α
gates for all α enables
one to construct any unitary exactly [37].
3 Graph-like ZX-diagrams
Before starting our simplification procedure, we transform ZX-diagrams into the following,
convenient form.
Definition 3.1. A ZX-diagram is graph-like when:
1. All spiders are Z-spiders.
2. Z-spiders are only connected via Hadamard edges.
3. There are no parallel Hadamard edges or self-loops.
4. Every input or output is connected to a Z-spider and every Z-spider is connected to
at most one input or output.
A ZX-diagram is called a graph state if it is graph-like, every spider is connected to
an output, and there are no non-zero phases. This corresponds to the standard notion of
graph state from the literature [21]. Hence, graph-like ZX-diagrams are a generalisation
of graph states to maps where we allow arbitrary phases and some interior spiders, i.e.
spiders not connected to an input or output.
Lemma 3.2. Every ZX-diagram is equal to a graph-like ZX-diagram.
Accepted in Quantum 2020-04-27, click title to verify 6
Proof. Starting with an arbitrary ZX-diagram, we apply (h) to turn all red spiders into
green spiders surrounded by Hadamard gates. We then remove excess Hadamards via
(i2). Any non-Hadamard edge is then removed by fusing the adjacent spiders with (f ).
Any parallel Hadamard edges or self-loops can be removed via the following 3 rules:
α
β
... ...
=
α
β
... ...
α
...
=
...
α α
...
=
...
α + π
(3)
The first one of these follows by using (a):
α
β
... ...
=
α
...
β
...
(h)
=
(f)
α
... ...
β
=
(a)
α
... ...
β
=
(f)
α
... ...
β
(h)
The second one follows by applying (i1) from right to left and then using (f ). For the
last one we do:
α
...
π
2
π
2
α
...
π
2
=
π
2
...
α + π
=
...
α + π
=
(f)
Here, the first step is simply the definition of the Hadamard box, and in the last step we
use the antipode rule (a) and implicitly drop the scalar X-spider that we are left with.
At this point, the first 3 conditions are satisfied. To satisfy condition 4, we must
deal with two special cases: (a) inputs/outputs not connected to any Z-spider, and (b)
multiple inputs/outputs connected to the same Z-spider. For case (a), there are only two
possibilities left: either an input and an output are directly connected (i.e. a ‘bare wire’),
or they are connected to a Hadamard gate. These situations can both be removed by
right-to-left applications of (i1) and (i2) as follows:
= =
......
=
......
For case (b), we can again use (i1) and (i2) to introduce ‘dummy’ spiders until each
input/output is connected to a single spider:
==
α
...
α
...
α
...
α
...
Once this is done, the resulting ZX-diagram satisfies conditions 1-4.
A useful feature of a graph-like ZX-diagram is that much of its structure is captured
by its underlying open graph.
Definition 3.3. An open graph is a triple (G, I, O) where G = (V, E) is an undirected
graph, and I V is a set of inputs and O V a set of outputs. For a ZX-diagram D, the
underlying open graph G(D) is the open graph whose vertices are the spiders of D, whose
edges correspond to Hadamard edges, and whose sets I and O are the subsets of spiders
connected to the inputs and outputs of D, respectively.
See Figure 2 for an example of converting a circuit into a graph-like diagram with
Lemma 3.2 and how the associated underlying graph is found.
A graph-like ZX-diagram can be seen as an open graph with an assignment of angles
to each of its vertices. Note that, because of Definition 3.1, the sets I and O in G(D) will
Accepted in Quantum 2020-04-27, click title to verify 7
α
γ
I 3
I 3
I 3
O
O
O
I 3 O
=
γ
α
=
γ
α
(f) (i1)
α
γ
=
(h)
=
(i2)
α
γ
Figure 2: A circuit, which is transformed into an equivalent graph-like ZX-diagram, and its underlying
open graph.
always be disjoint. When discussing open graphs we will use the notation I := V \ I and
O := V \ O for the non-inputs and non-outputs respectively. The set of neighbours of a
vertex v V will be denoted by N (v).
We are now ready to define a graph-theoretic condition that will be instrumental in
our circuit extraction procedure.
Definition 3.4. [34] Given an open graph G, a focused gFlow (g, ) on G consists of a
function g : O 2
I
and a partial order on the vertices V of G such that for all u O,
1. Odd
G
(g(u)) O = {u}
2. v g(u), u v
where 2
I
is the powerset of I and Odd
G
(A) := {v V (G) | |N (v) A| 1 mod 2} is the
odd neighbourhood of A.
Example 3.5. While not strictly necessary for the following, we briefly give some intuition
for the conditions in Definition 3.4. They can be understood in a more operational way
with the following game. Suppose we consider an open graph G whose vertices are labelled
with 0’s and 1’s, where a 1 indicates the presence of an error. Define an operation flip
v
,
which flips all of the bits on the neighbours of a given vertex v. Our goal is to propagate
all of the errors present in G to the outputs using only applications of the operation flip
v
.
For example:
I 3
I 3 O
0
0 01
v
O
1
w
flip
v
I 3
I 3 O
1
0 10
v
O
1
w
flip
w
I 3
I 3 O
0
0 10
v
O
1
w
(4)
For some open graphs and configurations of errors, this task might be impossible. For
example, there is no solution for the following graph:
I 3
I 3
O
0
0 0
1
Accepted in Quantum 2020-04-27, click title to verify 8
However, we can always succeed if we are given the following data: an ordering of
vertices which give a direction of ‘time’ going from inputs to outputs, and, for each vertex,
a correction set g(v) of vertices in the future of v (w.r.t. ) such that applying flip
w
for
all w g(v) flips the bit on v without affecting any other bits, except for those labelling
outputs and g(v) itself. By repeatedly finding the minimal vertex v (w.r.t. ) with an
error and applying flip
w
to all w g(v), the procedure will eventually propagate all of
the 1’s to the outputs of G.
Remark 3.6. Generalised flow techniques were introduced in the context of measurement-
based quantum computing [13, 14]. Focused gFlow is a special case of the standard notion
of gFlow [8], where the latter allows other vertices v in the set Odd
G
(g(u)) O, provided
they are in the future of u (i.e. u v). However, as a property of graphs, the two notions
are equivalent: an open graph has a gFlow if and only if it has a focused gFlow. We will
rely on this equivalence in Appendix B.1 to prove the following Lemma.
Lemma 3.7. If D is a graph-like ZX-diagram obtained from a circuit by the procedure
of Lemma 3.2, then G(D) admits a focused gFlow.
Proof. See Appendix B.1.
4 Local complementation and pivoting
Local complementation is a graph transformation introduced by Kotzig [30].
Definition 4.1. Let G be a graph and let u be a vertex of G. The local complementation
of G according to u, written as G u, is a graph which has the same vertices as G, but all
the neighbours v, w of u are connected in G u if and only if they are not connected in G.
All other edges are unchanged.
Example 4.2. Local complementations according to the vertices a and b are given by:
G
a
b
d
c
G a
a
b
d
c
(G a) b
a
b
d
c
A related graph-theoretic operation is pivoting, which takes place at a pair of adjacent
vertices.
Definition 4.3. Let G be a graph, and let u and v be a pair of connected vertices in G.
The pivot of G along the edge uv is the graph G uv := G u v u.
On a graph, pivoting consists in exchanging u and v, and complementing the edges
between three particular subsets of the vertices: the common neighbourhood of u and v
(i.e. N
G
(u) N
G
(v)), the exclusive neighbourhood of u (i.e. N
G
(u) \ (N
G
(v) {v})), and
exclusive neighbourhood of v (i.e. N
G
(v) \ (N
G
(u) {u})):
G
A
B C
vu
G uv
A
B C
v u
For a more concrete illustration of pivoting see Example 4.4 or Equation (6) below.
Accepted in Quantum 2020-04-27, click title to verify 9
Example 4.4. In the graph G below, {a, b} is in the neighbourhood of u alone, {d} is in
the neighbourhood of v alone, and {c} is in the the neighbourhood of both. To perform
the pivot along uv, we complement the edges connecting {a, b} to {d}, {d} to {c} and
{a, b} to {c}. We then swap u and v:
G
u v
d
b
c
a
e
G uv
v u
d
b
c
a
e
Our primary interest in local complementation and pivoting is that each corresponds
to a transformation of ZX-diagrams. In the special case where a ZX-diagram D is a graph-
state, it is possible to obtain a diagram D
0
where G(D
0
) = G(D) u by applying an X
π/2
gate on the spider corresponding to u and Z
π/2
on all of the spiders in N(v):
-
π
2
π
2
π
2
π
2
N(u)
u
=
... ...
(5)
This is a well-known property of graph states, and a derivation using the rules of the
ZX-calculus was given in Ref. [16]. Similarly, it was shown in Ref. [18] that a pivot
G(D
0
) = G(D) uv can be introduced by applying Hadamard gates on u and v and Z
π
gates on N(u) N(v):
......
ππ
...
... ...
......
...
u v
N(u)\(N(v) {v}) N(v)\(N(u) {u})
N(u) N(v)
=
(6)
Note that the swap on the RHS comes from the vertices u and v being interchanged by
the pivot.
The following theorem will be crucial for our extraction routine. It shows that the
existence of a focused gFlow is preserved by local complementation (resp. pivoting) followed
by the deletion of the vertex (resp. the pair of vertices) on which the transformation is
applied:
Theorem 4.5. Let (G, I, O) be an open graph that admits a focused gFlow, then (G
0
, I, O)
also admits a gFlow in the following two cases:
1. for u / I O, setting G
0
:= (G u)\{u}
2. for adjacent u, v / I O, setting G
0
:= (G uv)\{u, v}
where G \W is the graph obtained by deleting the vertices in W and any incident edges.
Proof. The two cases are proved in Appendix B.2, Lemmas B.5 and B.8 respectively.
Accepted in Quantum 2020-04-27, click title to verify 10
5 A simplification strategy for circuits
We now have all the necessary machinery to introduce our simplification routine. The
general idea is to use local complementation and pivoting based rewrite rules to remove as
many interior spiders as possible. A spider is called interior when it is not connected to
an input or an output, otherwise it is called a boundary spider.
Definition 5.1. We call a spider Pauli if its phase is a multiple of π, and Clifford if its
phase is a multiple of
π
2
. If the phase of a Clifford spider is an odd multiple of
π
2
(and
hence non-Pauli), we call this a proper Clifford spider.
The graph-like ZX-diagram resulting from the translation of a Clifford circuit contains only
Clifford spiders, since the only time the phase changes on a spider is during a spider-fusion
step, in which case the phases are added together.
We will show that our procedure is able to eliminate all interior proper Clifford spiders
and all Pauli spiders adjacent either to a boundary spider or any interior Pauli spider. In
particular, for Clifford circuits, we will obtain a pseudo-normal form which contains no
interior spiders (cf. Section 7).
The main rewrite rules we use are based on local complementation and pivoting. The
first one allows us to remove any interior proper Clifford spider while the second one
removes any two connected interior Pauli spiders.
Lemma 5.2. The following rule holds in the ZX-calculus:
±
π
2
α
1
α
n
...
... ...
=
...
α
1
π
2
...
α
n
π
2
α
2
...
α
n1
...
α
2
π
2
...
α
n1
π
2
...
...
(7)
where the RHS is obtained from the LHS by performing a local complementation at the
marked vertex, removing it, and updating the phases as shown.
Lemma 5.3. The following rule holds in the ZX-calculus:
jπ
α
1
=
α
n
β
1
β
n
γ
1
γ
n
...
...
...
α
n
+ kπ
β
n
+ (j + k + 1)π
...
β
1
+ (j + k + 1)π
γ
1
+ jπ
α
1
+ kπ
...
...
γ
n
+ jπ
...
...
...
...
...
...
...
...
...
...
...
...
(8)
where the RHS is obtained from the LHS by performing a pivot at the marked vertices,
removing them, and updating the phases as shown.
The proofs of these lemmas can be found in Appendix B.3.
We can additionally apply (8) to remove an interior Pauli spider that is adjacent to a
boundary spider. To do this, we first turn the boundary spider into a (phaseless) interior
spider via the following transformation, which follows from the rules (f ), (i1), and (i2):
jπ
α
1
=
α
n
α
...
...... ...
u
jπ
α
1
α
n
...
...... ...
α
v w
u
v
(9)
After this transformation, we can perform (8) on the two spiders labelled {u, v} to remove
them. For our purposes, we can then treat w as a boundary spider, and save the single-
qubit unitaries to the right of w separately.
Accepted in Quantum 2020-04-27, click title to verify 11
Theorem 5.4. There exists a terminating procedure which turns any graph-like ZX-
diagram D into a graph-like ZX-diagram D
0
(up to single-qubit unitaries on inputs/outputs)
which does not contain
1. interior proper Clifford spiders,
2. adjacent pairs of interior Pauli spiders,
3. and interior Pauli spiders adjacent to a boundary spider.
In particular, if D only contains Clifford spiders, then D
0
contains no interior spiders.
Proof. Starting with a graph-like ZX-diagram, mark every interior Clifford spider for sim-
plification. Then repeat the steps below (followed by (3) to remove parallel edges), until
no rule matches:
Apply (7) to remove a marked proper Clifford spider.
Apply (8) to remove an adjacent pair of marked Pauli spiders.
Apply (9) to a boundary adjacent to a marked Pauli spider and immediately ap-
ply (8).
All 3 rules remove at least 1 marked node, so the procedure terminates. Since none of
these rules will introduce non-Clifford spiders, if D contains only Clifford spiders so too
does D
0
. Since the only possibilities for interior spiders in D
0
are covered by cases 1-3, D
0
contains no interior spiders.
Corollary 5.5. For D and D
0
the ZX-diagrams from Theorem 5.4, if G(D) admits a
focused gFlow, then so too does G(D
0
).
Proof. It was shown in Theorem 4.5 that the transformations (7) and (8) preserve focused
gFlow. The transformation (9) acts as an input/output extension on G(D). That is, for
X {I, O}, v X, it adds a new vertex w and an edge vw, and sets X
0
:= (X\{v}){w}.
It was shown in [34] that these transformations preserve focused gFlow.
This simplification procedure is very effective, especially for circuits with few non-
Clifford gates. We can see this by considering a randomly-generated circuit, where 2%
of the gates are non-Clifford:
π
2
π
2
3π
2
π
2
5π
4
π
2
π
2
π
2
π
2
3π
2
π
2
3π
2
π
4
π
2
3π
2
3π
2
π
2
3π
2
3π
2
3π
2
π
2
π
2
3π
2
3π
2
3π
2
3π
2
3π
4
π
2
3π
2
π
2
π
2
π
2
π
2
π
2
π
2
3π
2
π
2
π
2
3π
2
3π
2
3π
2
3π
2
π
2
π
2
π
2
π
2
π
2
3π
2
3π
2
π
2
3π
2
3π
4
3π
2
π
2
π
2
π
2
π
2
π
2
π
2
π
2
π
2
π
2
3π
2
3π
2
π
2
π
2
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Accepted in Quantum 2020-04-27, click title to verify 12
This circuit has 195 gates, with 4 non-Clifford gates. If we apply the simplification proce-
dure, we obtain a small ‘skeleton’ of the circuit, containing 12 spiders:
π
2
π
4
5π
4
π
2
π
4
π
4
π
π
(10)
Note the non-Clifford phases now clearly appear on the 4 interior spiders. In general, the
interior spiders will either be non-Clifford or be Pauli with only non-Clifford neighbours.
Any other possibilities will be removed.
Remark 5.6. Let n denote the amount of spiders in the diagram. As each step of Theo-
rem 5.4 removes a spider, the amount of steps is upper-bounded by n. Each step toggles
the connectivity of some subset of the vertices in the graph, and hence the elementary
graph operations per step is upper-bounded by n
2
. We see then that the full simplifica-
tion procedure has worst-case complexity O(n
3
). However, since the graphs coming from
circuits are far from being fully connected, we see a much better scaling in practice, with
the complexity lying between O(n) and O(n
2
) (see Ref. [28] for more details). Our imple-
mentation simplifies the example above in 25ms on a laptop computer, scaling up to a
few minutes for circuits with 10-20K gates.
6 Circuit extraction of Clifford circuits
As described in the previous section, when a Clifford circuit is fed into our simplification
routine, no interior spiders will be left, and hence the diagram is in GS-LC form (graph-
state with local Cliffords). It is straightforward to extract a Clifford circuit from a GS-LC
form. First, we unfuse spiders to create local Cliffords and CZ gates on the inputs and
outputs, then apply the (h) rule to the spiders on the right side of the resulting bipartite
graph:
LC
LC
LC
...
LC
LC
...
LC
···
=
LC
LC
...
LC
LC LC
...
LC
···
P
(11)
The part of the diagram marked P now has the form of a classical parity circuit. That is,
it is a permutation of computational basis states where the output basis is given in terms
of parities of the inputs, e.g. |x
1
, x
2
, x
3
, x
4
i 7→ |x
1
x
2
, x
1
x
3
, x
4
, x
3
i. Such a unitary
can always be realised via CNOT gates, using standard techniques based on Gaussian
elimination over F
2
(see e.g. [32]). Hence, we obtain a Clifford circuit with 6 layers of
gates:
Local Clifford + CZ + CNOT + H + CZ + Local Clifford
Using a strategy based on [4, Thm. 13], we can apply the local complementation rule (5)
to the LHS of (11) to reduce all of the local Cliffords on the inputs to the set {S
n
, H, ZH}
and the outputs to the set {S
n
, H, HZ} (cf. Appendix B.4). Hence, we can further refine
the decomposition above into 8 layers:
H + S + CZ + CNOT + H + CZ + S + H (12)
Accepted in Quantum 2020-04-27, click title to verify 13
where the S layer means powers of S gates (including S
2
= Z).
There are a variety of pseudo-normal forms for Clifford circuits in the literature, starting
with the 11-layer form given by Aaronson and Gottesman [1] and the courser-grained 5-
layer form of Dehaene and De Moore [15], which led to improved versions by Maslov
and Roetteler [33] and van den Nest [38], respectively. While there are some superficial
similarities between our normal forms and these earlier ones, there is at least one notable
difference. All of the forms mentioned above require at least two distinct CNOT layers, but
(with the exception of Ref. [1]) require just a single later of Hadamard gates. On the other
hand, our normal form has just a single CNOT layer, at the cost of multiple Hadamard
layers. We will now see that this trade-off has some nice consequences.
In Ref. [33] the authors argued that since there are 2
2n
2
+O(n)
Clifford unitaries on n
qubits, one needs at least 2n
2
+ O(n) Boolean degrees of freedom to specify all the n qubit
Clifford unitaries, and furthermore they found a normal form which has the same number
of degrees of freedom and hence is asymptotically optimal in this sense. They also study
the problem of finding a Clifford pseudo-normal form that has the lowest 2-qubit gate depth
when restricted to a linear nearest neighbour architecture and find a different normal form
that is bounded by a 14n 4 2-qubit gate depth. The decomposition (12) improves on this
bound, while at the same time also satisfying the 2n
2
+ O(n) asymptotically optimal gate
count.
Proposition 6.1. The GS-LC pseudo-normal form on n qubits has an asymptotically
optimal number of degrees of freedom 2n
2
+ O(n). Furthermore, any Clifford unitary in
this normal form can be mapped to a linear nearest neighbour architecture with a 2-qubit
gate depth of 9n 2.
Proof. The argument follows closely the one given in Ref. [33], but for a different normal
form. Our normal form has 5 layers of single qubit Clifford gates. The Hadamard layers
each add at most n gates, while the Z-phase layers add at most 3n gates, hence these
layers only add a linear amount of degrees of freedom. Each CZ layer adds n
2
/2 degrees of
freedom, while a CNOT layer adds n
2
degrees of freedom [33, Section I]. Hence the total
degrees of freedom is given by 3n + 2 · 3n + 2 · n
2
/2 + n
2
= 2n
2
+ O(n).
For the 2-qubit gate depth, we note that any CNOT circuit can be implemented on a
linear nearest neighbour architecture in depth 5n [31]. A CZ circuit followed or preceded
by a series of SWAP gates that reverses the qubit order can be implemented in depth
2n + 2 on a linear nearest neighbour architecture [33, Thm. 6]. But by [33, Cor. 7], when
we have two of these CZ circuits, possibly separated by some other gates, then this pair
of CZ circuits can be implemented in 2-qubit gate depth 4n 2. As the only layers in
our pseudo-normal form that contribute to the 2-qubit gate depth are two CZ layers and
a CNOT layer we then indeed have a total depth of 5n + 4n 2 = 9n 2.
7 Circuit extraction for general circuits
If a Clifford+T circuit or a more general circuit containing gates Z
α
or X
α
for α 6= k
π
2
is fed into our simplification routine, there might still be interior spiders left, and hence
the diagram will not be in GS-LC form. Our general strategy for extracting a circuit from
a diagram produced by our simplification routine is to progress through the diagram from
right-to-left, consuming vertices to the left and introducing quantum gates on the right.
For an n-qubit circuit, we maintain a layer of n vertices called the frontier between these
two parts. The goal is therefore to progress the frontier from the outputs all the way to the
Accepted in Quantum 2020-04-27, click title to verify 14
inputs, at which point we are left with an extracted circuit. We will see that the existence
of a focused gFlow guarantees we can always progress the frontier leftward in this manner.
Much like in the Clifford case, our extraction procedure relies on applying (a variant
of) Gaussian elimination on the adjacency matrix of a graph. Hence, we first establish
a correspondence between primitive row operations and CNOT gates, which is proven in
Appendix B.3.
Proposition 7.1. For any ZX-diagram D, the following equation holds:
. . .
M
. . .
. . .
D
=
. . .
M
0
. . .
. . .
D
where M describes the biadjacency matrix of the relevant vertices, and M
0
is the matrix
produced by starting with M and then adding row 1 to row 2, taking sums modulo 2.
Furthermore, if the diagram on the LHS has a focused gFlow, then so does the RHS.
We now describe our extraction procedure at a high level. To aid in understanding
this procedure, we provide a fully worked-out example in Appendix A and a pseudocode
description in Appendix C. To start, let the frontier F consist of all the output vertices.
If a vertex of the frontier has a non-zero phase, unfuse this phase in the direction of the
output. Whenever two vertices of the frontier are connected, unfuse this connection into a
CZ gate. If the diagram started out having a gFlow, then the resulting diagram still has a
gFlow since we only affected output vertices. Let g be the gFlow of the diagram. We push
the frontier onto new vertices in the following way:
1. Find an unextracted vertex v such that g(v) F . Such a vertex always exists: take
for instance any non-frontier vertex that is maximal in the gFlow order.
2. We know that Odd(g(v)) = {v} hence we can pick a designated frontier vertex
w g(v) such that w is connected to v.
3. Write the biadjency matrix of g(v) F and their neighbours to the left of the frontier
(‘the past’). Because Odd(g(v)) = {v} we know that the sum of all the rows in this
matrix modulo 2 is an all-zero vector except for a 1 corresponding to v. Hence, if we
apply row operations with w as the target from every other vertex in g(v) we know
that w will have only a single vertex connected to it in its past, namely v. Do these
row operations using Proposition 7.1. As a result, CNOT gates will be pushed onto
the extracted circuit. By that same proposition, the diagram will still have a gFlow.
4. At this point it might be that v is still connected to vertices of F that are not w.
For each of these vertices w
0
F , do a row operation from w to w
0
by adding the
corresponding CNOT to the extracted diagram in order to disconnect w
0
from v. At
this point v’s only connection to F is via w. We can therefore conclude that the
gFlow of the resulting diagram is such that the only vertex u that has w g(u) is v.
5. The vertex w has arity 2 and since it is phaseless we can remove it from the diagram
by (i1). Remove w from the frontier, and replace it by v. By the remarks in the
previous point the resulting diagram still has a gFlow. Unfuse the phase of v as a
phase gate to the extracted part.
Accepted in Quantum 2020-04-27, click title to verify 15
Figure 3: Comparison of different circuit optimization methods for random 8-qubit circuits with a varying
proportion p
t
of T gates. ‘original+’ applies simple peephole optimisations (e.g. gate cancellations),
‘naïve’ reduces each block of Clifford circuits to GS-LC form and re-synthesizes it, whereas ‘pyzx’ is our
full optimise-and-extract procedure.
6. If there are still unextracted vertices, go back to step 1, otherwise we are done.
After all vertices have been extracted by the above procedure, we will have some permu-
tation of the frontier vertices to the inputs. The extraction is finished by realising this
permutation as a series of SWAP gates.
Remark 7.2. An interesting thing to note is we do not actually need a pre-calculated
focused gFlow for this algorithm: knowing that one exists is enough. In step 3, it suffices
to apply primitive row operations until a row with a single 1 appears in the biadjacency
matrix. If this is possible by some set of row operations (i.e. if there exists a focused
gFlow), such a row will always appear in the reduced echelon form, so we can simply do
Gauss-Jordan elimination. This is how we describe this step in the pseudocode presented
in Appendix C.
Remark 7.3. The cost of the implementation of the extraction algorithm is dominated by
the Gauss-Jordan elimination steps. The amount of rows in the matrices involved is equal
to the qubit count q, while the amount of columns is equal to the amount of neighbours of
the frontier, and is hence upper-bounded by the amount of spiders in the diagram n. As in
the worst case n elimination steps are needed and each elimination step takes O(q
2
n), this
brings the complexity to O(q
2
n
2
). As with simplification, we see much more favourable
scaling in practice, due to sparsity of the graphs involved. For circuit extraction, our
implementation gives similar performance to that described in Remark 5.6.
Picking up our example from the previous section, we can apply this procedure to the
skeleton of the circuit in equation (10) and we obtain a new, extracted circuit:
π
2
π
2
π
4
π
4
π
5π
4
π
4
π
The circuit has been reduced from 195 gates to 41 gates, going via an intermediate repre-
sentation as a ZX-diagram with 12 spiders. As mentioned in the introduction, this example
is available as a Jupyter notebook demos/example-gtsimp.ipynb in the PyZX [28] repos-
itory on GitHub.
In Figure 3, we give an empirical comparison between the full optimise-and-extract
technique and the naïve approach of optimising all of the Clifford sub-circuits of a general
Accepted in Quantum 2020-04-27, click title to verify 16
Clifford+T circuit. This data was produced by generating random 8 qubit Clifford+T
circuits with 800 gates where the probability that each gate is a CNOT gate is 0.3 and we
vary the probability p
t
of T gates from 0 to 0.15. For each value we generate 20 circuits
and we report the average total and 2-qubit gate counts for the original circuit (labelled
original in Figure 3) and 3 different reduced versions.
The first reduced version (original+) is the original circuit after some basic post-
processing. This post-processing tries to cancel and combine as many adjacent gates as
possible. It does this by applying a forward pass on the circuit, where simple 2-gate com-
mutations such as CZ(1H) = (1H)CNOT are used to delay the placement of Hadamard
gates in the circuit as long as possible, while at the same time keeping track of a stack of
commuting gates behind the delayed Hadamard gates that are available for combination
with new incoming gates. After a pass, the circuit is reversed and the process is repeated
until no more gate reductions occur. This post-processing is intended to eliminate obvious
redundancies, rather than providing significant gate-based optimisations such as those in
e.g. [35].
The interesting two cases in Figure 3 are naïve and pyzx. In the naïve case, we cut
the circuit into alternating layers of Clifford circuits and T-gates. We then apply the
Clifford normalisation and extraction described in Section 6 to each Clifford chunk. For
pyzx, the full Clifford+T simplification and extraction described in Section 7 is applied. In
both cases, the resulting circuit is post-processed as in original+. For the steps requiring
Gaussian elimination, we use the asymptotically optimal algorithm proposed in Ref. [32].
When the circuits are very close to Clifford, both of the second two optimisations
perform very well, and the pyzx method outperforms the naïve method in every case. For
the naïve method, as the probability of T gates increases, each Clifford chunk will have far
fewer than quadratically many 2-qubit gates, in which case resynthesizing is likely actually
increase the gate count. At high T gate probability, Figure 3 shows that the gate and 2-
qubit gate count of the naïve method saturate. This is because the Clifford chunks are so
small that no Gaussian elimination is used at all. The pyzx case performs much better than
the naïve case, as it can use more ‘non-local’ structure that looks beyond the boundary
of the Clifford subcircuits. Nevertheless, as the non-Clifford density increases, the pyzx
routine also begins to increase the gate count. This is because we are still re-synthesising
parts of the circuit using the procedure from Ref. [32]. While this is asymptotically optimal,
it is less beneficial for very small pieces of the circuit, and can even increase the gate count.
There are two general ways in which this method can be improved: better simplification,
and better extraction. The simplification can be improved by including a larger selection
of simplification steps. This is done in Ref. [27], and allows the size of the graph to be
reduced significantly in many cases. The circuit extraction can be improved in several
ways. For instance, when doing Gaussian elimination, the order of the rows in the matrix
is immaterial as it corresponds to an arbitrary labelling of interior spiders. A suitable
heuristic, such as for instance the genetic algorithm of Ref. [26], for choosing an order of
columns can greatly improve the performance of the Gaussian elimination.
These experiments are available as a Jupyter Notebook in the PyZX repository
4
.
4
nbviewer.jupyter.org/github/Quantomatic/pyzx/blob/671da79/demos/Optimising
almost-Clifford circuits.ipynb
Accepted in Quantum 2020-04-27, click title to verify 17
8 Conclusions and Future Work
We have introduced a terminating rewrite strategy for ZX-diagrams that simplifies Clifford
circuits to GS-LC form using the graph-theoretic notions of local complementation and
pivoting. We have shown how the diagrams produced by the rewrite strategy applied to
non-Clifford circuits can be turned back into a circuit using the fact that our rewrites
preserve focused gFlow.
The question of how a circuit can be extracted from a general ZX-diagram is still open.
We speculate that this problem is not tractable in the general case, as it seems to be related
to the problem of finding an ancilla-free unitary from a circuit containing ancillae. This
observation does however not preclude finding larger classes of rewrites and ZX-diagrams
such that we can efficiently extract a circuit.
The next step for optimising quantum circuits using ZX-diagrams is to find additional
rewrite rules that allow one to produce smaller diagrams, while still being able to extract
the diagrams into a circuit. As mentioned in the introduction, two of the authors have
recently proposed an approach for T-count reduction based on the methods described here
which has been very successful in the ancilla-free case [27]. As mentioned in Ref. [27],
even more dramatic simplifications of ZX-diagrams are possible, but re-extracting a circuit
using gFlow becomes problematic. Developing more general circuit extraction procedures,
possibly with the help of ancillae and classical control is therefore a topic of ongoing
research.
A second avenue of future work is to adapt the circuit extraction procedure to work
in constrained qubit topologies. Many near-term quantum devices only allow interactions
between certain pairs of qubits (e.g. nearest neighbours in some fixed planar graph). A
notable feature of the circuit extraction procedure described in Section 7 is that we have
some freedom in choosing which CNOTs to apply in reducing the bi-adjacency matrix of
the ZX-diagram. Indeed it effectively amounts to performing Gaussian elimination using
only a constrained set of primitive row operations. In Ref. [26] (and independently in [36])
a strategy based on Steiner trees has been proposed for doing exactly that for CNOT or
CNOT+Phase circuits. In principle, these methods are directly applicable to the extraction
procedure from Section 7. However, unlike the simpler cases considered by [26] and [36],
our extraction procedure relies on many rounds of Gaussian elimination, so it will likely
be necessary to use some sort of lookahead to minimise global overhead.
Acknowledgements. SP acknowledges support from the projects ANR-17-CE25-0009 SoftQPro,
ANR-17-CE24-0035 VanQuTe, PIA-GDN/Quantex, and LUE / UOQ. AK and JvdW are supported
in part by AFOSR grant FA2386-18-1-4028. We would like to thank Quanlong Wang and Niel de
Beaudrap for useful conversations about circuit optimisation and extraction with the ZX-calculus.
References
[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits.
Physical Review A, 70(5):052328, 2004. DOI: 10.1103/PhysRevA.70.052328.
[2] Nabila Abdessaied, Mathias Soeken, and Rolf Drechsler. Quantum circuit optimiza-
tion by Hadamard gate reduction. In International Conference on Reversible Compu-
tation, pages 149–162. Springer, 2014. DOI: 10.1007/978-3-319-08494-7_12.
[3] Matthew Amy, Dmitri Maslov, and Michele Mosca. Polynomial-time T-depth op-
timization of Clifford+ T circuits via matroid partitioning. IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, 33(10):1476–1489, 2014.
DOI: 10.1109/TCAD.2014.2341953.
Accepted in Quantum 2020-04-27, click title to verify 18
[4] Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. New
Journal of Physics, 16(9):093021, 2014. DOI: 10.1088/1367-2630/16/9/093021.
[5] Miriam Backens. Making the stabilizer ZX-calculus complete for scalars. In Chris
Heunen, Peter Selinger, and Jamie Vicary, editors, Proceedings of the 12th Inter-
national Workshop on Quantum Physics and Logic (QPL 2015), volume 195 of
Electronic Proceedings in Theoretical Computer Science, pages 17–32, 2015. DOI:
10.4204/EPTCS.195.2.
[6] André Bouchet. Graphic presentations of isotropic systems. J. Comb. Theory Ser. A,
45:58–76, July 1987. ISSN 0097-3165. URL http://dl.acm.org/citation.cfm?id=
51355.51360.
[7] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the
clifford group. arXiv preprint arXiv:2003.09412, 2020.
[8] Daniel E Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix. Generalized
flow and determinism in measurement-based quantum computation. New Journal of
Physics, 9(8):250, 2007. DOI: 10.1088/1367-2630/9/8/250. URL http://stacks.
iop.org/1367-2630/9/i=8/a=250.
[9] Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Com-
pleteness of Graphical Languages for Mixed States Quantum Mechanics. In Christel
Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th
International Colloquium on Automata, Languages, and Programming (ICALP 2019),
volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 108:1–
108:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
ISBN 978-3-95977-109-2. DOI: 10.4230/LIPIcs.ICALP.2019.108.
[10] B. Coecke and A. Kissinger. Picturing Quantum Processes. Cambridge University
Press, 2014. DOI: 10.1007/978-3-319-91376-6_6.
[11] Bob Coecke and Ross Duncan. Interacting quantum observables: Categorical al-
gebra and diagrammatics. New Journal of Physics, 13(4):043016, apr 2011. DOI:
10.1088/1367-2630/13/4/043016. URL https://doi.org/10.1088%2F1367-2630%
2F13%2F4%2F043016.
[12] V. Danos and E. Kashefi. Determinism in the one-way model. Phys. Rev. A, 74
(052310), 2006. DOI: 10.1103/PhysRevA.74.052310.
[13] Vincent Danos, Elham Kashefi, and Prakash Panangaden. The measurement calculus.
Journal of the ACM (JACM), 54(2):8, 2007. DOI: 10.1145/1219092.1219096.
[14] Vincent Danos, Elham Kashefi, Prakash Panangaden, and Simon Perdrix. Extended
Measurement Calculus. Semantic Techniques in Quantum Computation, 2010. DOI:
10.1017/CBO9781139193313.008.
[15] Jeroen Dehaene and Bart De Moor. Clifford group, stabilizer states, and linear
and quadratic operations over GF(2). Physical Review A, 68(4):042318, 2003. DOI:
10.1103/PhysRevA.68.042318.
[16] R. Duncan and S. Perdrix. Graph states and the necessity of Euler decomposi-
tion. Mathematical Theory and Computational Practice, pages 167–177, 2009. DOI:
10.1007/978-3-642-03073-4_18.
[17] R. Duncan and S. Perdrix. Rewriting measurement-based quantum computations with
generalised flow. In Proceedings of ICALP, Lecture Notes in Computer Science, pages
285–296. Springer, 2010. DOI: 10.1007/978-3-642-14162-1_24.
[18] Ross Duncan and Simon Perdrix. Pivoting makes the ZX-calculus complete for real
stabilizers. In Proceedings of the 10th International Workshop on Quantum Physics
and Logic (QPL), volume 171 of Electronic Proceedings in Theoretical Computer Sci-
ence, pages 50–62. Open Publishing Association, 2014. DOI: 10.4204/EPTCS.171.5.
Accepted in Quantum 2020-04-27, click title to verify 19
[19] Andrew Fagan and Ross Duncan. Optimising Clifford Circuits with Quantomatic.
In Proceedings of the 15th International Conference on Quantum Physics and Logic
(QPL), volume 287 of Electronic Proceedings in Theoretical Computer Science, pages
85–105. Open Publishing Association, 2019. DOI: 10.4204/EPTCS.287.5.
[20] Amar Hadzihasanovic, Kang Feng Ng, and Quanlong Wang. Two complete ax-
iomatisations of pure-state qubit quantum computing. In Proceedings of the 33rd
Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages
502–511, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5583-4. DOI:
10.1145/3209108.3209128.
[21] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M Nest, and H-J Briegel.
Entanglement in graph states and its applications. In Proceedings of the International
School of Physics "Enrico Fermi", Quantum Computers, Algorithms and Chaos,, vol-
ume 162, pages 115 218, 2006. DOI: 10.3254/978-1-61499-018-5-115.
[22] Luke E Heyfron and Earl T Campbell. An efficient quantum compiler that reduces
T count. Quantum Science and Technology, 4(015004), 2018. DOI: 10.1088/2058-
9565/aad604.
[23] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Diagrammatic Rea-
soning Beyond Clifford+T Quantum Mechanics. In Proceedings of the 33rd An-
nual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages
569–578, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5583-4. DOI:
10.1145/3209108.3209139.
[24] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Complete Axiomati-
sation of the ZX-Calculus for Clifford+T Quantum Mechanics. In Proceedings of
the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18,
pages 559–568, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5583-4. DOI:
10.1145/3209108.3209131.
[25] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A generic normal form for
zx-diagrams and application to the rational angle completeness. In Proceedings of the
34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019.
DOI: 10.1109/LICS.2019.8785754.
[26] Aleks Kissinger and Arianne Meijer-van de Griend. Cnot circuit extraction for
topologically-constrained quantum memories. arXiv preprint arXiv:1904.00633, 2019.
[27] Aleks Kissinger and John van de Wetering. Reducing T-count with the ZX-calculus.
arXiv preprint arXiv:1903.10477, 2019.
[28] Aleks Kissinger and John van de Wetering. Pyzx: Large scale automated diagram-
matic reasoning. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th In-
ternational Conference on Quantum Physics and Logic, Chapman University, Or-
ange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theo-
retical Computer Science, pages 229–241. Open Publishing Association, 2020. DOI:
10.4204/EPTCS.318.14.
[29] Vadym Kliuchnikov and Dmitri Maslov. Optimization of Clifford circuits. Phys. Rev.
A, 88:052307, Nov 2013. DOI: 10.1103/PhysRevA.88.052307.
[30] Anton Kotzig. Eulerian lines in finite 4-valent graphs and their transformations. In
Colloqium on Graph Theory Tihany 1966, pages 219–230. Academic Press, 1968.
[31] Samuel A Kutin, David Petrie Moulton, and Lawren M Smithline. Computation at a
distance. arXiv preprint quant-ph/0701194, 2007.
[32] Ketan Markov, Igor Patel, and John Hayes. Optimal synthesis of linear reversible
circuits. Quantum Information and Computation, 8(3&4):0282–0294, 2008.
Accepted in Quantum 2020-04-27, click title to verify 20
[33] Dmitri Maslov and Martin Roetteler. Shorter stabilizer circuits via Bruhat decom-
position and quantum circuit transformations. IEEE Transactions on Information
Theory, 64(7):4729–4738, 2018. DOI: 10.1109/TIT.2018.2825602.
[34] Mehdi Mhalla, Mio Murao, Simon Perdrix, Masato Someya, and Peter S Turner.
Which graph states are useful for quantum information processing? In Conference on
Quantum Computation, Communication, and Cryptography, pages 174–187. Springer,
2011. DOI: 10.1007/978-3-642-54429-3_12.
[35] Yunseong Nam, Neil J Ross, Yuan Su, Andrew M Childs, and Dmitri Maslov. Au-
tomated optimization of large quantum circuits with continuous parameters. npj
Quantum Information, 4(1):23, 2018. DOI: 10.1038/s41534-018-0072-4.
[36] Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. Quantum circuit optimizations
for NISQ architectures. arXiv preprint arXiv:1904.01972, 2019.
[37] M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information.
Cambridge university press, 2010. DOI: 10.1119/1.1463744.
[38] Maarten Van Den Nest. Classical simulation of quantum computation, the gottesman-
knill theorem, and slightly beyond. Quantum Information & Computation, 10(3):
258–271, 2010.
[39] Renaud Vilmart. A near-optimal axiomatisation of ZX-calculus for pure qubit quan-
tum mechanics. In Proceedings of the 34th Annual ACM/IEEE Symposium on
Logic in Computer Science (LICS), 2019. DOI: 10.1109/LICS.2019.8785765. URL
https://arxiv.org/abs/1812.09114.
[40] Fang Zhang and Jianxin Chen. Optimizing t gates in clifford+t circuit as π/4 rotations
around paulis. arXiv:1903.12456, 2019.
A Example derivation
In this section we will work through a complete example of our simplification algorithm.
Let us start with the following circuit:
3π
2
π
2
π
2
3π
2
π
π
4
π
4
π
2
π
2
π
2
π
This has 5 two-qubit gates and 19 single-qubit gates. Using the procedure of Lemma 3.2
to get it in graph-like form we get:
3π
2
π
2
π
2
π
4
π
4
3π
2
π
π
2
π
2
π
2
π
We see that we have multiple interior Pauli and proper Clifford phases and hence
we must do local complementations and pivots. We start by doing a sequence of local
complementations. The locations of these operations are marked by a red star.
Accepted in Quantum 2020-04-27, click title to verify 21
3π
2
π
2
π
2
π
4
π
4
3π
2
π
π
2
π
2
π
2
π
π
π
2
3π
2
π
4
7π
4
3π
2
π
π
2
π
2
π
2
π
π
π
2
π
4
7π
4
3π
2
π
2
π
2
π
2
π
π
π
2
3π
2
π
4
7π
4
3π
2
π
2
π
π
π
2
3π
2
π
4
7π
4
π
π
2
=
= =
=
*
*
*
*
We now have two internal Pauli vertices left, but they are not connected. Hence we must
use equation (9), to be able to get rid of them:
π
π
2
3π
2
π
4
7π
4
π
π
2
π
7π
4
3π
2
π
2
π
π
2
π
4
=
Applying the pivots to the designated vertices gives us:
π
7π
4
3π
2
π
2
π
π
2
π
4
π
7π
4
π
3π
2
π
2
π
2
π
4
π
7π
4
π
3π
2
π
2
π
2
π
4
=
=
* *
* *
Note that in the bottom qubit we end up where we started before doing the pivots, but
now we have marked the π/2 vertex as a local Clifford, and hence the π vertex now counts
as a boundary vertex. This means the simplification procedure has ended. The final step
is extracting a circuit:
Accepted in Quantum 2020-04-27, click title to verify 22
π
7π
4
π
3π
2
π
2
π
2
π
4
=
π
7π
4
π
3π
2
π
2
π
2
π
4
=
π
7π
4
π
3π
2
π
2
π
2
π
4
*
*
*
7π
4
3π
2
π
2
π
2
π
4
=
π
π
Here the frontier is marked by the box. We first unfuse the phases onto gates. Then we
want to extract new vertices. These are marked by a red star. Since the three marked
vertices have no other connections to the frontier, and the frontier vertices have only these
single neighbours, we can extract these by simply putting them onto the frontier. The next
step is to extract the bottomleft vertex, but in this case there is a connection too many
which we must extract as a CNOT:
7π
4
3π
2
π
2
π
2
π
4
=
*
π
π
7π
4
3π
2
π
2
π
2
π
4
=
*
π
π
7π
4
3π
2
π
2
π
2
π
4
π
π
We now simply repeat this procedure until the entire circuit is extracted.
=
π
7π
4
π
π
2
π
2
π
4
3π
2
=
π
7π
4
π
π
2
π
2
π
4
3π
2
=
π
7π
4
π
π
2
π
2
π
4
3π
2
π
7π
4
π
3π
2
π
2
π
2
π
4
=
π
7π
4
π
3π
2
π
2
π
2
π
4
*
*
*
*
=
π
7π
4
π
3π
2
π
2
π
2
π
4
The extracted circuit has 4 two-qubit gates and 18 single-qubit gates. Applying some
final gate simplifications on the inputs and outputs gets the number of single-qubit gates
down to 11:
Accepted in Quantum 2020-04-27, click title to verify 23
π
7π
4
π
π
2
π
2
π
4
3π
2
B Proofs
B.1 Circuits and focused gFlow
To show that graph-like ZX-diagrams arising from circuits admit a focused gFlow, we
introduce a simpler sufficient condition.
Definition B.1. [12] Given an open graph G, a causal flow (f, ) on G consists of a
function f : O I and a partial order on the set V satisfying the following properties:
1. f(v) v
2. v f(v)
3. if u f(v) then v u
where v u means that u and v are adjacent in the graph.
Like focused gFlow, causal flow is a special case of a more general property called
gFlow:
Definition B.2. Given an open graph G, a generalised flow, or gFlow consists of a pair
(g : O 2
I
, ) such that for any u O:
1. u Odd
G
(g(u))
2. if v g(u), then u v
3. if v Odd
G
(g(u)) and v 6= u, then u v
In the case where all of the sets g(u) are singletons, the conditions above are equivalent
to the causal flow conditions. Hence, if a graph admits a causal flow, it also admits a
gFlow by letting g(u) := {f(u)}. It was furthermore shown in [34] that any gFlow can be
systematically transformed into a focused gFlow. Combining these two facts, we obtain
the following theorem.
Theorem B.3. If an open graph admits a causal flow (f, ), then it also admits a focused
gFlow.
The following proof of Lemma 3.7 shows that the diagrams produced by making a
circuit graph-like according to the procedure outlined in Lemma 3.2 have causal flow and
hence a focused gFlow.
Proof of Lemma 3.7. Let D denote the circuit, and let D
0
denote the diagram produced
by applying the procedure of Lemma 3.2 to D.
In order to prove that D
0
has a focused gFlow, it suffices to show that it admits a
causal flow, by Theorem B.3.
With every spider v of the circuit D we associate a number q
v
specifying on which
‘qubit-line’ it appears. We also associate a ‘row-number’ r
v
0 specifying how ‘deep’ in
Accepted in Quantum 2020-04-27, click title to verify 24
the circuit it appears. Suppose now that v w in D. If they are on the same qubit, so
q
v
= q
w
, then necessarily r
v
6= r
w
. Conversely, if they are on different qubits, q
v
6= q
w
,
then they must be part of a CZ or CNOT gate, and hence r
v
= r
w
.
In the diagram resulting from Lemma 3.2, every spider arises from fusing together
adjacent spiders on the same qubit line from the original diagram. For a spider v in D
0
we
can thus associate two numbers s
v
, and t
v
, where s
v
is the lowest row-number of a spider
fused into v, and t
v
is the highest. Spider fusion from D only happens for spiders on the
same qubit-line, and hence v also inherits a q
v
from all the spiders that got fused into it.
Any two spiders v and w in D
0
with q
v
= q
w
must have been produced by fusing together
adjacent spiders on the same qubit-line, and hence we must have t
v
< s
w
or t
w
< s
v
,
depending on which of the spiders is most to the left. If instead v w and q
v
6= q
w
,
then their connection must have arisen from some CNOT or CZ gate in D, and hence the
intervals [s
v
, t
v
] and [s
w
, t
w
] must have overlap, so that necessarily s
w
t
v
and s
v
t
w
.
Now we let O be the set of spiders connected to an output, and I the set of spiders
connected to an input in D
0
. For all v O we let f(v) be the unique connected spider to
the right of v on the same qubit-line. We define the partial order as follows: v w if and
only if v = w or t
v
< t
w
. It is straightforward to check that this is indeed a partial order.
By construction f(v) v and the property v f(v), follows from t
v
< s
f(v)
discussed
above, so let us look at the third property of causal flow.
Suppose w f(v). We need to show that v w. If v = w this is trivial so suppose
v 6= w. First suppose that q
w
= q
f(v)
(which is also equal to q
v
). f(v) has a maximum
of two neighbours on the same qubit-line, and since one of them is v, this can only be if
w = f (f(v)) and hence v f(v) w, and we are done. So suppose that q
w
6= q
f(v)
. By
the discussion above, we must then have s
w
t
f(v)
and s
f(v)
t
w
. Since we also have
t
v
< s
f(v)
we get t
v
< s
f(v)
t
w
so that indeed v w.
B.2 Preservation of focused gFlow
Throughout this section, we will rely extensively on the symmetric difference of sets:
A B := (A B) \(A B). Note that is associative and commutative, so it extends to
an n-ary operation in the obvious way. For I := 1, . . . , n we have:
iI
A
i
:= A
1
A
2
. . . A
n
In particular, we have a
iI
A
i
if and only if a appears in an odd number of sets A
i
. By
convention, we assume
...
binds as far to the right as possible, i.e.
iI
A
i
B
:=
iI
(A
i
B)
B.2.1 Local complementation
The following lemma will be needed in the other proofs, it shows how the odd neighbour-
hood of a set evolves under local complementation:
Lemma B.4. Given a graph G = (V, E), A V and u V ,
Odd
G?u
(A) =
(
Odd
G
(A) (N
G
(u) A) if u / Odd
G
(A)
Odd
G
(A) (N
G
(u) \ A) if u Odd
G
(A)
Accepted in Quantum 2020-04-27, click title to verify 25
Proof. First notice that Odd
G
(.) is linear: A, B, Odd
G
(A B) = Odd
G
(A) Odd
G
(B).
Moreover v, Odd
G
({v}) = N
G
(v), the neighbourhood of v in G. As a consequence,
A, Odd
G
(A) =
vA
N
G
(v).
The local complementation is acting as follows on the neighbourhoods:
v, N
G?u
(v) =
(
N
G
(v) N
G
(u) {v} if v N
G
(u)
N
G
(v) otherwise
As a consequence,
Odd
G?u
(A) =
vA
N
G?u
(v)
=
vAN
G
(u)
N
G
(v) N
G
(u) {v}
!
vA\N
G
(u)
N
G
(v)
!
=
vA
N
G
(v)
vAN
G
(u)
N
G
(u)
!
vAN
G
(u)
{v}
!
= Odd
G
(A)
vAN
G
(u)
N
G
(u)
!
(A N
G
(u))
Notice that |AN
G
(u)| 1 mod 2 iff u Odd
G
(A). Hence, if u / Odd
G
(A), Odd
G?u
(A) =
Odd
G
(A) (A N
G
(u)). Otherwise, if u Odd
G
(A), Odd
G?u
(A) = Odd
G
(A) N
G
(u)
(A N
G
(u)) = Odd
G
(A) (N
G
(u) \ A).
Lemma B.5. If (g, ) is a focused gFlow for (G, I, O) then (g
0
, ) is a focused gFlow for
(G u \ {u}, I, O) where g
0
: O \ {u} 2
I\{u}
is recursively defined as
g
0
(w) :=
g(w)
tR
w
g
0
(t)
if u / g(w)
g(w) {u} g(u)
tR
u
R
w
g
0
(t)
if u g(w)
where R
w
:= N
G
(u) g(w) O.
Proof. First of all, g
0
can indeed be defined inductively by starting at the maximal elements
in the partial order, since for any t R
w
, t g(w) so that w t, and similarly when
u g(w), w u so t R
u
implies u t hence w t. That g
0
preserves the order, i.e.
v g
0
(w) = w v, follows similarly. Moreover, it is easy to show that w O \ {u},
g
0
(w) I \ {u}.
It remains to show that w O\{u}, Odd
G?u\u
(g
0
(w)) O = {w}, or equivalently,
letting O
0
:= O {u}, w O
0
, Odd
G?u
(g
0
(w)) O
0
= {w}.
First notice that for any w O
0
, u / Odd
G
(g(w)) (because Odd
G
(g(w)) {w} O),
and hence using Lemma B.4, the linearity of Odd(.) and the distributivity of over ,
Odd
G?u
(g(w)) O
0
= Odd
G
(g(w)) O
0
(N
G
(u) g(w) O
0
)
= {w} R
w
Accepted in Quantum 2020-04-27, click title to verify 26
Moreover, u Odd
G
(g(u)), so
Odd
G?u
({u} g(u)) O
0
= (N
G?u
(u) Odd
G?u
(g(u))) O
0
(Lemma B.4) = (N
G
(u) Odd
G
(g(u)) (N
G
(u) \ g(u))) O
0
= (Odd
G
(g(u)) O
0
) (N
G
(u) g(u) O
0
)
= N
G
(u) g(u) O
0
= R
u
As a consequence, again using distributivity of over the odd neighbourhood and the
definition of g
0
:
Odd
G?u
g
0
(w)
O
0
=
{w} R
w
tR
w
Odd
G?u
(g
0
(t)) O
0
if u / g(w)
{w} R
w
R
u
tR
u
R
w
Odd
G?u
(g
0
(t)) O
0
if u g(w)
By induction on w O
0
, starting at maximal elements in the order, we will now show
that Odd
G?u
(g
0
(w)) O
0
= {w}.
Let w
0
O
0
be maximal for i.e. w O
0
, ¬(w
0
w). By maximality we must have
g(w
0
) O
0
and hence R
w
0
= . If u / g(w
0
), we then have Odd
G?u
(g
0
(w
0
)) O
0
= {w
0
}
and we are done. Otherwise, if u g(w
0
), then w
0
u, so that u is also maximal and
hence g(u) O which also gives R
u
= . As a result Odd
G?u
(g
0
(w)) O
0
is also equal to
{w
0
} in this case.
Now let w O
0
be arbitary. By induction we can now assume that for any t R
w
Odd
G?u
(g
0
(t)) O
0
= {t}. Hence:
If u / g(w),
Odd
G?u
g
0
(w)
O
0
= {w} R
w
tR
w
Odd
G?u
g
0
(t)
O
0
(IH) = {w} R
w
tR
w
{t}
= {w} R
w
R
w
= {w}
If u g(w), then w u and hence also Odd
G?u
(g
0
(t)) O
0
= {t} for any t R
u
.
We calculate:
Odd
G?u
g
0
(w)
O
0
= {w} R
w
R
u
tR
u
R
w
Odd
G?u
g
0
(t)
O
0
(IH) = {w} R
w
R
u
tR
u
R
w
{t}
= {w} R
w
R
u
R
u
R
w
= {w}
Remark B.6. If (g, ) is a focused gFlow for (G, I, O) then (g
0
, ) is a gFlow for (G
u \ u, I, O) where g
0
: O \ {u} 2
I\{u}
is defined as
g
0
(w) :=
(
g(w) if u / g(w)
g(w) {u} g(u) otherwise
Notice that (g
0
, ) is not necessarily a focused gFlow.
Accepted in Quantum 2020-04-27, click title to verify 27
B.2.2 Pivoting
We will show in this section that pivoting preserves focused gFlow. For this, it will be useful
to introduce some special sets. Let N
G
[u] := N
G
(u) {u} and Odd
G
[A] := Odd
G
(A) A
denote the closed neighbourhood and the closed odd neighbourhood respectively. Now, we
prove a technical lemma about the action of pivoting on the odd-neighbourhood in terms
of these sets.
Lemma B.7. Given a graph G = (V, E), A V , u V , and v N
G
(u),
Odd
Guv
(A) =
Odd
G
(A) if u, v / Odd
G
[A]
Odd
G
(A) N
G
[v] if u Odd
G
[A] , v / Odd
G
[A]
Odd
G
(A) N
G
[u] if u / Odd
G
[A] , v Odd
G
[A]
Odd
G
(A) N
G
[u] N
G
[v] if u, v Odd
G
[A]
(13)
Proof. Note that pivoting acts as follows on neighbourhoods:
w, N
Guv
(w) =
N
G
(w) N
G
[u] N
G
[v] if w N
G
[u] N
G
[v]
N
G
(w) N
G
[v] if w N
G
[u] \ N
G
[v]
N
G
(w) N
G
[u] if w N
G
[v] \ N
G
[u]
N
G
(w) otherwise
As a consequence,
Odd
Guv
(A) =
wA
N
Guv
(w)
=
wAN
G
[u]N
G
[v]
N
Guv
(w)
wAN
G
[u]
c
N
G
[v]
c
N
Guv
(w)
wAN
G
[u]
c
N
G
[v]
N
Guv
(w)
wAN
G
[u]N
G
[v]
c
N
Guv
(w)
=
wAN
G
[u]N
G
[v]
N
G
(w) N
G
[u] N
G
[v]
wAN
G
[u]
c
N
G
[v]
c
N
G
(w)
wAN
G
[u]
c
N
G
[v]
N
G
(w) N
G
[u]
!
wAN
G
[u]N
G
[v]
c
N
G
(w) N
G
[v]
!
= Odd
G
(A)
wAN
G
[v]
N
G
[u]
!
wAN
G
[u]
N
G
[v]
!
Notice that |A N
G
[u]| 1 mod 2 iff u Odd
G
[A], and similarly for v. Hence we obtain
(13) by case distinction.
Lemma B.8. If (g, ) is a focused gFlow for (G, I, O) then (g
0
, ) is a focused gFlow for
(G uv \{u, v}, I, O) where w O \{u, v}, g
0
(w) := g(w) \ {u, v}.
Proof. Every condition needed for g
0
to be a focused gFlow is obvious except that w
O\{u, v}, Odd
Guv\u\v
(g
0
(w)) O = {w}, or equivalently, defining O
0
:= O {u, v}, w
O
0
, Odd
Guv
(g
0
(w)) O
0
= {w}
Let w O
0
. Note that Odd
G
[g(w)] = Odd
G
(g(w)) g(w) = {w} g(w) = g(w) {w},
and thus u Odd
G
[g(w)] u g(w) and similarly for v. Hence, using Lemma B.7:
Accepted in Quantum 2020-04-27, click title to verify 28
If u, v g(w),
Odd
Guv
g
0
(w)
O
0
= Odd
Guv
(g(w) {u, v}) O
0
= Odd
Guv
(g(w)) O
0
Odd
Guv
({u, v}) O
0
(Lemma B.7) = Odd
G
(g(w)) O
0
(N
G
[u] N
G
[v]) O
0
Odd
G
({u, v}) O
0
= Odd
G
(g(w)) O
0
Odd
G
({u, v}) O
0
Odd
G
({u, v}) O
0
= {w}
If u g(w) and v / g(w),
Odd
Guv
g
0
(w)
O
0
= Odd
Guv
(g(w) {u}) O
0
= Odd
Guv
(g(w)) O
0
Odd
Guv
({u}) O
0
(Lemma B.7) = Odd
G
(g(w)) O
0
N
G
[v] O
0
Odd
G
({v}) O
0
= {w}
Here we have used that Odd
Guv
({u}) = N
G
(v) and that N
G
[v] O
0
= N
G
(v) O
0
.
If u / g(w) and v g(w) we prove it similarly to the previous case.
If u, v / g(w),
Odd
Guv
g
0
(w)
O
0
= Odd
Guv
(g(w)) O
0
= Odd
G
(g(w)) O
0
= {w}
B.3 ZX reduction rules
Lemma (5.2).
±
π
2
α
1
α
n
...
... ...
=
...
α
1
π
2
...
α
n
π
2
α
2
...
α
n1
...
α
2
π
2
...
α
n1
π
2
...
...
Proof. First of all, we will need the following equation:
π
2
=
π
2
π
2
=
-
π
2
-
π
2
-
π
2
=
-
π
2
-
π
2
=
-
π
2
=
-
π
2
(14)
We pull out all of the phases via (f ) then apply the local complementation rule (5):
±
π
2
α
1
α
n
...
... ...
=
α
2
...
α
n1
...
α
1
α
n
...
... ...
α
2
...
α
n1
...
±
π
2
(f)
=
α
1
α
n
...
...
...
α
2
...
α
n1
...
±
π
2
(5)
±
π
2
π
2
π
2
π
2
π
2
Accepted in Quantum 2020-04-27, click title to verify 29
Thanks to equation (14), the topmost spider in the RHS above becomes an X-spider,
with phase π/2, which is cancelled out by X
±π/2
gate directly below it. The resulting
(phaseless) X-spider copies and fuses with the neighbours:
...
α
1
π
2
...
α
n
π
2
α
2
π
2
...
α
n1
π
2
...
...
=
α
1
π
2
α
n
π
2
...
... ...
α
2
π
2
...
α
n1
π
2
...
(f)
=
α
1
π
2
α
n
π
2
...
... ...
α
2
π
2
...
α
n1
π
2
...
(c)
=
(h)
(14)
(f)
...
Lemma (5.3).
jπ
α
1
=
α
n
β
1
β
n
γ
1
γ
n
...
...
...
α
n
+ kπ
β
n
+ (j + k + 1)π
...
β
1
+ (j + k + 1)π
γ
1
+ jπ
α
1
+ kπ
...
...
γ
n
+ jπ
...
...
...
...
...
...
...
...
...
...
...
...
Proof. We pull out all of the phases via (f ) then apply the pivoting rule (6):
α
1
α
n
β
1
β
n
γ
1
γ
n
...
...
...
...
...
...
...
...
...
(f)
jπ
α
1
α
n
β
1
β
n
γ
1
γ
n
...
...
...
...
...
...
...
...
...
=
(6)
π
π
jπ
jπ
α
1
=
α
n
β
1
β
n
γ
1
γ
n
...
...
...
...
...
...
...
...
...
We then apply the colour-change rule to turn the Z-spiders with phases jπ and kπ into
X-spiders, which copy and fuse with the neighbours of the original two vertices:
=
α
1
α
n
β
1
β
n
γ
1
γ
n
...
...
...
...
...
...
...
...
...
=
(h)
π
π
jπ
(c)
jπjπjπ
(h)
(f)
α
n
+ kπ
β
n
+ (j + k + 1)π
...
β
1
+ (j + k + 1)π
γ
1
+ jπ
α
1
+ kπ
......
γ
n
+ jπ
...
...
...
...
...
...
...
Accepted in Quantum 2020-04-27, click title to verify 30
Proposition (7.1). The following equation holds.
. . .
M
. . .
. . .
D
=
. . .
M
0
. . .
. . .
D
(15)
Here M describes the biadjacency matrix of the relevant vertices, and M
0
is the matrix
produced by starting with M and then adding row 2 to row 1, taking sums modulo 2.
Furthermore, if the diagram on the LHS has a focused gFlow, then so does the RHS.
Proof. We will show how to transform the first diagram into the second in such a way
that gFlow and equality is preserved at every step. For clarity we will not draw the entire
diagram, but instead we focus on the relevant part. First of all we note that we can add
CNOTs in the following way while preserving equality:
. . .
M
. . .
=
. . .
M
. . .
=
. . .
M
. . .
. . .
. . .
. . .
As we are only adding vertices at the outputs, it should be clear how the gFlow can be
extended to incorporate these new vertices.
Now let A denote the set of vertices connected to the top vertex, but not to the vertex
beneath it, B the set of vertices connected to both, and C the vertices connected only to
the bottom one. Further restricting our view of the diagram to just these two lines, we
see that we can apply a pivot rewrite as in (8):
A
B
C
pivot
=
A
B
C
=
A
B
C
By Corollary 5.5 this rewrite preserves focused gFlow. Looking at the connectivity matrix,
it is straightforward to see that the matrix M has now been changed in exactly the way
described.
B.4 Reduction of Local Cliffords
This section will rely on the local complementation rule:
-
π
2
π
2
π
2
π
2
N(u)
u
=
... ...
(16)
to reduce the local Cliffords in a GS-LC form to a fixed set.
Let
e
S := HSH, i.e. an X-phase gate with phase π/2. Then, (16) introduces a
e
S
on a
single output while introducing a S on each of its neighbours.
Accepted in Quantum 2020-04-27, click title to verify 31
Theorem B.9. From the GS-LC form:
LC
LC
LC
...
LC
LC
...
LC
···
(17)
it is possible to apply local complementation rule (5) until all of the local Cliffords on the
inputs are in the set {S
n
, H, ZH} and the outputs to the set {S
n
, H, HZ}.
Proof. In Ref. [4, Thm. 13], Backens showed that, from a state (i.e. a diagram with only
outputs) in GS-LC form, the rule (16) could be applied until all local Cliffords are in the
set {S
n
,
e
SS,
e
SS
} and no two qubits with an
e
S gate are adjacent. If an output has
e
SS as
its local Clifford, we can apply (16) from right to left 3 times to transform it into
e
SS
e
S H.
As the vertex is only connected to vertices that have a S
n
gate, this doesn’t change the
type of Clifford those neighbours have, and it also doesn’t create new connections between
vertices that both have a
e
S gate.
Similarly, if the output has local Clifford
e
SS
, we can apply (16) 1 time to transform
it into
e
SS
e
S
HZ. Hence, the local Cliffords on all outputs for a GS-LC state can be
taken from the set {S
n
, H, HZ}.
To go from GS-LC states considered by Backens to GS-LC maps of the form (17), we
simply change some of the outputs into inputs via (partial) transpose. Hence input local
Cliffords can be taken from the set {(S
n
)
T
, H
T
, (HZ)
T
} = {S
n
, H, ZH}.
Accepted in Quantum 2020-04-27, click title to verify 32
C Pseudo-code for extraction algorithm
Algorithm 1 Extraction algorithm
1: procedure Extract(D) input is graph-like diagram D
2: Init empty circuit C
3: G, I, O Graph(D) get the underlying graph of D
4: F O initialise the frontier
5: for v F do
6: if v connected to output by Hadamard then
7: C Hadamard(Qubit(v))
8: Remove Hadamard from v to output
9: if v has non-zero phase then
10: C Phase-gate(P hase(v), Qubit(v))
11: for edge between v and w in F do
12: C CZ(Qubit(v), Qubit(w))
13: Remove edge between v and w
14: while v D\F do there are still vertices to be processed
15: D, F, C UpdateFrontier(D, F, C)
16: for v F do the only vertices still in D are in F
17: if v connected to input via Hadamard then
18: C Hadamard(Qubit(v))
19: Perm Permutation of Qubits of F to qubits of inputs
20: for swap(q
1
, q
2
) in PermutationAsSwaps(Perm) do
21: C Swap(q
1
, q
2
)
22: return C
23: procedure UpdateFrontier(D, F, C)
24: N Neighbours(F )
25: M Biadjacency(F, N )
26: M
0
GaussReduce(M )
27: Init ws initialise empty set ws
28: for row r in M
0
do
29: if sum(r) == 1 then there is a single 1 on row r
30: Set w to vertex corresponding to nonzero column of r
31: Add w to ws w will be part of the new frontier
32: M Biadjacency(F, ws) smaller biadjacency matrix
33: for (r
1
, r
2
) GaussRowOperations(M ) do
34: C CNOT(Qubit(r
1
), Qubit(r
2
))
35: Update D based on row operation
36: for w ws do all w now have a unique neighbour in F
37: v Unique neighbour of w in F
38: C Hadamard(Qubit(v))
39: C Phase-gate(Phase(w),Qubit(v))
40: Remove phase from w
41: Remove v from F
42: Add w to F
43: for edge between w
1
and w
2
of ws do
44: C CZ(Qubit(w
1
),Qubit(w
2
))
45: Remove edge between w
1
and w
2
46: return D, F, C
Accepted in Quantum 2020-04-27, click title to verify 33