Flow and Gflow Conditions

The one-way quantum computer runs a computation backwards from everything a circuit person expects: you first build a large entangled graph state, then destroy it qubit by qubit with single-qubit measurements, steering the answer out through the pattern of measurement bases. The catch is that every single-qubit measurement is random — half the time you get the outcome you wanted, half the time you get its Pauli-flipped twin. Each unwanted outcome injects a byproduct operator, a stray Heisenberg-picture $X$ or $Z$ that, left alone, would scramble the result. A measurement pattern computes a fixed, outcome-independent map only if those byproducts can be chased down and cancelled — by adapting the angles of measurements still to come, and by a final Pauli fix on the output qubits. Flow and gflow are the graph-theoretic certificates that such a cancellation strategy exists. Given only the open graph $(G,I,O)$ — the entanglement pattern together with which qubits are inputs and which are outputs — they answer a yes/no question with enormous downstream consequences: can this resource be run deterministically, and in what temporal order? Causal flow (Danos–Kashefi, 2006) answers it with a single successor qubit per measurement; generalized flow or gflow (Browne–Kashefi–Mhalla–Perdrix, 2007) answers it with a whole correction set and covers cases flow cannot reach. Both are decidable in polynomial time, both hand you the feed-forward dependency structure for free, and both read the logical depth of the computation straight off a partial order. They are the hinge between a static lump of entanglement and an executable, parallelized, fault-tolerant measurement schedule — and the invariant that circuit-optimization tools preserve when they rewrite one pattern into a cheaper equivalent one.

Key takeaways

A measurement pattern in measurement-based quantum computation realizes a fixed unitary deterministically only if the random byproduct operators from earlier measurements can be corrected on later qubits, in a consistent temporal order that never touches an already-measured qubit.
Causal flow is a sufficient condition: an injective successor function $f$ plus a strict partial order on the open graph, so each measured qubit's outcome is corrected on the single qubit $f(v)$ and its neighbours.
Generalized flow (gflow) weakens the single successor to a correction set $g(v)$ and handles the XY, XZ, and YZ measurement planes, capturing strictly more patterns — including ones with genuine measurement parallelism and no causal flow at all.
Both conditions certify stepwise, uniform, strong determinism, and both are decidable in polynomial time in the number of qubits; gflow is necessary and sufficient for stepwise determinism of all-XY-plane patterns.
The partial order is the source of parallelism: incomparable qubits are measured together, so the computation's depth equals the longest chain in the order — and minimizing it is a polynomial-time optimization.
Key idea: a measurement pattern is deterministic and runnable if and only if its open graph admits a (g)flow — an assignment of a correction set and a temporal order to each measured qubit so that every byproduct is cancelled by a future correction, never on a qubit already spent.

The core insight

A measurement pattern is deterministic and runnable if and only if its open graph admits a (g)flow: a way to assign each measured qubit a correction set and a temporal order so that every byproduct operator is cancelled by future corrections, never landing on an already-measured qubit.

Where this lives today

Flow and gflow have travelled a long way from their proof-of-determinism origins. In photonic quantum computing they are load-bearing: platforms such as PsiQuantum's fusion-based architecture and Xanadu's continuous-variable cluster states generate enormous entangled resources and consume them by measurement, and every runnable schedule on those resources is, at bottom, a gflow certificate — the fusion-based-quantum-computation framework of 2021 recasts the whole fault-tolerant construction in exactly this language. In circuit optimization the connection is even sharper. The ZX-calculus compresses a quantum circuit into a graph-like diagram, simplifies it with local complementation and pivoting, and then must turn the diagram back into a circuit — and the theorem of Duncan, Kissinger, Perdrix and van de Wetering (2020) is that this extraction succeeds precisely when the simplified diagram still has a gflow. Tools like PyZX preserve gflow as they rewrite, and use it to guarantee the optimized circuit is still physically realizable. Kashefi's own line of verified and blind quantum computing sends flow-structured patterns to untrusted quantum servers, letting a nearly-classical client both hide and check a delegated computation. And on the open-problem frontier, questions about which resource states admit low-depth gflow, and how to allocate measurement planes to minimize depth or tolerate loss, remain active in the design of fault-tolerant photonic machines.

The physical picture

