Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Rewriting Measurement-Based Quantum Computations with Generalised Flow

Ross Duncan, Simon Perdrix

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

Abstract. We present a method for verifying measurement-based quan-tum computations, by producing a quantum circuit equivalent to a given deterministic measurement pattern. We define a diagrammatic presenta-tion of the pattern, and produce a circuit via a rewriting strategy based on the generalised flow of the pattern. Unlike other methods for translat-ing measurement patterns with generalised flow to circuits, this method uses neither ancilla qubits nor acausal loops. In addition this method can detect errors in the correction strategy used to make the pattern deterministic. 1

Related papers

Relating Measurement Patterns to Circuits via Pauli Flow

Will Simmons

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.

arXiv:2109.05654•Electronic Proceedings in Theoretical Computer Science•Sep 9, 2021•18 citations

Completeness for flow-preserving rewrite rules

Miriam Backens, Simon Perdrix

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.

quant-pharXiv:2608.13035•Aug 14, 2026•0 citations

Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements

Tommy McElvanney, Miriam Backens

In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via measurements on some standard 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.Existing work on rewriting MBQC patterns while preserving the existence of flow has focused on rewrites that reduce the number of qubits.In this work, we show that introducing new Z-measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow.Furthermore, we give a unique canonical form for stabilizer ZX-diagrams inspired by recent work of Hu & Khesin [17].We prove that any MBQClike stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form using only rules which preserve the existence of Pauli flow, and that each of these rules can be reversed while also preserving the existence of Pauli flow.Hence we have complete graphical rewriting for MBQC-like stabilizer ZX-diagrams with Pauli flow.

arXiv:2205.02009•Electronic Proceedings in Theoretical Computer Science•Nov 14, 2023•9 citations

Generating one-way computations with flow: flow-preserving rewriting that ignores the interpretation

Miriam Backens

The one-way model is a universal model of quantum computation, driven by successive adaptive single-qubit measurements on an entangled resource state. Measurements are non-deterministic, yet if the computation satisfies one of several related families of conditions known as 'flows', the computation can be made deterministic overall by modifying later measurements depending on the outcomes of earlier ones. Flow properties also enable efficient translation from one-way computations to circuits, motivating research into rewriting one-way computations while preserving the existence of flow. Existing approaches to flow-preserving rewriting are used for compilation or optimisation and preserve both the interpretation and the existence of flow. Here, we broaden our perspective to consider flow-preserving rewriting that does not necessarily preserve the interpretation, with applications to creating test instances for software that works with flow, as well as to generating ansätze for quantum machine learning. We show that a family of just three flow-preserving rewrite rules suffices to generate any diagram with flow from a trivial diagram with the desired number of inputs and outputs. This rule set is nearly the same as the complete set of flow- and interpretation-preserving rewrite rules for one-way computations in which all measurements are Pauli; and just a small subset of the flow- and interpretation-preserving rewrite rules for arbitrary measurements.

quant-pharXiv:2607.03250•Jul 6, 2026•0 citations

Flow-preserving ZX-calculus Rewrite Rules for Optimisation and Obfuscation

Tommy McElvanney, Miriam Backens

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.

arXiv:2304.08166•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•8 citations

ZX-Flow: A Flexible Criterion for Deterministic Computation with ZX-Diagrams

Aleks Kissinger, John van de Wetering

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.

quant-pharXiv:2603.09580•Mar 11, 2026•0 citations
Abstract. We present a method for verifying measurement-based quan-tum computations, by producing a quantum circuit equivalent to a given deterministic measurement pattern. We define a diagrammatic presenta-tion of the pattern, and produce a circuit via a rewriting strategy based on the generalised flow of the pattern. Unlike other methods for translat-ing measurement patterns with generalised flow to circuits, this method uses neither ancilla qubits nor acausal loops. In addition this method can detect errors in the correction strategy used to make the pattern deterministic. 1
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.
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 some standard 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.Existing work on rewriting MBQC patterns while preserving the existence of flow has focused on rewrites that reduce the number of qubits.In this work, we show that introducing new Z-measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow.Furthermore, we give a unique canonical form for stabilizer ZX-diagrams inspired by recent work of Hu & Khesin [17].We prove that any MBQClike stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form using only rules which preserve the existence of Pauli flow, and that each of these rules can be reversed while also preserving the existence of Pauli flow.Hence we have complete graphical rewriting for MBQC-like stabilizer ZX-diagrams with Pauli flow.
The one-way model is a universal model of quantum computation, driven by successive adaptive single-qubit measurements on an entangled resource state. Measurements are non-deterministic, yet if the computation satisfies one of several related families of conditions known as 'flows', the computation can be made deterministic overall by modifying later measurements depending on the outcomes of earlier ones. Flow properties also enable efficient translation from one-way computations to circuits, motivating research into rewriting one-way computations while preserving the existence of flow. Existing approaches to flow-preserving rewriting are used for compilation or optimisation and preserve both the interpretation and the existence of flow. Here, we broaden our perspective to consider flow-preserving rewriting that does not necessarily preserve the interpretation, with applications to creating test instances for software that works with flow, as well as to generating ansätze for quantum machine learning. We show that a family of just three flow-preserving rewrite rules suffices to generate any diagram with flow from a trivial diagram with the desired number of inputs and outputs. This rule set is nearly the same as the complete set of flow- and interpretation-preserving rewrite rules for one-way computations in which all measurements are Pauli; and just a small subset of the flow- and interpretation-preserving rewrite rules for arbitrary measurements.
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.