Relating Measurement Patterns to Circuits via Pauli Flow

There are numerous approaches to quantum computation that differ in how problems are encoded and how the system evolves over time. The one-way model [32] is a variant of Measurement-Based Quantum Computing (MBQC) where the inputs are embedded into a general graph state, and the chosen computation is specified by a sequence of single-qubit measurements to apply, consuming the state and inducing a desired output state on the remaining qubits. In contrast, the gate-based model[30] applies unitary gates from some universal gateset to the input qubits directly. Gate-based circuits may use ancilla qubits and measurements, though they are only necessary for expanding to a larger state space for outputs and reading out final data.

There is a wide literature on rewriting both measurement patterns [17, 33, 18] and circuits [26, 19, 22, 35, 3, 12] to reduce the resource cost. Of particular interest here is the use of graph-theoretic rewrites of ZX-diagrams (in close correspondence with measurement patterns [17]) by Kissinger and van de Wetering [22], and of representations focussed on sequences of rotations about Pauli tensors such as by Zhang and Chen [35] herein referred to as Pauli Dependency DAGs (PDDAGs) as they capture the temporal dependencies between these rotations. Both works presented these as techniques for $T$ gate reduction with identical performance. The extraction method in this paper maps a measurement pattern/ZX-diagram directly into the form of a PDDAG, allowing us to formally demonstrate that each of the graph-theoretic rewrites can be simulated by moving Clifford-angled rotations through the PDDAG. This complements existing work on deriving equivalences between the PathSum formalism and the ZH calculus [5, 4, 24] and between different graphical calculi [29, 23] which have shown to provide useful insight on the semantics of operations for the more abstract calculi.

Previous work in this area has given algorithms for extracting circuits from measurement patterns that satisfy flow properties which describe how the errors from unwanted measurement outcomes can be corrected using the stabilizers of the graph state [8, 6]. The weakest such property that allows for interesting (i.e. non-Pauli) measurements is generalised flow (gflow) for which the single-plane form exactly describes the set of patterns that are uniformly, strongly, and stepwise deterministic [10]. Pauli flow [10] weakens the uniformity condition by labelling some of the measurements as being in a Pauli basis rather than at some arbitrary angle in a plane of the Bloch sphere. This allows for more interesting corrections that make use of Pauli projections to absorb some terms of the graph state stabilizers. This paper directly extends the works of Mhalla and Perdrix [28] and Backens et al. [6] for gflow to handle this wider class of measurement patterns.

This paper starts by laying out the key definitions and concepts behind measurement patterns and existing results on causal flow and gflow in Section 2. Section 3 will give a short overview of the Pauli Dependency DAG structure and how it can be used to rewrite circuits. We will then introduce the notion of Pauli flow and decompose the circuit extraction problem to generate a procedure that works for any measurement pattern with Pauli flow in Section 4. Then Section 5 will cover a number of methods of rewriting measurement patterns in turn and investigate their effects on the PDDAG extracted to show how they can be simulated.

The one-way model follows the typical structure of MBQC of building some resource state which is then consumed by single-qubit measurements. The particular resource considered is a graph state, constructed by matching qubits (inputs and ancillas prepared in the $\ket{+}=\tfrac{1}{\sqrt{2}}\left(\ket{0}+\ket{1}\right)$ state) with vertices in a graph, and entangling them (with a $CZ$ gate) according to the edges. Measurements are generally non-deterministic so, in order to have a deterministic effect overall, local gates can be applied to the remaining qubits to counteract the difference between the projectors for each outcome, giving the net effect of post-selecting the desired outcome. The introduction of such correction gates can be viewed as adapting the choice of basis for the future measurements.

Single qubit measurements are characterised by the bases they project into, which themselves can be described by a vector in the Bloch sphere. For MBQC, we conventionally restrict measurements into a plane of the Bloch sphere spanned by two of the Pauli bases. Such planar measurement bases are described by the following for $\alpha\in\left[0,2\pi\right)$:

with the following special cases for Pauli measurements for $\alpha=a\pi$ ($a\in\{0,1\}$):