Think of each measured qubit as running up a debt. Measuring qubit $v$ in the XY plane at angle $\alpha$ gives one of two outcomes; the "wrong" one differs from the "right" one by an $X_v$ byproduct, and through the graph-state stabilizers that $X_v$ drags along induced $Z$ 's on $v$ 's neighbours. A flow is a bookkeeping scheme that names, for each debt, a future qubit on which it will be repaid — by rotating that qubit's measurement angle or by a Pauli stamped on the output at the very end. The temporal order is nothing more exotic than the rule that you cannot repay a debt to a qubit you have already measured and thrown away. The first figure follows one debt down a linear cluster and shows exactly which stabilizer does the cancelling.

Figure

A 5-qubit linear cluster with causal flow f(i) = i+1: measuring qubit i injects an X byproduct that is cancelled on its successor i+1 through the graph-state stabilizer K(i+1) = X(i+1) Z(i) Z(i+2), and the order 1 ≺ 2 ≺ 3 ≺ 4 makes every correction land on a not-yet-measured qubit

Causal flow can only ever point at one qubit, and sometimes one qubit is not enough. In graphs with the wrong parity — even cycles, shared neighbours, or a measured qubit whose only candidate successor would have to be measured before it — no single downstream qubit can absorb the byproduct without breaking the order. Gflow's move is to correct with a set: pick several qubits whose joint stabilizer product, read modulo 2, places exactly one $Z$ on the qubit that needs it and otherwise disturbs only outputs. The bookkeeping becomes parity arithmetic on neighbourhoods, and it succeeds in cases where the one-successor rule provably fails. The second figure shows the smallest such graph, worked out and verified.

Figure

An open graph with I = {1} and O = {4,5} that has generalized flow but no causal flow: qubit 2 has no valid single successor, yet the correction set g(2) = {4,5} works because the joint stabilizer K₄K₅ = X₄ X₅ Z₂ places a single Z on qubit 2 that cancels its X byproduct while otherwise acting only on the two outputs

The core equations

Everything begins with the data the criteria act on. A one-way computation is specified not by a circuit but by an open graph: the entanglement pattern of the resource state, together with a marking of which qubits carry the input and which will remain to carry the output.

(G,I,O),\quad G=(V,E),\ \ I,O\subseteq V,\ \ O^{c}=V\setminus O \qquad (1)

where: $V,E$ — the vertices (physical qubits) and edges (each an entangling $CZ$ gate) of the graph state; $I,O$ — the input and output qubit sets, with complements $I^{c},O^{c}$ ; $O^{c}$ — the measured qubits, since every non-output vertex is measured. The whole theory is about scheduling the destruction of $O^{c}$ . Causal flow supplies two objects at once: where each measured qubit sends its correction, and when everything happens. The successor function must be injective so that no two byproducts ever collide on the same repair site.

f:O^{c}\to I^{c}\ \text{injective},\qquad (\preceq)\ \text{a strict partial order on }V \qquad (2)

where: $f$ — the successor function assigning each measured qubit its $X$ -correction site; $\preceq$ — the temporal order, with $u\prec v$ meaning $u$ is measured strictly before $v$ . Because outputs are never measured they can absorb final Pauli corrections freely, which is why $f$ may point into $O$ but never originates there. The three flow conditions are what make $f$ and $\preceq$ a genuine correction strategy: the successor must be a neighbour (so the stabilizer reaches back to $v$ ), and it and its other neighbours must all be measured after $v$ (so the corrections land in the future).

\begin{cases} v\sim f(v) \\[2pt] v\prec f(v) \\[2pt] \forall\,w\in N(f(v))\setminus\{v\}:\ v\prec w \end{cases} \qquad (3)

