© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2207.09368 · Quantum

Shadow Pauli Flow: Characterising Determinism in MBQCs involving Pauli Measurements

Mehdi Mhalla, Simon Perdrix, Luc Sanselme

Published Jul 16, 2026• 1 citation

Abstract

We introduce a new characterisation of determinism in Measurement-Based Quantum Computing (MBQC). The one-way model consists in performing local measurements over a large entangled state represented by a graph. The ability to perform an overall deterministic computation requires a correction strategy because of the non-determinism of each measurement. The existence of such a correction strategy depends on the underlying open graph, which is a description of the resource state together with the basis of the performed measurements. GFlow is a well-known graphical characterisation of robust determinism in MBQC when every measurement is performed in some specific planes of the Bloch sphere. While Pauli measurements are ubiquitous in MBQC, GFlow fails to be necessary for determinism when a measurement-based quantum computation involves Pauli measurements. Pauli Flow was designed as a generalisation of GFlow to handle MBQC with Pauli measurements, and guarantees robust determinism, however, it has been shown more recently that it fails to be a necessary condition. Our contribution is twofold. First, we demonstrate that Pauli flow is actually necessary for robust determinism in a weaker sense: given an open graph, i.e. a resource state, a deterministic computation can be driven iff it has a Pauli flow. However, the Pauli flows do not reflect all the possible correction strategies over a particular resource state, and properties like measurement order or computational depth are not necessarily reflected by a Pauli flow. Thus, to characterise determinism in full generality, we introduce a further extension called Shadow Pauli Flow that we prove necessary and sufficient for robust determinism: An MBQC is robustly deterministic if and only if its correction strategy is consistent with a Shadow Pauli flow. Furthermore, we show that Shadow Pauli flow can be computed in polynomial time.

DOI: 10.22331/q-2026-07-16-2163

Related papers

Outcome determinism in measurement-based quantum computation with qudits

Robert I. Booth, Aleks Kissinger, Damian Markham +2 more

Abstract In measurement-based quantum computing (MBQC), computation is carried out by a sequence of measurements and corrections on an entangled state. Flow, and related concepts, are powerful techniques for characterising the dependence of the corrections on previous measurement outcomes. We introduce flow-based methods for MBQC with qudit graph states, which we call Z d -flow, when the local dimension is an odd prime. Our main results are a proof that Z d -flow is a necessary and sufficient condition for a strong form of outcome determinism. Along the way, we find a suitable generalisation of the concept of measurement planes to this setting and characterise the allowed measurements in a qudit MBQC. We also provide a polynomial-time algorithm for finding an optimal Z d -flow whenever one exists.

arXiv:2109.13810•Journal of Physics A Mathematical and Theoretical•Feb 9, 2023•6 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

Pauli Flow on Open Graphs with Unknown Measurement Labels

Piotr Mitosek

One-way quantum computation, or measurement-based quantum computation, is a universal model of quantum computation alternative to the circuit model. The computation progresses by measurements of a pre-prepared resource state together with corrections of undesired outcomes via applications of Pauli gates to yet unmeasured qubits. The fundamental question of this model is determining whether computation can be implemented deterministically. Pauli flow is one of the most general structures guaranteeing determinism. It is also essential for polynomial time ancilla-free circuit extraction. It is known how to efficiently determine the existence of Pauli flow given an open graph together with a measurement labelling (a choice of measurements to be performed). In this work, we focus on the problem of deciding the existence of Pauli flow for a given open graph when the measurement labelling is unknown. We show that this problem is in RP by providing a random polynomial time algorithm. To do it, we extend previous algebraic interpretations of Pauli flow, by showing that, in the case of X and Z measurements only, flow existence corresponds to the right-invertibility of a matrix derived from the adjacency matrix. We also use this interpretation to show that the number of output qubits can always be reduced to match the number of input qubits while preserving the existence of flow.

arXiv:2408.06059•Electronic Proceedings in Theoretical Computer Science•Aug 9, 2024•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

Finding gflow on unlabelled open graphs

