February 1, 2023

Graph-theoretic simplification of quantum circuits with the ZX-calculus

Researchers have presented a completely new approach to quantum circuit optimisation, based on the ZX-calculus.

Looking at quantum circuits just as lists of gates doesn’t tell a whole lot about what computation is being performed, or how it might be optimised. However, if one “breaks open” quantum gates, one sees a rich graphical/algebraic structure inside called the ZX-calculus.

In this paper, they give a technique for optimizing quantum circuits that first breaks the gates open to reveal a graph-like structure underneath. They then give a strategy for reducing these graphs in size without changing the computation they represent, then extracting a new, smaller circuit out of the result.

They have first interpreted quantum circuits as ZX-diagrams, which provide a flexible, lower-level language for describing quantum computations graphically. Then, using the rules of the ZX-calculus, they provided a simplification strategy for ZX-diagrams based on the two graph transformations of local complementation and pivoting and showed that the resulting reduced diagram can be transformed back into a quantum circuit.

While little is known about extracting circuits from arbitrary ZX-diagrams, they showed that the underlying graph of their simplified ZX-diagram always has a graph-theoretic property called generalized 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 upper bound on gate depth for nearest-neighbour architectures.

For Clifford+T and more general circuits, their technique enabled them to “see around” gates that obstruct the Clifford structure and produce smaller circuits than naïve “cut-and-resynthesise” methods.

The team has implemented the technique described in this paper in a Python tool called PyZX.

Read more.