
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 [16–18], 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