Miriam Backens, Victor Gasse, Piotr Mitosek +1 more

The one-way model of measurement-based quantum computing implements computations via successive adaptive single-qubit measurements on a resource graph state. This model has practical applications, particularly in photonics, and it is also useful as a theoretical tool e.g. for optimisation. Gflow is a necessary and sufficient condition for implementing certain one-way computations deterministically (in a suitable sense); it is also used in efficient translations from the one-way model to quantum circuits. For a computation on $n$ qubits, a gflow can be found in $\mathcal{O}(n^3)$ time. Here, we consider an incompletely specified computation given by an unlabelled open graph: the graph state as well as the input and output qubits are known, but the measurements have not yet been fixed. We give an algorithm that identifies a measurement labelling and a compatible gflow, and runs in $\mathcal{O}(n^3)$, strictly generalising the previous approach. The new algorithm can also handle restrictions on the order of the measurements and returns only solutions compatible with these constraints. We additionally prove that if an open graph has equal numbers of inputs and outputs, it has at most one labelling compatible with gflow; and show how to identify additional inputs for an open graph that does not yet have the maximal number, without breaking an existing gflow.

quant-pharXiv:2609.40099•Oct 1, 2026•0 citations

An algebraic formulation of Pauli flow, leading to faster flow-finding algorithms

Piotr Mitosek, Miriam Backens

Abstract The one-way model of quantum computation is an alternative to the circuit model. A one-way computation is driven entirely by successive adaptive measurements of a pre-prepared entangled resource state. For each measurement, only one outcome is desired; hence a fundamental question is whether some intended measurement scheme can be performed in a robustly deterministic way. So-called flow structures witness robust determinism by providing instructions for correcting undesired outcomes. Pauli flow is one of the broadest of these structures and has been studied extensively. 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. We simplify these definitions by providing a new algebraic formulation of Pauli flow. This involves defining two matrices arising from the adjacency matrix of the underlying graph: the flow-demand matrix M and the order-demand matrix N . We show that Pauli flow exists if and only if there is a right inverse C of M such that the product NC forms the adjacency matrix of a directed acyclic graph. From the newly defined algebraic formulation, we obtain O ( n 3 ) algorithms for finding Pauli flow, improving on the previous O ( n 4 ) bound for finding generalised flow, a weaker variant of flow, and O ( n 5 ) bound for finding Pauli flow. We also introduce a first lower bound for the Pauli flow-finding problem, by linking it to the matrix invertibility and multiplication problems over F 2 .

arXiv:2410.23439•Journal of Physics A Mathematical and Theoretical•Dec 8, 2025•1 citation

We introduce a new characterisation of determinism in Measurement-Based Quantum Computing (MBQC). The one-way model consists in performing local measurements over a large entangled state represented by a graph. The ability to perform an overall deterministic computation requires a correction strategy because of the non-determinism of each measurement. The existence of such a correction strategy depends on the underlying open graph, which is a description of the resource state together with the basis of the performed measurements. GFlow is a well-known graphical characterisation of robust determinism in MBQC when every measurement is performed in some specific planes of the Bloch sphere. While Pauli measurements are ubiquitous in MBQC, GFlow fails to be necessary for determinism when a measurement-based quantum computation involves Pauli measurements. Pauli Flow was designed as a generalisation of GFlow to handle MBQC with Pauli measurements, and guarantees robust determinism, however, it has been shown more recently that it fails to be a necessary condition. Our contribution is twofold. First, we demonstrate that Pauli flow is actually necessary for robust determinism in a weaker sense: given an open graph, i.e. a resource state, a deterministic computation can be driven iff it has a Pauli flow. However, the Pauli flows do not reflect all the possible correction strategies over a particular resource state, and properties like measurement order or computational depth are not necessarily reflected by a Pauli flow. Thus, to characterise determinism in full generality, we introduce a further extension called Shadow Pauli Flow that we prove necessary and sufficient for robust determinism: An MBQC is robustly deterministic if and only if its correction strategy is consistent with a Shadow Pauli flow. Furthermore, we show that Shadow Pauli flow can be computed in polynomial time.