For any measurement basis, the negative outcome at angle $\alpha$ is equivalent to the positive outcome at angle $\alpha+\pi$. We usually treat the positive measurement outcome as the desired branch, i.e. the projector we want to apply to achieve our desired end state.

Formally, measurement patterns (i.e. MBQC programs) are defined as follows:

The intended branch of a measurement pattern (where all measurement outcomes are $0$ and hence no corrections are required) can be summarised by a tuple $(\Gamma,\alpha)$ of a labelled open graph $\Gamma$ describing the entanglement and measurement planes, and an assignment of measurement angles $\alpha:\overline{O}\to\left[0,2\pi\right)$.

Each branch (combination of measurement outcomes) gives rise to a linear map from the inputs to the outputs based on the commands run and the projections observed. The overall channel from considering all branches is a completely-positive trace-preserving map whose Kraus maps are exactly the branch maps. When we have a strongly deterministic pattern (all branches are equal up to global phase), we just associate it with the linear map of the intended branch. Since runnable patterns can be standardised to perform all initialisations first, then all entangling gates, and finally alternate measurements and corrections, this linear map also has a standard representation.

Interpreting the graph state as $E_{G}N_{\overline{I}}$ gives rise to a stabilizer per initialised vertex $u\in\overline{I}$:

Since the linear map of a pattern is not just a simple graph state but a projected graph state, it is possible for some Pauli terms introduced by graph state stabilizers to be absorbed by the Pauli projections:

These stabilizers and Pauli absorptions are practical for deriving possible means of correcting for unwanted measurement outcomes.

The intention behind different types of flow conditions is to capture the ability to propagate errors from unwanted measurement outcomes forward to the rest of the circuit in order to correct them, aiming for stepwise determinism (each measurement can be corrected independently). Causal flow is the simplest case where we suppose all vertices are measured in the $XY$ basis and each error can be corrected by considering a single stabilizer of the graph state.

The idea here is that $Z_{v}$ from the graph stabilizer $\left(\prod_{w\in N_{G}(f(v))}Z_{w}\right)X_{f(v)}$ will eliminate the effect of the measurement error on qubit $v$, meaning we can correct the error by applying $\left(\prod_{w\in N_{G}(f(v))\setminus\{v\}}Z_{w}\right)X_{f(v)}$ and implicitly invoking the stabilizer. The partial order $\prec$ indicates a required order of the measurements, ensuring that none of the vertices required for correcting $v$ have been measured yet.

Generalised flow takes a similar approach, but allows us to take combinations of the basic stabilizers. If the stabilizer of a candidate $f(v)$ would require a $Z$ correction on some $u\in N_{G}(f(v))$ that has already been measured, there may exist some other stabilizer we can apply that cancels out the $Z$ for us. Now, instead of the stabilizer being determined by a single vertex $f(v)\in\overline{I}$, we have a set $g(v)\subseteq\overline{I}$ giving $\left(\prod_{w\in\mathrm{Odd}(g(v))}Z_{w}\right)\left(\prod_{w\in g(v)}X_{w}\right)$ up to phase. By relaxing these restrictions on the stabilizers used, we can also generate $Y$ or $X$ on the measured vertex, allowing the correction of measurements in the $XZ$ and $YZ$ planes respectively.

There exist polynomial-time algorithms for identifying whether or not a labelled open graph admits causal flow or gflow [15, 28, 6], and for extracting an equivalent unitary circuit for the measurement pattern given either type of flow [8, 6].

The Pauli Dependency DAG is a data structure for representing the action of a pure quantum circuit that abstracts away gate set, Clifford gates, and gate commutations. This was notably covered in the work of Zhang and Chen [35] where it was used to identify possible pairs of $T$ gates which could be merged through some sequence of gate commutations and Clifford gate relations in order to reduce the number of $T$ gates in the circuit. Similar structures are also covered by Litinski [25] for compiling circuits for lattice surgery and by Gosset et al. [20] as an intermediate for synthesis of Clifford+$T$ circuits.

