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/0603072

A complete algorithm to find flows in the one-way measurement model

Niel de Beaudrap

Published Mar 8, 2006• 6 citations
arXivHTMLPDF

Abstract

This article is the complement to [quant-ph/0611284], which proves that flows (as introduced by [quant-ph/0506062]) can be found efficiently for patterns in the one-way measurement model which have non-empty input and output subsystems of the same size. This article presents a complete algorithm for finding flows, and a proof of its' correctness, without assuming any knowledge of graph-theoretic algorithms on the part of the reader. This article is a revised version of [quant-ph/0603072v2], where the results of [quant-ph/0611284] also first appeared.

DOI
10.48550/arxiv.quant-ph/0603072

Related papers

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•25 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 extremal result for geometries in the one-way measurement model

Niel de Beaudrap, Martin Pei

We present an extremal result for the class of graphs $G$ which (together with some specified sets of input and output vertices, $I$ and $O$) have a certain ``flow'' property introduced by Danos and Kashefi for the one-way measurement model of quantum computation. The existence of a flow for a triple $(G,I,O)$ allows a unitary embedding to be derived from any choice of measurement bases allowed in the one-way measurement model. We prove an upper bound on the number of edges that a graph $G$ may have, in order for a triple $(G,I,O)$ to have a flow for some $I, O \subseteq V(G)$, in terms of the number of vertices in $G$ and $O$. This implies that finding a flow for a triple $(G,I,O)$ when $\lvert I \rvert = \lvert O \rvert = k$ (corresponding to unitary transformations in the measurement model) and $\lvert V(G) \rvert = n$ can be performed in time $O(k^2 n)$, improving the earlier known bound of $O(km)$ given in \cite{B06a}, where $m = \lvert E(G) \rvert$.

arXiv:quant-ph/0702229•Quantum Information and Computation•May 1, 2008•8 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

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

Comments on quant-ph/0609176

Wu, XiaoDi

In this note, we show the mistake which has been made in quant-ph/0609176. Further more, we provide a sketch of proof to show the impossibility of the effort of such kind toward improving the efficiency of Grover's Algorithm.

arXiv:quant-ph/0701035•Jan 8, 2007•0 citations
This article is the complement to [quant-ph/0611284], which proves that flows (as introduced by [quant-ph/0506062]) can be found efficiently for patterns in the one-way measurement model which have non-empty input and output subsystems of the same size. This article presents a complete algorithm for finding flows, and a proof of its' correctness, without assuming any knowledge of graph-theoretic algorithms on the part of the reader. This article is a revised version of [quant-ph/0603072v2], where the results of [quant-ph/0611284] also first appeared.
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.
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 nnn qubits, a gflow can be found in O(n3)\mathcal{O}(n^3)O(n3) 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 O(n3)\mathcal{O}(n^3)O(n3), 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.
We present an extremal result for the class of graphs GGG which (together with some specified sets of input and output vertices, III and OOO) have a certain ``flow'' property introduced by Danos and Kashefi for the one-way measurement model of quantum computation. The existence of a flow for a triple (G,I,O)(G,I,O)(G,I,O) allows a unitary embedding to be derived from any choice of measurement bases allowed in the one-way measurement model. We prove an upper bound on the number of edges that a graph GGG may have, in order for a triple (G,I,O)(G,I,O)(G,I,O) to have a flow for some I,O⊆V(G)I, O \subseteq V(G)I,O⊆V(G), in terms of the number of vertices in GGG and OOO. This implies that finding a flow for a triple (G,I,O)(G,I,O)(G,I,O) when ∣I∣=∣O∣=k\lvert I \rvert = \lvert O \rvert = k∣I∣=∣O∣=k (corresponding to unitary transformations in the measurement model) and ∣V(G)∣=n\lvert V(G) \rvert = n∣V(G)∣=n can be performed in time O(k2n)O(k^2 n)O(k2n), improving the earlier known bound of O(km)O(km)O(km) given in \cite{B06a}, where m=∣E(G)∣m = \lvert E(G) \rvertm=∣E(G)∣.
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.
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 .