Abstract In measurement-based quantum computing (MBQC), computation is carried out by a sequence of measurements and corrections on an entangled state. Flow, and related concepts, are powerful techniques for characterising the dependence of the corrections on previous measurement outcomes. We introduce flow-based methods for MBQC with qudit graph states, which we call Z d -flow, when the local dimension is an odd prime. Our main results are a proof that Z d -flow is a necessary and sufficient condition for a strong form of outcome determinism. Along the way, we find a suitable generalisation of the concept of measurement planes to this setting and characterise the allowed measurements in a qudit MBQC. We also provide a polynomial-time algorithm for finding an optimal Z d -flow whenever one exists.

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.

One-way quantum computation, or measurement-based quantum computation, is a universal model of quantum computation alternative to the circuit model. The computation progresses by measurements of a pre-prepared resource state together with corrections of undesired outcomes via applications of Pauli gates to yet unmeasured qubits. The fundamental question of this model is determining whether computation can be implemented deterministically. Pauli flow is one of the most general structures guaranteeing determinism. It is also essential for polynomial time ancilla-free circuit extraction. It is known how to efficiently determine the existence of Pauli flow given an open graph together with a measurement labelling (a choice of measurements to be performed). In this work, we focus on the problem of deciding the existence of Pauli flow for a given open graph when the measurement labelling is unknown. We show that this problem is in RP by providing a random polynomial time algorithm. To do it, we extend previous algebraic interpretations of Pauli flow, by showing that, in the case of X and Z measurements only, flow existence corresponds to the right-invertibility of a matrix derived from the adjacency matrix. We also use this interpretation to show that the number of output qubits can always be reduced to match the number of input qubits while preserving the existence of 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 of measurement-based quantum computing implements computations via successive adaptive single-qubit measurements on a resource graph state. This model has practical applications, particularly in photonics, and it is also useful as a theoretical tool e.g. for optimisation. Gflow is a necessary and sufficient condition for implementing certain one-way computations deterministically (in a suitable sense); it is also used in efficient translations from the one-way model to quantum circuits. For a computation on

n

qubits, a gflow can be found in

\mathcal{O}(n^3)

time. Here, we consider an incompletely specified computation given by an unlabelled open graph: the graph state as well as the input and output qubits are known, but the measurements have not yet been fixed. We give an algorithm that identifies a measurement labelling and a compatible gflow, and runs in

\mathcal{O}(n^3)

, strictly generalising the previous approach. The new algorithm can also handle restrictions on the order of the measurements and returns only solutions compatible with these constraints. We additionally prove that if an open graph has equal numbers of inputs and outputs, it has at most one labelling compatible with gflow; and show how to identify additional inputs for an open graph that does not yet have the maximal number, without breaking an existing gflow.

Abstract The one-way model of quantum computation is an alternative to the circuit model. A one-way computation is driven entirely by successive adaptive measurements of a pre-prepared entangled resource state. For each measurement, only one outcome is desired; hence a fundamental question is whether some intended measurement scheme can be performed in a robustly deterministic way. So-called flow structures witness robust determinism by providing instructions for correcting undesired outcomes. Pauli flow is one of the broadest of these structures and has been studied extensively. 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. We simplify these definitions by providing a new algebraic formulation of Pauli flow. This involves defining two matrices arising from the adjacency matrix of the underlying graph: the flow-demand matrix M and the order-demand matrix N . We show that Pauli flow exists if and only if there is a right inverse C of M such that the product NC forms the adjacency matrix of a directed acyclic graph. From the newly defined algebraic formulation, we obtain O ( n 3 ) algorithms for finding Pauli flow, improving on the previous O ( n 4 ) bound for finding generalised flow, a weaker variant of flow, and O ( n 5 ) bound for finding Pauli flow. We also introduce a first lower bound for the Pauli flow-finding problem, by linking it to the matrix invertibility and multiplication problems over F 2 .