The Clifford group is the group of linear maps that can be formed from $CX$, Hadamard, and $RZ(\tfrac{\pi}{2})$ with qubit initialisation in the $\ket{0}$ state. These hold a special place in quantum theory as the maximal group of actions under which the Pauli group is closed. Their behaviour is conveniently captured by the stabilizer framework, allowing for canonical representations like the stabilizer tableau [34, 2]. They are often viewed as the “easy” gates in a circuit because of their simple algebra, efficient simulation [21, 2], and low resource cost in many error correction schemes [11].

Most common gate types can be expressed as (combinations of) Pauli exponentials ($e^{i\theta P}$ for some $P\in\{I,X,Y,Z\}^{\otimes n}$), which also benefit from elegant relations with stabilizers.

Pauli exponentials where the coefficient is an integral multiple of $\tfrac{\pi}{4}$ correspond to Clifford gates. The action of Clifford gates on both Paulis and arbitrary Pauli exponentials can be summarised in a few equations.

We can represent any circuit as a set of qubit initialisations followed by a sequence of Pauli exponentials by decomposing each gate in turn. The above rules can then be used to move any Clifford-angled exponentials to the start of the circuit, resulting in the product form $\left(\prod_{k}e^{i\phi_{k}A_{k}}\right)\mathcal{C}$ where $\mathcal{C}$ is a stabilizer process and each $\phi_{k}$ is not an integral multiple of $\tfrac{\pi}{4}$. Previous presentations [25, 35] collected the Clifford gates at the end of the circuit rather than at the start. When considering unitary circuits, the choice of direction is arbitrary, but in the general case we may not always be able to transport qubit initialisations through the Pauli exponentials to the end.

$\mathcal{C}$ can be expressed canonically by its stabilizer tableau. Specifically, since we could have an arbitrary number of inputs we need a variant mixing the extremes of the unitary case [2] and the usual state case [34] to capture both how Paulis over the inputs are transformed to Pauli strings over the outputs and additional generators for free stabilizers over the outputs. In examples, we will describe this by the stabilizers of the Choi operator of $\mathcal{C}$ (which we shall refer to as an isometry tableau for clarity), from which it is simple to convert it to any binary matrix format of choice. Such tableaux can be identified and synthesised by embedding them into unitary tableaux by breaking down the isometry into an initialisation of $|O|-|I|$ qubits in the $\ket{0}$ state followed by a unitary circuit which maps $Z$ on the initialised qubits to each of the free output stabilizers and $X$ to any choice of operators that extend our generators to span the full Pauli group. Since the rows are just generators for the stabilizer group, we still have the notion of “free actions” given by reordering rows or multiplying two rows together.

For the rotation list, there is still some obvious redundancy in the product form resulting from commutations. Because anticommuting Pauli strings prevent commutation of their exponentials, any valid ordering of the rotations will preserve the relative order of rotations with anticommuting strings, inducing a temporal dependency between them. Taking the transitive closure of these dependencies gives a partial order between the exponentials which represents $\prod_{k}e^{i\phi_{k}A_{k}}$ up to any number of commutations.

Since the full $\prec$ relation is rather large, we use the minimal representation/Hasse diagram which includes edges in the DAG for immediate successors (those pairs of exponentials whose strings anticommute and could appear adjacent to one another in some valid topological ordering).

Rewrite rules for PDDAGs change the structure but preserve the linear map. The most useful rewrite for circuit reduction is rotation merging: two nodes in the graph $j,k$ can be merged to give a single node with $(A_{j},\alpha_{j}+\alpha_{k})$ if $A_{j}=A_{k}$ and both $j\not\prec k$ and $k\not\prec j$ (i.e. there is some valid topological ordering of the graph which puts these rotations together).

The PDDAG definition permits Clifford-angled rotations, allowing the movement of Clifford rotations through the circuit via the 3.2 to be an explicit rewrite. Combining this with merging/splitting of phases and eliminating rotations with angle $0$ permits a more rigid canonical form where the range of angles for each rotation is reduced from $\left[0,2\pi\right)$ to $\left(0,\tfrac{\pi}{2}\right)$.

