Flows and determinism¶
Every measurement in MBQC has a random outcome, so a computation can unfold along many different branches. The key idea we saw in the introduction is that outcome-dependent Pauli corrections can “correct” this randomness. With the right corrections, the pattern implements the same transformation, up to a global phase, in every branch. This property is called strong determinism.
Strongly deterministic patterns realize unitary transformations, which makes them the MBQC counterpart of quantum circuits.
A central question in MBQC is which resource states can support a unitary pattern (or, more generally, an isometry, when the number of outputs exceeds the number of inputs, \(|O| > |I|\)). Put differently: given an open graph, is there a correction strategy that makes the computation strongly deterministic?
Previous work answers this with graph-theoretic criteria on labelled open graphs, known as flow conditions [BMBdF+21, BKMP07, MP08, MB26, Sim21]. There are different flavors of flows depending on the measurements of the open graph, but they all share the same structure. Each consists of:
a correction function, which maps each measured qubit to prepared qubits, and
a partial order on the nodes, which fixes the order in which measurements may be performed.
Whenever a flow exists, it can be found in polynomial time.
Causal flow¶
The simplest flow is the causal flow. It applies to open graphs in which every measurement lies in the \(\XYplane\) plane.
Causal flow [DK06]
An open graph \((G, I, O, \lambda: O^c \rightarrow \{\XYplane\})\) has causal flow if there exist a map \(c: O^c \rightarrow I^c\) and a strict partial order \(\prec\) over \(V\) such that, for every \(i \in O^c\):
(C1) \(i\) and \(c(i)\) are neighbors,
(C2) \(i \prec c(i)\),
(C3) \(i \prec j\) for every neighbor \(j \neq i\) of \(c(i)\).
Here \(O^c\) is the set of measured (non-output) nodes and \(I^c\) the set of prepared (non-input) nodes.
Graphix enables you to analyze the determinism of computations on open graphs and offers abstractions to represent flows. The following example shows how to extract and draw a causal flow from an open graph:
import networkx as nx
from graphix import Measurement, OpenGraph
og = OpenGraph(
graph=nx.Graph([(0, 2), (1, 3), (2, 3), (2, 4), (3, 5)]),
input_nodes=[0, 1],
output_nodes=[4, 5],
measurements={
0: Measurement.XY(0.1),
1: Measurement.XY(0.2),
2: Measurement.XY(0.3),
3: Measurement.XY(0.4)})
cf = og.to_causalflow()
print("Causal flow: ", cf)
cf.draw()
Causal flow: c(2) = {4}, c(3) = {5}, c(0) = {2}, c(1) = {3}; {0, 1} < {2, 3} < {4, 5}
The method OpenGraph.to_causalflow() runs in \(O(N^2)\) with \(N\) the number of nodes and returns a CausalFlow instance when the open graph has causal flow. If it doesn’t, it will raise an OpenGraphError exception. For convenience, there is the OpenGraph.to_causalflow_or_none() method which handles the exception and returns None.
We visualize flows similarly to XZ-correction maps: black arrows represent the flow’s correction function on the open graph. The nodes are arranged in layers that represent the flow’s partial order, from left to right.
Note
The layer numbering follows this convention:
Layer 0 holds the output nodes, if there are any.
Higher layers are measured first. If \(l_i < l_j\), every node in layer \(l_j\) is measured before the nodes in layer \(l_i\). In terms of the flow, this says that nodes in layer \(l_j\) precede nodes in layer \(l_i\) in the partial order \(\prec\).
From flows to computations¶
A flow does more than promise that a deterministic computation exists. It also gives a specific pattern implementing the computation itself. Concretely, a causal flow \((c, \prec)\) yields the following XZ-correction maps:
where \(N_G(j)\) is the neighborhood of node \(j\) in the open graph. From these, we can reconstruct a pattern:
Recall that we read patterns from right to left: we first prepare the non-input nodes, then entangle them according to the graph, and finally go through the measured nodes in the order given by \(\prec\). Each node is measured, and its outcome \(s_i\) is immediately used to correct the nodes \(c(i)\) and \(N_G(c(i)) \setminus \{i\}\).
Note
To see why these corrections make the pattern deterministic, notice that we can make a single measurement \(\M_i^{\XYplane,\alpha_i}\) deterministic by preceding it with a Pauli-\(Z\) correction \(\Z_i^{s_i}\). For example, for a one-qubit state \(\lvert\psi_0\rangle = a\lvert 0\rangle + b\lvert 1\rangle\), both outcomes give the same amplitude:
However, the correction \(\Z_i^{s_i}\) depends on the outcome of the measurement it precedes, which is not yet known, so it’s unphysical. The way out is that open graphs are partial stabilizer states:
where \(\E_G \N_{I^c} = \prod_{(i,j) \in E} \E_{ij} \prod_{i \in I^c} \N_i\).
Inserting the stabilizer \(K_{c(i)}^{s_i}\) makes the unphysical \(\Z_i^{s_i}\) cancel out and leaves a runnable pattern:
The first equality uses (4). The third one is where the flow conditions come in:
(C1) \(i \in N_G(c(i))\), so the stabilizer contains a \(\Z_i\) that cancels the unphysical \(\Z_i^{s_i}\).
(C2) \(c(i)\) is measured after \(i\), so \(\X_{c(i)}^{s_i}\) commutes past \(\M_i^{\XYplane,\alpha_i}\).
(C3) The nodes in \(N_G(c(i)) \setminus \{i\}\) are measured after \(i\), so \(\Z_{N_G(c(i)) \setminus \{i\}}^{s_i}\) also commutes past \(\M_i^{\XYplane,\alpha_i}\).
Repeating this for every measured node \(i \in O^c\), in the appropriate order, gives the pattern of (2).
Using (1), Graphix converts any flow into an XZCorrections object that holds
the X and Z corrections, and from there you can recover the corresponding deterministic Pattern:
xz_corr = cf.to_xzcorrections()
pattern = xz_corr.to_pattern()
xz_corr.draw()
print("Pattern: ", pattern)
Pattern: X(5,{3}) M(3,2pi/5) X(4,{2}) M(2,3pi/10) X(3,{1}) Z(5,{1}) Z(2,{1}) M(1,pi/5) X(2,{0}) Z(4,{0}) Z(3,{0}) M(0,pi/10) E(3,5) E(1,3) E(2,4) E(2,3) E(0,2) N(5) N(4) N(3) N(2)
Tip
to_pattern() bundles both steps (to_xzcorrections followed by to_pattern) into a single call.
Gflow and Pauli flow¶
Causal flow only covers measurements in the \(\XYplane\) plane. Once measurements can also lie in the \(\XZplane\) or \(\YZplane\) planes, strong determinism is characterized by the existence of a generalised flow, or gflow. Both causal flow and gflow guarantee strong determinism for any choice of measurement angles. This property is called robust determinism.
Whether a gflow exists depends on the relationship between the entanglement structure of the open graph, and the chosen measurement planes. Given an open graph, one can fix some measurement angles to Pauli angles, that is, integer multiples of \(\pi/2\). At these angles, a measurement belongs to two measurement planes at once. For example, an \(\XYplane\) measurement at angle \(0\) is also an \(\XZplane\) measurement. This extra freedom can be exploited to establish strong determinism even when no gflow exists. This more general setting is captured by the Pauli flow, which strictly generalizes gflow by taking advantage of these fixed Pauli measurements.
As with causal flow, gflow and Pauli flow also yield a specific deterministic correction strategy on the open graph. For the flow definitions and the ensuing corrections, see [BKMP07, UNG+26].
Graphix provides OpenGraph.to_gflow() and OpenGraph.to_pauliflow().
Both run in \(O(N^3)\), with \(N\) the number of nodes. They return a
GFlow or a PauliFlow instance, respectively, or raise an
OpenGraphError if the flow does not exist. The methods OpenGraph.to_gflow_or_none(), OpenGraph.to_pauliflow_or_none() handle the exception and return None if no flow exists.
For example:
import networkx as nx
from graphix import Measurement, OpenGraph
og = OpenGraph(
graph=nx.Graph([(0, 1), (0, 2), (0, 4), (1, 5), (2, 4), (2, 5), (3, 5)]),
input_nodes=[0, 1],
output_nodes=[4, 5],
measurements={
0: Measurement.XY(0.1),
1: Measurement.XY(0.1),
2: Measurement.XZ(0.2),
3: Measurement.YZ(0.3),
},
)
gf = og.to_gflow()
gf.draw()
Flow extraction algorithms don’t identify Pauli measurements. This means that if your open graph contains for instance an Measurement.XY(0), it will be treated as a planar measurement and not as a Pauli measurement PauliMeasurement.X. However, you can manually cast planar measurements with a Pauli angle into Pauli measurements with the method OpenGraph.infer_pauli_measurements(). This distinction can allow to extract a Pauli flow where a gflow does not exist or a flow with lower depth:
import networkx as nx
from graphix import Measurement, OpenGraph
og = OpenGraph(
graph=nx.Graph(
[(0, 1), (1, 2), (3, 4), (4, 5), (6, 7), (7, 8), (1, 3), (4, 6)]),
input_nodes=[0, 3, 6],
output_nodes=[2, 5, 8],
measurements=dict.fromkeys((0, 1, 3, 4, 6, 7), Measurement.XY(0)))
gf = og.to_gflow()
pf = og.infer_pauli_measurements().to_pauliflow()
gf.draw()
pf.draw()
The two plots share the same graph structure (nodes and dashed lines). Only the
correction function and the number of layers differ. If you skip the
Pauli-measurement inference and call og.to_pauliflow()
directly on the original open graph, you still get a PauliFlow
object. Its correction function and partial order, however, are identical
to those of the gflow. This is valid, because every gflow is also a
Pauli flow; it simply does not exploit the Pauli measurements.
Note
It follows from the flow definitions [BKMP07, UNG+26] that causal flows are a special case of gflows (with \(\XYplane\)-measurements only), and gflows are a special case of Pauli flows (with planar measurements only). Accordingly, CausalFlow is a subclass of GFlow, which is itself a subclass of PauliFlow.
Warning
Attempting to extract a gflow or a causal flow from an open graph that contains Pauli
measurements is not a valid operation. For instance,
og.infer_pauli_measurements().to_gflow() in the previous example fails
at runtime. The type checker mypy catches the mistake before you run
the code, because the inferred Pauli measurements have a different type.
To learn more, see the advanced tutorial on measurement types.
Both the gflow and the Pauli flow let us extract a deterministic pattern. Here the two correction functions differ, so the patterns differ too. However, they implement the same unitary transformation:
from numpy.random import default_rng
rng = default_rng(42)
pattern_gf = gf.to_pattern() # Equivalent to ``gf.to_xzcorrections().to_pattern()``
pattern_pf = pf.to_pattern()
# The "gflow pattern" has more commands:
assert len(pattern_gf) > len(pattern_pf)
# By default, the input state is |+++〉
state_gf = pattern_gf.simulate(rng=rng)
state_pf = pattern_pf.simulate(rng=rng)
assert state_gf.isclose(state_pf)
print(state_gf)
sqrt(2)/4(|000> + |001> + |010> + |011> + |100> + |101> + |110> + |111>)
This example shows an important property of open graphs: once the measurement angles are fixed, an open graph implements a single unitary, but many correction strategies can implement it. For a given open graph, the correction functions of gflow and Pauli flow are not unique.
Graphix extracts a valid correction function, not all of them. It does not currently support enumerating every correction function that exists on an open graph.
Robust determinism is uniform¶
Whether an open graph has a flow depends only on the measurement planes and axes assigned to its nodes, never on the specific value of an angle.
Note
This may look at odds with the previous section, where we said that fixing Pauli angles can make a Pauli flow possible even without a gflow. To be fully precise, angles matter only through whether they are Pauli:
A non-Pauli angle in a plane behaves like any other non-Pauli angle in that plane. Changing its value never changes whether a flow exists.
A Pauli angle places the measurement on an axis (\(\Xaxis\), \(\Yaxis\) or \(\Zaxis\)). That extra structure is what Pauli flow exploits, and an
Axisrecords it directly.
So the question “does a flow exist?” is answered by the planes and axes alone, without needing to know the continuous angle values.
This means we can extract flows from open graphs where measurements is
specified as a mapping from nodes to Plane or Axis, instead of
Measurement, and convert them to an XZCorrections instance:
import networkx as nx
from graphix import Axis, Plane, OpenGraph
og = OpenGraph(
graph=nx.Graph([(0, 2), (2, 4), (3, 4), (4, 6), (1, 4), (1, 6), (2, 3), (3, 5), (2, 6), (3, 6)]),
input_nodes=[0],
output_nodes=[5, 6],
measurements={
0: Plane.XY,
1: Plane.XZ,
2: Axis.Y,
3: Plane.XY,
4: Axis.Z},
)
pf = og.to_pauliflow()
xz_corr = pf.to_xzcorrections()
print(pf)
xz_corr.draw()
p(0) = {2, 3, 5}, p(1) = {1, 3, 5, 6}, p(2) = {3}, p(3) = {5}, p(4) = {4, 6}; {0, 1, 2, 4} < {3} < {5, 6}
Warning
Building a pattern requires the measurement angles, so calling
xz_corr.to_pattern() on the previous example is incorrect.
mypy flags it, and running it anyway produces a faulty Pattern (simulating this pattern will fail at runtime, for instance). If you don’t want to commit to concrete angle values yet, you can use parametric placeholders instead. They let you build the pattern now and assign the angles later.
Extracting flows from corrections¶
The previous examples showed how to go from a flow to its X and Z corrections.
Graphix also supports the opposite direction. Given a specific deterministic
correction strategy on an open graph, you can recover the flow it implements
with XZCorrections.to_causalflow(), XZCorrections.to_gflow(), and
XZCorrections.to_pauliflow().
These methods do not call the open-graph flow-finding algorithms. They read the flow’s correction function directly from the X and Z correction maps.
This is an important distinction: running a flow-finding algorithm on the open graph underlying your corrections returns a gflow or Pauli flow, not necessarily the one that produced them, because the flow of an open graph is not unique. The corrections derived from that flow may therefore differ from the original strategy. Extracting the flow from the corrections themselves avoids this ambiguity. We illustrate this effect in the example below:
import networkx as nx
from graphix import OpenGraph, Plane, XZCorrections
og = OpenGraph(
graph=nx.Graph([(0, 1), (1, 2), (2, 3)]),
input_nodes=[0],
output_nodes=[3],
measurements=dict.fromkeys(range(3), Plane.XY))
x_map = {0: {1}, 1: {2}, 2: {3}}
z_map = {0: {2}, 1: {3}}
xz_corr = XZCorrections.from_measured_nodes_mapping(og, x_map, z_map)
gf_from_xz = xz_corr.to_gflow() # Gflow from X and Z corrections
gf_from_og = xz_corr.og.to_gflow() # Gflow extraction algorithm on the open graph
# The flow correction functions differ!
print(gf_from_xz)
print(gf_from_og)
gf_from_xz.to_xzcorrections().draw() # Equal to the original ``xz_corr``
gf_from_og.to_xzcorrections().draw() # Different from the original
g(0) = {1}, g(1) = {2}, g(2) = {3}; {0} < {1} < {2} < {3}
g(0) = {1, 3}, g(1) = {2}, g(2) = {3}; {0} < {1} < {2} < {3}
Tip
Patterns have their own shortcuts, Pattern.to_causalflow(),
Pattern.to_gflow(), and Pattern.to_pauliflow(). Each one
extracts the X and Z corrections from the pattern and then recovers the flow
from them.
Going the other way, OpenGraph.to_pattern() is a convenient shorthand
for open graphs. It tries to find a flow and builds the pattern from it.
Building flows by hand¶
Most of the time you will obtain flows programmatically, from open graphs or patterns, as in the previous examples. However, you can also instantiate a flow directly by specifying its correction function and its partial order.
Graphix lets you represent flows that are not valid. To check one, call
CausalFlow.check_well_formed(), GFlow.check_well_formed(), or
PauliFlow.check_well_formed(). If the flow is not well formed, they raise
a FlowException that tells you exactly which condition is violated.
This can be useful when you are learning about flows and want to experiment, or when
you are designing a new flow-extraction algorithm.
import networkx as nx
from graphix import CausalFlow, OpenGraph, Plane
from graphix.flow.exceptions import FlowError
og = OpenGraph(
graph=nx.Graph([(0, 1), (1, 2), (2, 3)]),
input_nodes=[0],
output_nodes=[3],
measurements=dict.fromkeys(range(3), Plane.XY))
cf = CausalFlow(
og,
correction_function={0: {1}, 1: {2, 3}, 2: {3}},
partial_order_layers=({3}, {2}, {1}, {0}))
try:
cf.check_well_formed()
except FlowError as err:
print(err)
Correction set c(1) = {2, 3} has more than one element.
Tip
If you only need a yes-or-no answer, PauliFlow.is_well_formed() (and its
counterparts on the other flow classes) catches the exception and returns a
boolean.
References¶
Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering. There and back again: A circuit extraction tale. Quantum, 5:421, March 2021. URL: https://doi.org/10.22331/q-2021-03-25-421, doi:10.22331/q-2021-03-25-421.
Dan E. Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix. Generalized flow and determinism in measurement-based quantum computation. New Journal of Physics, 9(8):250, aug 2007. URL: https://dx.doi.org/10.1088/1367-2630/9/8/250, doi:10.1088/1367-2630/9/8/250.
Vincent Danos and Elham Kashefi. Determinism in the one-way model. Phys. Rev. A, 74:052310, Nov 2006. URL: https://link.aps.org/doi/10.1103/PhysRevA.74.052310, doi:10.1103/PhysRevA.74.052310.
Mehdi Mhalla and Simon Perdrix. Finding optimal flows efficiently. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 857–868. Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-540-70575-8_70, doi:10.1007/978-3-540-70575-8_70.
Piotr Mitosek and Miriam Backens. An algebraic formulation of Pauli flow, leading to faster flow-finding algorithms. Journal of Physics A: Mathematical and Theoretical, 59(3):035301, jan 2026. URL: https://doi.org/10.1088/1751-8121/ae2999, doi:10.1088/1751-8121/ae2999.
Will Simmons. Relating Measurement Patterns to Circuits via Pauli Flow. In Chris Heunen and Miriam Backens, editors, Proceedings 18th International Conference on Quantum Physics and Logic, QPL 2021, Gdansk, Poland, and online, 7-11 June 2021, volume 343 of EPTCS, 50–101. 2021. URL: https://doi.org/10.4204/EPTCS.343.4, doi:10.4204/EPTCS.343.4.