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:quant-ph/0506062 · Physical Review A

Determinism in the one-way model

Vincent Danos, Elham Kashefi

Published Nov 8, 2006• 158 citations
arXivHTMLPDF

Abstract

We introduce a flow condition on open graph states (graph states with inputs and outputs) which guarantees globally deterministic behavior of a class of measurement patterns defined over them. Dependent Pauli corrections are derived for all such patterns, which equalize all computation branches, and only depend on the underlying entanglement graph and its choice of inputs and outputs. The class of patterns having flow is stable under composition and tensorization, and has unitary embeddings as realizations. The restricted class of patterns having both flow and reverse flow supports an operation of adjunction, and has all and only unitaries as realizations.

DOI
10.1103/physreva.74.052310

Related papers

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

Phase map decompositions for unitaries

Niel de Beaudrap, Vincent Danos, Elham Kashefi

We propose a universal decomposition of unitary maps over a tensorial power of C^2, introducing the key concept of "phase maps", and investigate how this decomposition can be used to implement unitary maps directly in the measurement-based model for quantum computing. Specifically, we show how to extract from such a decomposition a matching entangled graph state (with inputs), and a set of measurements angles, when there is one. Next, we check whether the obtained graph state verifies a "flow" condition, which guarantees an execution order such that the dependent measurements and corrections of the pattern yield deterministic results. Using a graph theoretic characterization of flows, we can determine whether a flow can be constructed for a graph state in polynomial time. This approach yields an algorithmic procedure which, when it succeeds, may produce an efficient pattern for a given unitary.

arXiv:quant-ph/0603266•Mar 29, 2006•17 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

Finding flows in the one-way measurement model

Niel de Beaudrap

The one-way measurement model is a framework for universal quantum computation in which algorithms are partially described by a graph $G$ of entanglement relations on a collection of qubits. A sufficient condition for an algorithm to perform a unitary embedding between two Hilbert spaces is for the graph $G$, together with input and output $\mathit{I}$, $\mathit{O}$ vertices $I,O\ensuremath{\subseteq}V(G)$, to have a flow in the sense introduced by Danos and Kashefi [Phys. Rev. A 74, 052310 (2006)]. For the special case of $|I|=|O|$, using a graph-theoretic characterization, I show that such flows are unique when they exist. This leads to an efficient algorithm for finding flows by a reduction to solved problems in graph theory.

arXiv:quant-ph/0611284•Physical Review A•Feb 29, 2008•35 citations

Geometry-based signal shifting of one-way quantum computation measurement patterns

Maryam Eslamy, Mahboobeh Houshmand, Morteza Saheb Zamani +1 more

In one-way quantum computation (1WQC) model, an initial highly entangled state called a graph state is used to perform universal quantum computations by a sequence of adaptive single-qubit measurements and post-measurement Pauli-X and Pauli-Z corrections. The needed computations are organized as measurement patterns or simply patterns in the 1WQC model. The entanglement operations in a pattern can be shown by a graph which together with the set of its input and output qubits is called the geometry of the pattern. Causal flow is a sufficient condition to identify a dependency structure for measurement sequences in order to obtain determinism. Signal shifting is an optimization technique which uses a set of rewrite rules to propagate the Pauli-Z corrections on the measured qubits to the end of patterns. However, automatically applying these rules has difficulties for implementation and is time consuming due to using many ineffective commutation rules. To overcome this problem, in this paper, a new automatic approach is proposed to perform signal shifting on patterns with flows based on their geometries instead of using rewriting rules. It is shown that the time complexity of the proposed approach is improved compared to the previous ones.

Iranian Conference on Electrical Engineering•May 1, 2016•3 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•1 citation
We introduce a flow condition on open graph states (graph states with inputs and outputs) which guarantees globally deterministic behavior of a class of measurement patterns defined over them. Dependent Pauli corrections are derived for all such patterns, which equalize all computation branches, and only depend on the underlying entanglement graph and its choice of inputs and outputs. The class of patterns having flow is stable under composition and tensorization, and has unitary embeddings as realizations. The restricted class of patterns having both flow and reverse flow supports an operation of adjunction, and has all and only unitaries as realizations.
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.
We propose a universal decomposition of unitary maps over a tensorial power of C^2, introducing the key concept of "phase maps", and investigate how this decomposition can be used to implement unitary maps directly in the measurement-based model for quantum computing. Specifically, we show how to extract from such a decomposition a matching entangled graph state (with inputs), and a set of measurements angles, when there is one. Next, we check whether the obtained graph state verifies a "flow" condition, which guarantees an execution order such that the dependent measurements and corrections of the pattern yield deterministic results. Using a graph theoretic characterization of flows, we can determine whether a flow can be constructed for a graph state in polynomial time. This approach yields an algorithmic procedure which, when it succeeds, may produce an efficient pattern for a given unitary.
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.
The one-way measurement model is a framework for universal quantum computation in which algorithms are partially described by a graph GGG of entanglement relations on a collection of qubits. A sufficient condition for an algorithm to perform a unitary embedding between two Hilbert spaces is for the graph GGG, together with input and output I\mathit{I}I, O\mathit{O}O vertices $I,O\ensuremath{\subseteq}V(G)$, to have a flow in the sense introduced by Danos and Kashefi [Phys. Rev. A 74, 052310 (2006)]. For the special case of ∣I∣=∣O∣|I|=|O|∣I∣=∣O∣, using a graph-theoretic characterization, I show that such flows are unique when they exist. This leads to an efficient algorithm for finding flows by a reduction to solved problems in graph theory.
In one-way quantum computation (1WQC) model, an initial highly entangled state called a graph state is used to perform universal quantum computations by a sequence of adaptive single-qubit measurements and post-measurement Pauli-X and Pauli-Z corrections. The needed computations are organized as measurement patterns or simply patterns in the 1WQC model. The entanglement operations in a pattern can be shown by a graph which together with the set of its input and output qubits is called the geometry of the pattern. Causal flow is a sufficient condition to identify a dependency structure for measurement sequences in order to obtain determinism. Signal shifting is an optimization technique which uses a set of rewrite rules to propagate the Pauli-Z corrections on the measured qubits to the end of patterns. However, automatically applying these rules has difficulties for implementation and is time consuming due to using many ineffective commutation rules. To overcome this problem, in this paper, a new automatic approach is proposed to perform signal shifting on patterns with flows based on their geometries instead of using rewriting rules. It is shown that the time complexity of the proposed approach is improved compared to the previous ones.
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.