When the initial Clifford process includes some qubit initialisations, it will have some free stabilizers over its outputs that can be used to change the Pauli strings of rotations in the DAG using the 3.1. We can use the 3.2 to propagate the stabilizers beyond the initial rotations to find more places to perform this rewrite. Changing the Pauli strings of rotations in this way can affect how they commute/anticommute with their neighbours, modifying the dependency relation $\prec$.

Extracting a circuit back out of an arbitrary PDDAG can be naively done by synthesising the stabilizer tableau [2, 27] and each of the Pauli exponentials in turn according to some topological ordering using some standard decompositions [7, 12] although this will typically add an extremely high amount of redundant Clifford gates. More efficient synthesis can be performed using techniques for synthesising pairs of rotations simultaneously [12] or by diagonalising sets of mutually commuting rotations [9, 13]. It is also possible that future architectures may find efficient ways to perform each Pauli rotation natively or employ lattice surgery where it is practical to just perform them directly [25].

Alternatively, similar to the action of phase teleportation in ZX-diagram rewriting [22], one can also retain the structure of a circuit and just use the PDDAG structure to spot where non-adjacent gates can be merged via the rotation merging rewrites. This is typically good when the original circuit already has a relatively low density of Clifford gates when it is unlikely that resynthesis will give as efficient a circuit structure.

The goal of circuit extraction is to identify a sequence of gates that implements the same linear map as a given measurement pattern. Simply calculating the linear map and using standard matrix decomposition techniques is not sufficient since it will scale exponentially with the size of the pattern, making it impractical in the long-run. The method presented here will make use of a Pauli flow to determine the effect that each measurement angle has on the outputs. Doing so will yield the PDDAG representation directly, giving a rotation per planar measurement and a stabilizer process.

To motivate our method, recall the possible measurement bases from Section 2. Each planar basis projection can be constructed as a basic rotation of some Pauli basis:

The key idea driving this method of circuit extraction is to apply the 3.1 to alter these rotations and move them to onto the output qubits, but this requires identifying an appropriate stabilizer of the graph state to use. In a similar way, flow conditions already describe stabilizers for propagating errors onto other qubits. Pauli flow is one such example which can handle both planar measurements $\lambda(v)\in\{XY,XZ,YZ\}$ and special cases for Pauli measurements $\lambda(v)\in\{X,Y,Z\}$. Similar to gflow, it gives a stabilizer that applies a Pauli $X$ to vertices in $p(v)$ and a Pauli $Z$ to vertices in $\mathrm{Odd}(p(v))$. However, because Equation 5 means Pauli corrections have no observable effect if the qubit is measured in the same basis, it doesn’t matter if, for example, a vertex $u\in p(v)$ with $\lambda(u)=X$ has already been measured before $v$.

Relating this definition to the goal of using the 3.1, the cases for $P^{\bot v}$ match the rotations in Equation 10. The fact that the rest of the stabilizer is over the outputs means we are successfully removing it from the scope of the pattern. For the purposes of extraction, we can assume all measurement angles of future vertices have already been extracted, making them Pauli projections. The notion of a focussed flow [28, 6] then guarantees that all Pauli terms are absorbed, leaving something in the form of an extraction string.

To make this extraction technique practical, we need to be able to find a focussed Pauli flow when one exists. This follows similarly to the corresponding results for causal flow and gflow.

We are now in the position where we can take any Pauli flow and extract all of the planar measurement angles from a measurement pattern. This just leaves a Clifford process which can be characterised completely by stabilizer theory. The rows of the isometry tableau describing how inputs are mapped are given by extraction strings of the inputs (taking input extensions of the measurement pattern as appropriate), and the remaining generators over the outputs are obtained from extraction strings.

