Preservation of determinism in MBQC under ZX-calculus rewrites

McElvanney, Tommy (2025). Preservation of determinism in MBQC under ZX-calculus rewrites. University of Birmingham. Ph.D.

Preview

McElvanney2025PhD.pdf
Text - Accepted Version
Available under License Creative Commons Attribution.
Download (1MB) | Preview

Abstract

The ZX-calculus is a powerful graphical language for reasoning about and optimizing quantum computations, being able to represent and rewrite both quantum circuits and measurement-based quantum computations (MBQCs) in a natural way, along with acting as a tool to translate between the two aforementioned types of quantum computation. Finding a circuit that is equivalent to a ZX-diagram can be #P hard [11] - it is therefore
important to look at the classes of ZX-diagrams that we have efficient circuit extraction algorithms for. The most general of these classes are ZX-diagrams with a property known as Pauli flow - this is a property from measurement-based quantum computing which ensures that computations remain deterministic despite quantum measurements being inherently probabilistic. The standard ZX-calculus rules are not particularly well suited
to measurement-based quantum computing as they often do not preserve the existence of Pauli flow nor preserve the MBQC structure itself. Thus by developing our understanding of ZX-calculus rewrite rules which preserve the existence of Pauli flow, we can better understand which ZX diagrams we are able to efficiently extract a circuit from as well as which Measurement-based computations we can perform deterministically.

In this thesis, I introduce new ZX-calculus rewrite rules and prove that these rules preserve the existence of Pauli flow. These rules have a variety of applications across many areas of quantum computation which will also be explored - to start, I show that these rules give us a procedure for rewriting any measurement-based quantum computation with arbitrary planar measurements along with X, Y and Z Pauli measurements into a diagram containing only XY -planar measurements and X and Y Pauli measurements (that is, only containing green spiders in the ZX-calculus). I then show that when we restrict to the stabilizer fragment of quantum computing - where we only have Pauli-measurements in measurement-based quantum computations - we are able to find a complete set of rewrite rules which preserve the existence of Pauli flow. To do this, I introduce a procedure for rewriting any stabilizer ZX-diagram into a unique normal form using only flow-preserving rewrite rules.

Finally, I examine the flow preservation of the "neighbour unfusion" rule of [60]. This rule was used in an optimization procedure for reducing 2-qubit gate count but the authors did not know in what cases this rule preserved gflow which was important for their algorithm to function. Neighbour unfusion is a special case of one of the rules which I proved to preserve Pauli flow and so it also preserves Pauli flow, but it is not as simple in the case of gflow. I find a condition that is both sufficient and necessary for neighbour unfusion to preserve the existence of gflow, along with providing less strict conditions for gflow to be preserved that can function as useful heuristics in their algorithm.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):