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:2109.13810 · Journal of Physics A Mathematical and Theoretical

Outcome determinism in measurement-based quantum computation with qudits

Robert I. Booth, Aleks Kissinger, Damian Markham, Clément Meignant, Simon Perdrix

Published Feb 9, 2023• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1751-8121/acbace

Related papers

Flow conditions for continuous variable measurement-based quantum computing

Robert I. Booth, Damian Markham

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 results. We introduce flow-based methods for quantum computation with continuous-variable graph states, which we call CV-flow. These are inspired by, but not equivalent to, the notions of causal flow and g-flow for qubit MBQC. We also show that an MBQC with CV-flow approximates a unitary arbitrarily well in the infinite-squeezing limit, addressing issues of convergence which are unavoidable in the infinite-dimensional setting. In developing our proofs, we provide a method for converting a CV-MBQC computation into a circuit form, analogous to the circuit extraction method of Miyazaki et al, and an efficient algorithm for finding CV-flow when it exists based on the qubit version by Mhalla and Perdrix. Our results and techniques naturally extend to the cases of MBQC for quantum computation with qudits of prime local dimension.

arXiv:2104.00572•Quantum•Oct 19, 2023•9 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•Electronic Proceedings in Theoretical Computer Science•Jun 30, 2026•2 citations

Shadow Pauli Flow: Characterising Determinism in MBQCs involving Pauli Measurements

Mehdi Mhalla, Simon Perdrix, Luc Sanselme

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.

arXiv:2207.09368•Quantum•Jul 16, 2026•13 citations

Generalized flow and determinism in measurement-based quantum computation

Dan E. Browne, Elham Kashefi, Mehdi Mhalla +1 more

We extend the notion of quantum information flow defined by Danos and Kashefi (2006 Phys. Rev. A 74 052310) for the one-way model (Raussendorf and Briegel 2001 Phys. Rev. Lett. 86 910) and present a necessary and sufficient condition for the stepwise uniformly deterministic computation in this model. The generalized flow also applied in the extended model with measurements in the ( X , Y ), ( X , Z ) and ( Y , Z ) planes. We apply both measurement calculus and the stabiliser formalism to derive our main theorem which for the first time gives a full characterization of the stepwise uniformly deterministic computation in the one-way model. We present several examples to show how our result improves over the traditional notion of flow, such as geometries (entanglement graph with input and output) with no flow but having generalized flow and we discuss how they lead to an optimal implementation of the unitaries. More importantly one can also obtain a better quantum computation depth with the generalized flow rather than with flow. We believe our characterization result is particularly valuable for the study of the algorithms and complexity in the one-way model.

arXiv:quant-ph/0702212•New Journal of Physics•Aug 2, 2007•156 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•4 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•7 citations
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 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 results. We introduce flow-based methods for quantum computation with continuous-variable graph states, which we call CV-flow. These are inspired by, but not equivalent to, the notions of causal flow and g-flow for qubit MBQC. We also show that an MBQC with CV-flow approximates a unitary arbitrarily well in the infinite-squeezing limit, addressing issues of convergence which are unavoidable in the infinite-dimensional setting. In developing our proofs, we provide a method for converting a CV-MBQC computation into a circuit form, analogous to the circuit extraction method of Miyazaki et al, and an efficient algorithm for finding CV-flow when it exists based on the qubit version by Mhalla and Perdrix. Our results and techniques naturally extend to the cases of MBQC for quantum computation with qudits of prime local dimension.
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.
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.
We extend the notion of quantum information flow defined by Danos and Kashefi (2006 Phys. Rev. A 74 052310) for the one-way model (Raussendorf and Briegel 2001 Phys. Rev. Lett. 86 910) and present a necessary and sufficient condition for the stepwise uniformly deterministic computation in this model. The generalized flow also applied in the extended model with measurements in the ( X , Y ), ( X , Z ) and ( Y , Z ) planes. We apply both measurement calculus and the stabiliser formalism to derive our main theorem which for the first time gives a full characterization of the stepwise uniformly deterministic computation in the one-way model. We present several examples to show how our result improves over the traditional notion of flow, such as geometries (entanglement graph with input and output) with no flow but having generalized flow and we discuss how they lead to an optimal implementation of the unitaries. More importantly one can also obtain a better quantum computation depth with the generalized flow rather than with flow. We believe our characterization result is particularly valuable for the study of the algorithms and complexity in the one-way model.
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 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.