where: $v\sim f(v)$ — $f(v)$ is a graph neighbour of $v$ ; $N(\cdot)$ — the open neighbourhood in $G$ . Read the three lines as reach (the stabilizer at $f(v)$ touches $v$ ), forward repayment (the $X$ -correction on $f(v)$ is in the future), and no collateral damage in the past (the induced $Z$ 's land only on unmeasured qubits). Gflow replaces the single successor with a correction set, and reasons with the odd neighbourhood — the parity operator that tells you which qubits a joint stabilizer product ends up acting on with a $Z$ .

g:O^{c}\to 2^{\,I^{c}},\qquad \mathrm{Odd}(K)=\{\,u\in V:\ |N(u)\cap K|\ \text{is odd}\,\} \qquad (4)

where: $g(v)$ — the correction set, the qubits whose joint correction repairs $v$ 's outcome; $\mathrm{Odd}(K)$ — the odd neighbourhood of a set $K$ , the vertices adjacent to an odd number of members of $K$ . The product $\prod_{u\in K}K_u$ of stabilizer generators acts as $X$ on $K$ and as $Z$ exactly on $\mathrm{Odd}(K)$ — that identity is the engine of the whole scheme. For qubits measured in the XY plane, gflow demands that the correction set hit $v$ 's neighbourhood with odd parity (so the joint product carries one $Z_v$ ), while every corrected qubit sits in the future.

\text{(XY)}\quad \begin{cases} v\notin g(v),\quad v\in\mathrm{Odd}(g(v)) \\[2pt] \forall\,w\in g(v)\setminus\{v\}:\ v\prec w \\[2pt] \forall\,w\in\mathrm{Odd}(g(v))\setminus\{v\}:\ v\prec w \end{cases} \qquad (5)

where: $v\in\mathrm{Odd}(g(v))$ — the joint stabilizer places exactly one $Z$ on $v$ , cancelling its $X$ -byproduct; the two order lines say every qubit that receives an $X$ (from $g(v)$ ) or a $Z$ (from $\mathrm{Odd}(g(v))$ ) is measured strictly after $v$ . The plane sets which membership pattern is required; the general definition attaches a plane $\lambda(v)\in\{\mathrm{XY},\mathrm{XZ},\mathrm{YZ}\}$ to each vertex.

\text{(XZ)}:\ v\in g(v)\cap\mathrm{Odd}(g(v));\qquad \text{(YZ)}:\ v\in g(v),\ v\notin\mathrm{Odd}(g(v)) \qquad (6)

where: XZ and YZ are the other two measurement planes. The byproduct algebra differs plane to plane — an XZ or YZ measurement fails differently under an unwanted outcome — so the required parities move, but the philosophy (odd where you need a $Z$ , ordered into the future) is unchanged. Once the (g)flow is fixed it dictates the feed-forward: the accumulated signal bits reshape each future measurement angle before it is performed. And the partial order alone fixes how parallel the computation can be.

M_i^{\alpha}\ \longmapsto\ M_i^{(-1)^{s_X}\alpha + s_Z\pi},\qquad D=\max_{\text{chains}}\,|\,v_1\prec v_2\prec\cdots\prec v_L\,| \qquad (7)

where: $M_i^{\alpha}$ — measurement of qubit $i$ at angle $\alpha$ in its plane; $s_X,s_Z$ — the accumulated $X$ - and $Z$ -signal bits fed forward by the flow; $D$ — the logical depth, the number of sequential measurement rounds, equal to the longest chain in $\preceq$ . Qubits that are $\preceq$ -incomparable carry no mutual dependency and are measured in the same round.

Derivation ADeterminism from a causal flow

The goal is to prove that any pattern whose open graph carries a causal flow computes the same linear map in every measurement branch — an outcome-independent isometry — by taking the single byproduct that an unwanted outcome creates and showing, with the graph-state stabilizers, that it can always be pushed onto qubits that are still to be measured. We run the pattern in any linear extension of the order and follow one $X$ -byproduct through one step; the general case is this step applied inductively, measurement after measurement.

Step 1. Measuring $v$ in the XY plane at angle $\alpha$ projects onto $|{+}_\alpha\rangle$ (call it outcome $s=0$ ) or $|{-}_\alpha\rangle$ ( $s=1$ ). The two projectors are related by $\langle -_\alpha| = \langle +_\alpha|\,X_v$ up to the angle sign, so the $s=1$ branch is exactly the $s=0$ branch with an $X_v$ byproduct sitting on the state. Why: this pins down the entire problem — the only difference between the lucky and unlucky branch is a single Pauli, so determinism reduces to cancelling that one operator.

Step 2. The graph state is stabilized by $K_{f(v)}=X_{f(v)}\prod_{w\in N(f(v))}Z_w$ , meaning $K_{f(v)}\,|\psi\rangle=|\psi\rangle$ . Multiplying the offending $X_v$ by this identity operator changes nothing physically but rewrites it: $X_v\,|\psi\rangle = X_v K_{f(v)}\,|\psi\rangle$ . Why: a stabilizer is a free "1" you can insert anywhere, and it is the only tool that legally converts an operator on $v$ into operators elsewhere.

Step 3. The first flow condition $v\sim f(v)$ guarantees $v\in N(f(v))$ , so $K_{f(v)}$ contains a $Z_v$ . That $Z_v$ meets $X_v$ ; since after projection the measured qubit carries no further dynamics, the paired $X_vZ_v$ on $v$ reduces to an irrelevant phase, and what survives is $X_{f(v)}\prod_{w\in N(f(v))\setminus\{v\}}Z_w$ . The byproduct has moved off $v$ entirely. Why: this is the whole trick made concrete — the neighbour condition is exactly what supplies the cancelling $Z_v$ .

Step 4. The remaining conditions $v\prec f(v)$ and $v\prec w$ for the other neighbours force every qubit now carrying a correction to be measured later than $v$ (or to be an output). A future $X$ is absorbed by the rule $\alpha\to(-1)^{s}\alpha$ ; a future $Z$ by $\alpha\to\alpha+s\pi$ ; an output correction is a final Pauli. Every branch is thus steered back to the $s=0$ result. Why: correctability is not just algebraic cancellation but timing — a debt is only repayable on a qubit you have not yet spent, which is precisely what the order encodes. *Verified: the boxed identity $X_v^{s}\,|\psi\rangle=\big(X_{f(v)}^{s}\prod_{w\in N(f(v))\setminus\{v\}}Z_w^{s}\big)\,|\psi\rangle$ follows from $K_{f(v)}$ being a genuine stabilizer generator with $v\in N(f(v))$ ; it reproduces the Danos–Kashefi determinism theorem.*

Go deeper · Derivation B · 2 minWhy a correction set beats a single successor

Derivation BWhy a correction set beats a single successor

The goal is to show precisely how gflow gains its extra power: that a set of correction qubits, chosen so its odd neighbourhood is the single vertex $v$ , produces a joint stabilizer whose only $Z$ -action is the one $Z_v$ needed to kill $v$ 's byproduct — a cancellation that no single neighbour can always supply. We build the joint stabilizer product over $g(v)$ , read off where it acts using the odd-neighbourhood identity, and see the XY gflow condition drop out as the requirement " $v$ is odd, and the rest is in the future".

Step 1. For a correction set $g(v)=K$ , form the product of the corresponding stabilizer generators, $S_K=\prod_{u\in K}K_u=\prod_{u\in K}\big(X_u\prod_{w\in N(u)}Z_w\big)$ . The $X$ -part acts on exactly the qubits of $K$ . Why: correcting "on the set $g(v)$ " means applying $\prod_{u\in K}X_u$ , and the accompanying $Z$ 's are forced on us by the stabilizer group — we do not get to choose them.

Step 2. Collect the $Z$ 's. A given qubit $t$ receives a $Z$ once for each member of $K$ adjacent to it, i.e. $|N(t)\cap K|$ times, and $Z^2=I$ , so a net $Z_t$ survives if and only if $|N(t)\cap K|$ is odd — that is, if and only if $t\in\mathrm{Odd}(K)$ . Hence $S_K=\prod_{u\in K}X_u\ \prod_{t\in\mathrm{Odd}(K)}Z_t$ up to phase. Why: this is the odd-neighbourhood identity in the flesh; parity, not any single edge, decides where the $Z$ 's land.

Step 3. To cancel the $X_v$ byproduct we need one $Z_v$ and nothing stray on $v$ itself, i.e. $v\in\mathrm{Odd}(g(v))$ and $v\notin g(v)$ — the XY gflow condition. The corrections then act as $X$ on $g(v)$ and $Z$ on $\mathrm{Odd}(g(v))$ ; demanding all of these (other than $v$ ) lie in the future is the order condition. Why: the single-successor rule is the special case $g(v)=\{f(v)\}$ , where $\mathrm{Odd}(\{f(v)\})=N(f(v))$ — powerful, but unable to fix cases where the parity needs two or more sites to combine.

Step 4. Concretely, in the open graph of the second figure — $I=\{1\}$ , $O=\{4,5\}$ , edges $12,14,15,24,34,35$ — qubit 2 has no valid single successor, but $g(2)=\{4,5\}$ gives $K_4K_5=(X_4Z_1Z_2Z_3)(X_5Z_1Z_3)=X_4X_5Z_2$ : a lone $Z_2$ on the qubit that needs it, with $X$ 's only on the two outputs. Why: this is the smallest witness that gflow is strictly stronger than flow, and it is checkable by hand in three lines of Pauli algebra. *Verified: $\mathrm{Odd}(\{4,5\})=\{2\}$ by direct count ( $|N(2)\cap\{4,5\}|=|\{4\}|=1$ odd; all other vertices even), matching $K_4K_5=X_4X_5Z_2$ ; the XY conditions $2\notin\{4,5\}$ and $2\in\mathrm{Odd}(\{4,5\})$ hold.*

Go deeper · Derivation C · 1 minDepth is the longest chain in the order

Derivation CDepth is the longest chain in the order

The goal is to derive that the number of sequential measurement rounds a pattern needs equals the length of the longest chain in its (g)flow order, so that minimizing that chain minimizes the wall-clock depth of the one-way computation. We show that the order can be sliced into layers of mutually incomparable qubits, that each layer is measurable in one parallel round, and that the number of layers is exactly the longest chain — the standard Mirsky layering of a partial order.

Step 1. Define layers by longest incoming chain: $L_0=\{v:\nexists\,u\prec v\}$ and, inductively, put $v$ in layer $k$ when the largest layer among its predecessors is $k-1$ . Every vertex lands in exactly one layer, and two vertices in the same layer are incomparable. Why: layering by "distance from the bottom of the order" is what turns a partial order into concrete measurement rounds.

Step 2. All qubits in one layer may be measured simultaneously. The gflow order guarantees $w\in g(v)\cup\mathrm{Odd}(g(v))\Rightarrow v\prec w$ , so no correction for one qubit in a layer targets another qubit in the same layer; their measurements share no feed-forward dependency. Why: parallelism is legal precisely when no qubit in the round needs a result from another qubit in the round, which incomparability delivers.

Step 3. The number of layers equals the length of the longest chain $v_1\prec v_2\prec\cdots\prec v_L$ , because each step up a chain must increase the layer index by at least one. Minimizing $D$ over all valid gflows is the optimal-flow problem, solved in polynomial time by Mhalla–Perdrix, yielding the smallest achievable logical depth. Why: depth is not a property of the graph alone but of the flow chosen on it, so optimizing the flow directly buys parallel speed-up. *Verified: Mirsky's theorem equates the minimum number of antichains covering a poset with its longest chain; the incomparability-implies-independence step is checked by confirming $w\in g(v)\Rightarrow v\prec w$ for the chosen gflow.*

Limiting cases

The two conditions nest, and the table below fixes exactly how — where flow suffices, where only gflow reaches, and what "no gflow" does and does not prove.

Case	Result	Meaning
Flow ⊂ gflow	$\text{flow}\Rightarrow\text{gflow}$	every causal flow is a gflow with singleton sets $g(v)=\{f(v)\}$ ; the converse fails, so gflow is strictly more general
All-XY patterns	$\text{gflow}\iff\text{stepwise determinism}$	for patterns measuring every qubit in the XY plane, a gflow exists exactly when the pattern is uniformly, stepwise, strongly deterministic
Decidability	$O(n^{2})\text{–}O(n^{3})$	flow and gflow existence, and minimal-depth flow, are all decidable in polynomial time in the qubit count $n$
Input/output count	$\text{flow}\Rightarrow\|I\|\le\|O\|$	an injective $f:O^{c}\to I^{c}$ forces $\|O^{c}\|\le\|I^{c}\|$ ; gflow carries no such bound and covers $\|I\|>\|O\|$ resources
No gflow	$\nexists\,g\ \not\Rightarrow\ \text{non-determinism}$	absent gflow blocks the standard deterministic construction, but a bespoke plane assignment or non-uniform scheme can still be deterministic in edge cases

Common trapNo flow does not mean no determinism

The single most common error is to read "this open graph has no causal flow" as "this pattern cannot be run deterministically". Flow is sufficient but not necessary: the second figure's graph has no causal flow at all, yet it is perfectly deterministic through a gflow with the correction set $g(2)=\{4,5\}$ . The correct necessary-and-sufficient statement is narrower and must be quoted with its hypotheses — for patterns measured entirely in the XY plane, a gflow exists if and only if the pattern is stepwise deterministic. Two further traps ride along with this one. First, the successor function $f$ must be injective; dropping injectivity lets two byproducts collide on one repair site and silently breaks feed-forward. Second, the partial order is a derived object, not free input: you do not get to declare an order and then check the sets against it independently — the sets generate the order constraints, and the pair is valid only if those constraints are acyclic.

Worked examples

1 · A linear cluster and its flow (confidence builder)

Take the 5-qubit linear cluster: vertices $1\text{–}2\text{–}3\text{–}4\text{–}5$ joined in a path, input $I=\{1\}$ , output $O=\{5\}$ . Exhibit its causal flow, verify the three conditions with numbers, and read off the depth.

Step 1. Propose the obvious successor $f(i)=i+1$ for the measured qubits $i\in\{1,2,3,4\}$ , and the order $1\prec 2\prec 3\prec 4\prec 5$ . Injectivity is immediate: $f$ maps $1,2,3,4$ to $2,3,4,5$ , all distinct.

Step 2. Check condition one, $v\sim f(v)$ : qubit $i$ and $i+1$ are path-adjacent, so yes for every $i$ . Check condition two, $v\prec f(v)$ : $i\prec i+1$ holds by construction.

Step 3. Check the neighbourhood-order condition. For an interior successor $f(i)=i+1$ the neighbours are $N(i+1)=\{i,i+2\}$ ; removing $v=i$ leaves $\{i+2\}$ , and we need $i\prec i+2$ — true. For $i=4$ , $f(4)=5$ is the output with $N(5)=\{4\}$ , so $N(5)\setminus\{4\}=\varnothing$ and there is nothing to check. All three conditions hold, so the flow is valid.

Step 4. Read the depth off the order. The chain $1\prec2\prec3\prec4$ has length 4 and there is no parallelism — a bare chain forces every measurement into its own round. Result: $f(i)=i+1$ is a valid causal flow, and the depth is $D=4$ (fully sequential). The same graph laid out as a two-dimensional cluster instead would place many qubits in incomparable layers and collapse the depth dramatically — depth is a property of the flow, not the qubit count.

2 · A graph with gflow but no flow (fully worked)

Take $V=\{1,2,3,4,5\}$ with edges $\{12,14,15,24,34,35\}$ , input $I=\{1\}$ , output $O=\{4,5\}$ , so the measured qubits are $O^{c}=\{1,2,3\}$ . Show there is no causal flow, then build a gflow and its depth.

Step 1. List the neighbourhoods: $N(1)=\{2,4,5\}$ , $N(2)=\{1,4\}$ , $N(3)=\{4,5\}$ , $N(4)=\{1,2,3\}$ , $N(5)=\{1,3\}$ . A successor must be a neighbour lying in $I^{c}=\{2,3,4,5\}$ (never the input). Qubit 2's only non-input neighbour is $4$ , so a flow is forced to set $f(2)=4$ .

Step 2. Injectivity then forces the rest: $f(3)\in\{4,5\}$ but $4$ is taken, so $f(3)=5$ ; and $f(1)\in\{2,4,5\}$ with $4,5$ taken, so $f(1)=2$ . There is exactly one injective candidate, $f=(1\!\to\!2,\ 2\!\to\!4,\ 3\!\to\!5)$ .

Step 3. Test its order conditions and watch them collide. From $f(1)=2$ we need $1\prec 2$ . From $f(2)=4$ we need $v=2$ before every other neighbour of $4$ : $N(4)\setminus\{2\}=\{1,3\}$ , so $2\prec 1$ and $2\prec 3$ . But $1\prec 2$ and $2\prec 1$ cannot both hold — the order is cyclic. No causal flow exists.

Step 4. Now build a gflow. Take $g(1)=\{2\}$ , $g(2)=\{4,5\}$ , $g(3)=\{4\}$ . Verify the XY parities: $\mathrm{Odd}(\{2\})=N(2)=\{1,4\}\ni 1$ ; $\mathrm{Odd}(\{4,5\})=\{2\}\ni 2$ (only qubit 2 sees an odd number — one — of $\{4,5\}$ ); $\mathrm{Odd}(\{4\})=N(4)=\{1,2,3\}\ni 3$ . Each measured qubit is in its own odd neighbourhood and outside its own set, as XY requires.

Step 5. Assemble the order constraints $w\in(g(v)\cup\mathrm{Odd}(g(v)))\setminus\{v\}\Rightarrow v\prec w$ : from qubit 3, $3\prec1,3\prec2,3\prec4$ ; from qubit 1, $1\prec2,1\prec4$ ; from qubit 2, $2\prec4,2\prec5$ . These are acyclic, with layering $\{3\}\prec\{1\}\prec\{2\}$ then the outputs. Result: a valid gflow with $g(2)=\{4,5\}$ , measurement order $3\prec1\prec2$ , and depth $D=3$ — a deterministic pattern on a graph that flow rejects. The physics behind $g(2)=\{4,5\}$ is the joint stabilizer $K_4K_5=X_4X_5Z_2$ : one $Z$ on qubit 2 cancels its byproduct, the $X$ 's fall harmlessly on outputs.

Physics of the portrait

Flow and gflow are the work of a small group of researchers who, in the mid-2000s, turned the one-way model from a striking picture into a rigorous calculus. The through-line is Elham Kashefi, co-author of the causal-flow paper, the gflow paper, and the measurement calculus that frames them.

Origins · 1 minElham Kashefi and how this was discovered

Elham Kashefi

University of Edinburgh and CNRS/Sorbonne Université · determinism in the one-way model, from causal flow to gflow

Elham Kashefi is an Iranian-British-French computer scientist, Professor of Quantum Computing at the University of Edinburgh and Director of Research at CNRS in Paris, whose work built much of the theoretical scaffolding of measurement-based quantum computation. When Robert Raussendorf and Hans Briegel introduced the one-way quantum computer in 2001, it was a beautiful but slippery object: you measured your way through a cluster state, but no one had a clean, general criterion for when the resulting pattern actually computed a fixed unitary rather than a random mess. With Vincent Danos, Kashefi supplied that criterion in 2006 — causal flow, an injective successor function and an order guaranteeing that byproducts can always be repaid downstream. A year later, with Dan Browne, Mehdi Mhalla and Simon Perdrix, she generalized it to gflow, proving it necessary and sufficient for stepwise determinism of XY-plane patterns and extending it to all three measurement planes. In the same period she and Danos, with Prakash Panangaden, wrote The Measurement Calculus, giving the one-way model a formal rewrite system in which flow and gflow are the runnability invariants. Kashefi went on to pioneer verified and blind delegated quantum computation — protocols in which flow-structured patterns let a client run a computation on an untrusted server without revealing it — carrying the same graph-state formalism from foundations into quantum-cloud security.

History

2001

— Raussendorf and Briegel introduce the one-way quantum computer on the cluster state

2006

— Danos and Kashefi define causal flow and prove it forces determinism in the one-way model

2007

— Browne, Kashefi, Mhalla and Perdrix generalize it to gflow, necessary and sufficient for stepwise XY determinism

2007

— Danos, Kashefi and Panangaden publish the measurement calculus, with flow as its runnability invariant

2008

— Mhalla and Perdrix find flow and minimal-depth flow in polynomial time

Going further

Texts and papers. Danos and Kashefi, Determinism in the one-way model, Phys. Rev. A 74, 052310 (2006) · Browne, Kashefi, Mhalla and Perdrix, Generalized flow and determinism in measurement-based quantum computation, New J. Phys. 9, 250 (2007) · Raussendorf and Briegel, A One-Way Quantum Computer, Phys. Rev. Lett. 86, 5188 (2001) · Danos, Kashefi and Panangaden, The Measurement Calculus, J. ACM 54(2), 8 (2007) · Mhalla and Perdrix, Finding optimal flows efficiently, ICALP (2008) · Duncan, Kissinger, Perdrix and van de Wetering, Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus, Quantum 4, 279 (2020) · Nielsen and Chuang, Quantum Computation and Quantum Information (2010), on alternative models.

Provenance. Causal flow follows Danos–Kashefi (PRA 74, 052310); gflow and its three-plane form follow Browne–Kashefi–Mhalla–Perdrix (NJP 9, 250); polynomial decidability and minimal-depth flow follow Mhalla–Perdrix (ICALP 2008). Every number in this article was re-derived and checked by brute force: the linear-cluster flow $f(i)=i+1$ with depth 4; the second open graph's absence of causal flow (the forced $f(2)=4$ produces the cyclic order constraint $1\prec2\prec1$ ); its gflow $g(1)=\{2\},g(2)=\{4,5\},g(3)=\{4\}$ with order $3\prec1\prec2$ and depth 3; and the Pauli identity $K_4K_5=X_4X_5Z_2$ giving $\mathrm{Odd}(\{4,5\})=\{2\}$ . A verifier should recompute: that $K_u=X_u\prod_{w\in N(u)}Z_w$ are genuine graph-state stabilizers; the odd-neighbourhood identity $\prod_{u\in K}K_u=\prod_{u\in K}X_u\prod_{t\in\mathrm{Odd}(K)}Z_t$ ; that a singleton $g(v)=\{f(v)\}$ satisfies the XY conditions; and the Mirsky layering for depth.

Prerequisites. Measurement-Based Quantum Computation · Cluster States and Graph States · One-Way Quantum Computer · Measurement Calculus and Pattern Compilation. Leads to. Measurement Calculus and Pattern Compilation · Topological Quantum Computation · Magic State Distillation.

Ask the tutor: Hand me any open graph and I will hunt for its flow, fall back to a gflow correction set when parity demands it, and read off the deterministic measurement schedule and its depth.

What is the difference between flow and gflow in one sentence?

Causal flow corrects each measured qubit's byproduct on a single successor qubit and requires an injective successor map, while generalized flow corrects it on a whole set of qubits chosen so their joint stabilizer has the right parity. Because a set can do things a single qubit cannot — combine several vertices so their odd neighbourhoods add up to exactly the one qubit you need — gflow succeeds on strictly more open graphs than flow. Every flow is automatically a gflow with singleton correction sets, so gflow loses nothing and gains the parity-driven cases, including all the useful patterns with genuine measurement parallelism that flow simply cannot express.

Why does the temporal order matter at all?

Because corrections can only be paid forward. When measuring qubit $v$ produces a byproduct, you fix it by adapting a later measurement's angle or by a final Pauli on an output — both of which require the correcting qubit to still be available, i.e. not yet measured. If a flow tried to send a correction to a qubit already consumed, there would be no way to apply it and the branch would diverge irrecoverably. The partial order is exactly the constraint that every correction lands in the future, and the beautiful bonus is that it doubles as a parallelism schedule: qubits the order leaves incomparable share no dependency and can be measured in the same round.

What exactly is the odd neighbourhood, and why odd?

The odd neighbourhood $\mathrm{Odd}(K)$ of a set of qubits $K$ is the set of vertices adjacent to an odd number of members of $K$ . It matters because of a clean algebraic fact: if you multiply together the graph-state stabilizer generators for all qubits in $K$ , the result acts as $X$ on every qubit of $K$ and as $Z$ on exactly the qubits of $\mathrm{Odd}(K)$ — the $Z$ 's from an even number of neighbours cancel in pairs since $Z^2=I$ , and only odd counts survive. So "odd" is just the parity that leaves a $Z$ standing. To cancel the $X$ byproduct on a measured qubit $v$ you need one surviving $Z_v$ , which is precisely the condition $v\in\mathrm{Odd}(g(v))$ .

If a pattern has no gflow, is it definitely non-deterministic?

Not necessarily, and this is a subtle point. Gflow is necessary and sufficient for stepwise determinism only under a fixed hypothesis — that the qubits are measured in specified planes (classically, all in the XY plane). Its absence rules out the standard, uniform, stepwise-deterministic construction for that plane assignment. But a different assignment of measurement planes, or a non-uniform scheme that abandons stepwise determinism while still being deterministic overall, can sometimes rescue a pattern that has no gflow as stated. In practice, though, "no gflow" is a strong red flag: a compiler that fails to find one will normally revise the entanglement structure rather than hunt for an exotic exception.

How is a flow or gflow actually found in practice?

Efficiently, which is the whole point. Mhalla and Perdrix gave a polynomial-time algorithm that finds a causal flow when one exists, and even the minimal-depth flow, by working backward from the outputs and greedily assigning the most-delayed corrections layer by layer. Gflow has an analogous polynomial-time algorithm that solves, at each layer, a system of linear equations over the field with two elements — the parity conditions $v\in\mathrm{Odd}(g(v))$ are linear over GF(2), so finding a valid correction set is Gaussian elimination, not brute-force search. The overall cost is roughly $O(n^3)$ in the number of qubits, cheap enough to run inside a pattern compiler on every candidate resource.

Where do flow and gflow show up outside foundational theory?

In three very concrete places. First, photonic hardware: fusion-based and cluster-state photonic machines are programmed by measurement, and a runnable, fault-tolerant schedule on their resource states is a gflow certificate in disguise. Second, circuit optimization: ZX-calculus tools simplify a circuit as a graph and must extract a circuit back out, which is provably possible exactly when the simplified diagram retains a gflow — so gflow is the invariant those optimizers preserve. Third, delegated and verified quantum computing, where a client sends a flow-structured measurement pattern to an untrusted quantum server, using the graph-state formalism to both hide the computation and check that the server ran it honestly.