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

arXiv:2607.03250

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

Miriam Backens

quant-phSubmitted Jul 3, 2026• Announced Jul 6, 2026• 0 citations• Revised Jul 21, 2026 (v2)
v1 · Jul 3, 2026v2 · Jul 21, 2026
arXivHTMLPDF

Abstract

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.

Comments
19 pages, v2 fixes an issue in the generation procedure

Related papers

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

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

Inserting Planar-Measured Qubits into MBQC Patterns while Preserving Flow

Miriam Backens, Thomas Perez

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.

arXiv:2508.14671•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•0 citations

Working with measurement-based computations on qudits

Piotr Mitosek, Miriam Backens

Measurement-based quantum computing is a universal model of quantum computation in which successive product measurements of an entangled resource state drive the computation. The non-deterministic nature of measurements necessitates adaptivity to ensure an overall deterministic computation. Flow structures characterise cases in which such an adaptive correction procedure is possible. Recently, flow has been defined in a setting where the resource states are prime-dimensional qudit graph states rather than the usual qubit graph states. Yet, this qudit flow definition is more burdensome to work with than analogous definitions for qubits. Here, we give a simpler definition of qudit flow and consider various useful properties of this flow, drawing on results for the qubit case. In particular, we show how to focus qudit flow and argue that focused flow is canonical. We improve the previous algebraic formulation to capture focused flow and use it to obtain an $O(n^3)$ flow-finding algorithm (where $n$ is the number of qudits), matching the best known complexity for qubit flows and improving on the previous $O(n^4)$ result for qudits. Furthermore, we explore multiple flow-preserving transformations, thus opening a pathway to using flow for optimisation. These transformations include pivoting, removal and insertion of certain types of vertices, and reversibility of flow. Lastly, we propose an algorithmic approach to generating large qudit computations with flow, for testing or machine learning.

quant-pharXiv:2606.30525•Jun 30, 2026•0 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
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.
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.
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.
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.
Measurement-based quantum computing is a universal model of quantum computation in which successive product measurements of an entangled resource state drive the computation. The non-deterministic nature of measurements necessitates adaptivity to ensure an overall deterministic computation. Flow structures characterise cases in which such an adaptive correction procedure is possible. Recently, flow has been defined in a setting where the resource states are prime-dimensional qudit graph states rather than the usual qubit graph states. Yet, this qudit flow definition is more burdensome to work with than analogous definitions for qubits. Here, we give a simpler definition of qudit flow and consider various useful properties of this flow, drawing on results for the qubit case. In particular, we show how to focus qudit flow and argue that focused flow is canonical. We improve the previous algebraic formulation to capture focused flow and use it to obtain an O(n3)O(n^3)O(n3) flow-finding algorithm (where nnn is the number of qudits), matching the best known complexity for qubit flows and improving on the previous O(n4)O(n^4)O(n4) result for qudits. Furthermore, we explore multiple flow-preserving transformations, thus opening a pathway to using flow for optimisation. These transformations include pivoting, removal and insertion of certain types of vertices, and reversibility of flow. Lastly, we propose an algorithmic approach to generating large qudit computations with flow, for testing or machine learning.
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.