The one-way model of Measurement-Based Quantum Computing and the gate-based circuit model give two different presentations of how quantum computation can be performed. There are known methods for converting any gate-based quantum circuit into a one-way computation, whereas the reverse is only efficient given some constraints on the structure of the measurement pattern. Causal flow and generalised flow have already been shown as sufficient, with efficient algorithms for identifying these properties and performing the circuit extraction. Pauli flow is a weaker set of conditions that extends generalised flow to use the knowledge that some vertices are measured in a Pauli basis. In this paper, we show that Pauli flow can similarly be identified efficiently and that any measurement pattern whose underlying graph admits a Pauli flow can be efficiently transformed into a gate-based circuit without using ancilla qubits. We then use this relationship to derive simulation results for the effects of graph-theoretic rewrites in the ZX-calculus using a more circuit-like data structure we call the Pauli Dependency DAG.
The one-way model of Measurement-Based Quantum Computing and the gate-based circuit model give two different presentations of how quantum computation can be performed. There are known methods for converting any gate-based quantum circuit into a one-way computation, whereas the reverse is only efficient given some constraints on the structure of the measurement pattern. Causal flow and generalised flow have already been shown as sufficient, with efficient algorithms for identifying these properties and performing the circuit extraction. Pauli flow is a weaker set of conditions that extends generalised flow to use the knowledge that some vertices are measured in a Pauli basis. In this paper, we show that Pauli flow can similarly be identified efficiently and that any measurement pattern whose underlying graph admits a Pauli flow can be efficiently transformed into a gate-based circuit without using ancilla qubits. We then use this relationship to derive simulation results for the effects of graph-theoretic rewrites in the ZX-calculus using a more circuit-like data structure we call the Pauli Dependency DAG.
Diagrammatic reasoning via languages such as ZX Calculus is a powerful tool in theoretical quantum computing. However, physical quantum computers do not understand diagrams and require explicit quantum circuits as inputs. Finding a circuit equivalent to the given diagram is known as circuit extraction. Such problems in graphical calculi form a limitation preventing the wider adoption of diagrammatic reasoning. Computational complexity theory formalises the difficulty of problems. For ZX diagrams, the circuit extraction problem is #P-hard and unlikely to have an efficient algorithm. Therefore, partial solutions are critical. Currently, efficient circuit extraction is only possible for diagrams containing a structure of so-called Pauli flow. This structure is necessary and sufficient for robust determinism in measurement-based quantum computation (MBQC) – a model of quantum computation, an alternative to circuits, where adaptive single-qubit measurements drive computation. Thus, Pauli flow links MBQC, ZX Calculus, and the circuit model. It is known how to find flow structures in polynomial time when they exist; nevertheless, their lengthy and complex definitions often hinder working with them. In this thesis, I present contributions to two connected topics: the hardness of problems in graphical calculi and Pauli flow as a method for overcoming circuit extraction. First, I show that circuit extraction can be #P-hard for phase-free ZH diagrams, extending the previous result for ZX diagrams. I also establish a relation between phase-free ZH and NP⧣P class. This involves weakening the oracle, crafting a complete problem, and encoding the problem into phase-free ZH. My next contribution concerns Pauli flow. I simplify the Pauli flow definition by providing a new algebraic interpretation. This involves defining two matrices arising from the adjacency matrix of the underlying graph. Then, Pauli flow corresponds to the existence of a right-inverse of the first matrix, which, when multiplied by the second matrix, results in a matrix of a directed acyclic graph. Based on the newly defined algebraic interpretation, I obtain O(n3) algorithms for finding Pauli flow, improving on the previous O(n4) bounds. I also introduce a lower bound for Pauli flow-finding by linking it to linear algebra problems over F2. Finally, when given an unlabelled open graph, I show how to find measurement labelling resulting in Pauli flow.
Complete sets of graphical rewrite rules enable fully graphical reasoning about quantum computations and have been an area of active research for more than a decade. Many recent applications of the ZX-calculus have made use of the close correspondence between ZX-diagrams and computations in the one-way model of measurement-based quantum computation. In this model, various kinds of flow properties ensure deterministic implementability; for ZX-diagrams, these same properties allow efficient translation into quantum circuits (a problem that is known to be #P-hard in general). Therefore, flow-preserving ZX-calculus rewrite rules are of strong interest.
Here, we extend the set of flow-preserving rules appearing in the literature with a few new rules and extensions of existing rules. We then show that the resulting rule set is complete for all flow-preserving translations between ZX-diagrams of appropriate form. The proof employs a manifestly flow-preserving equivalent of circuit extraction, where a diagram with gflow is transformed, using only flow-preserving rewrite rules, into a diagram with causal flow.
In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via measurements on a resource state.So-called flow conditions ensure that the overall computation is deterministic in a suitable sense, with Pauli flow being the most general of these.Computations, represented as measurement patterns, may be rewritten to optimise resource use and for other purposes.Such rewrites need to preserve the existence of flow to ensure the new pattern can still be implemented deterministically.The majority of existing work in this area has focused on rewrites that reduce the number of qubits, yet it can be beneficial to increase the number of qubits for certain kinds of optimisation, as well as for obfuscation.In this work, we introduce several ZX-calculus rewrite rules that increase the number of qubits and preserve the existence of Pauli flow.These rules can be used to transform any measurement pattern into a pattern containing only (general or Pauli) measurements within the XY-plane.We also give the first flow-preserving rewrite rule that allows measurement angles to be changed arbitrarily, and use this to prove that the 'neighbour unfusion' rule of Staudacher et al. preserves the existence of Pauli flow.This implies it may be possible to reduce the runtime of their two-qubit-gate optimisation procedure by removing the need to regularly run the costly gflow-finding algorithm.
Flow criteria are used to efficiently extract computations, either in the form of measurement patterns or quantum circuits, from ZX-diagrams. Existing criteria such as causal flow, generalised flow, and Pauli flow, were all originally formulated for graph states, so they require ZX-diagrams to be in a very particular graph-state-like form. This form is easily broken by applying basic ZX rules and makes establishing some desirable properties very complicated. Here, we introduce a new "ZX-native" flow criterion called ZX-flow, formulated using a new type of decoration of a ZX-diagram we call Pauli semiwebs. These are a generalisation of Pauli webs, which have recently been used extensively in reasoning about fault-tolerant computations in the ZX-calculus. We show that ZX-flow is straightforwardly preserved by all Clifford rewrites and furthermore that a ZX-diagram has ZX-flow if and only if it is Clifford-equivalent to a graph-like ZX-diagram with Pauli flow. Finally, we show that any diagram with ZX-flow can be readily interpreted either as a deterministic measurement-based computation or as a Clifford isometry followed by a sequence of Pauli exponentials. The latter can then be efficiently extracted to a quantum circuit.
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.
In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via single-qubit measurements on a resource state.Flow conditions ensure that the overall computation is deterministic in a suitable sense, and are required for efficient translation into quantum circuits.Procedures that rewrite MBQC patterns -e.g. for optimisation, or adapting to hardware constraints -thus need to preserve the existence of flow.Most previous work has focused on rewrites that reduce the number of qubits in the computation, or that introduce new Pauli-measured qubits.Here, we consider the insertion of planar-measured qubits into MBQC patterns, i.e. arbitrary measurements in a plane of the Bloch sphere spanned by a pair of Pauli operators; such measurements are necessary for universal MBQC.We extend the definition of causal flow, previously restricted to XY -measurements only, to also permit Y Z-measurements and derive the conditions under which a Y Z-insertion preserves causal flow.Then we derive conditions for Y Z-insertion into patterns with gflow or Pauli flow, in which case the argument straightforwardly extends to XZ-insertions as well.We also show that the 'vertex splitting' or 'neighbour unfusion' rule previously used in the literature can be derived from Y Z-insertion and pivoting.This work contributes to understanding the broad properties of flow-preserving rewriting in MBQC and in the ZX-calculus more broadly, and it will enable more efficient optimisation, obfuscation, or routing.