The most common rewrites in PDDAGs are merging terms and moving Clifford rotations, most notably moving a Clifford phase between a node in the DAG and the initial Clifford process. The structure or redundancy being exploiting for optimisation is very clear and easy to understand. On the other hand, graph-theoretic rewrites used for measurement patterns or ZX-diagrams have less obvious interpretations in how they relate to optimisations in the gate-based model. To compare the two, we consider extracting a PDDAG from a measurement pattern before and after a rewrite to observe the changes in the order, Pauli strings, and phases of the rotations from each measurement or tableau row, and then find a sequence of simple PDDAG rewrites that produces the same effect. Detailed proofs and examples can be found in Appendix D.

Given the special treatment of Pauli measurements in our representation of measurement patterns, the simplest rewrite we can do is to relabel a vertex measured in a Pauli basis between a planar label and a Pauli label, without changing the graph or other vertices.

Removing vertices from the measurement pattern typically involves reducing a vertex’s measurement to the $Z$ basis, at which point it no longer needs to be entangled with the other qubits. We can consider doing this both when the vertex is labelled as a Pauli $Z$ measurement and as a planar measurement in the $XZ$ or $YZ$ planes.

Here, we have a slightly different effect for planar labels compared to the Pauli $Z$ label, though this can be thought of as a combination of the previous rewriting rule and the basic case for Pauli $Z$ elimination. The additional rotations generated are exactly the $Z$ gates introduced on neighbouring qubits to preserve the semantics (Lemma D.6).

One of the more interesting rewrites on measurement patterns is performing local complementation about some vertex $u$. This inverts the connectivity between each pair of vertices neighbouring $u$. To preserve the semantics, we also update the labels and measurement angles of $u$ and its neighbours. Combining this with $Z$ vertex elimination allows the elimination of vertices measured in the $Y$ basis.

Another similar operation to local complementation is the act of pivoting a diagram about an edge, which can be used to prepare a Pauli $X$ measurement for elimination. This action can be decomposed into a sequence of local complementations about each end of the edge, so this can also be simulated by some sequence of Clifford transformations in the PDDAG.

In each of the above, we assume that a particular transformation is made to the focussed Pauli flow and focussed sets for the measurement pattern based on the rewrite chosen, as detailed in Appendix D. In truth, focussed Pauli flows need not be unique for a measurement pattern. We can view the map between focussed Pauli flows as a rewrite on the measurement pattern that changes the corrections applied after each measurement, keeping the labelled open graph and measurement angles the same. We can compare the differences to the focussed sets for the pattern to obtain our final correspondence theorem:

An interesting consequence of this result is the uniqueness of focussed Pauli flow for unitary patterns (up to weakening of the partial order), since there are no free stabilizers with which to apply the 3.1.

We have investigated the significance of Pauli flow in the extraction of gate-based reversible circuits from measurement patterns, demonstrating that it is sufficient. This weakens the requirements for circuit extraction from universal measurement patterns compared to previous results. The principal contributions are a polynomial-time algorithm for identifying a Pauli flow for a measurement pattern (if one exists) and using this to construct an equivalent circuit without using ancillas or measurements.

The subsequent investigation using this map formally demonstrated that the effects of common graph-theoretic rewrites on measurement patterns/ZX-diagrams can be simulated via movement of Clifford rotations in a Pauli Dependency DAG. We know that the reverse simulation must be possible from the completeness of the ZX-calculus.

There are a number of possible avenues for future development regarding the topics of this paper:

• •

  The simulation of rewrites demonstrates that ZX-calculus and PDDAGs can perform equivalent effects, but analysis of the computational complexities is needed to determine preferences for practical usage such as the actual data structure of choice for quantum circuit compilation. This will be heavily dependent on the choice of the graph structure used in each case and how this can capture the dependency relation in the PDDAG.

• •

  Given a PDDAG (or generic gate-based circuit), the work here provides some practical constraints on Pauli flows that any equivalent measurement pattern should admit. This could give rise to a reverse construction to find a minimal measurement pattern for a given PDDAG, allowing for explicit simulations for any PDDAG rewrite in measurement patterns.

• •

  The flexibility of the PDDAG structure could be extended by incorporating measurements, discards or decoherence, conditional gates, and more elaborate rewrites aiming for completeness for deciding circuit equivalence.