Pith. sign in

REVIEW 3 major objections 5 minor 27 references

This paper proves that three flow-preserving rewrite rules generate every measurement-based quantum computation with Pauli flow from a trivial diagram, while deliberately ignoring the computation's interpretation.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 08:51 UTC pith:OFULTT4J

load-bearing objection Genuine within-subfield result: three flow-preserving rules generate all flow-carrying MBQC patterns, but the completeness proof leans on an unpublished companion lemma, so treat the central theorem as conditional until [3] appears. the 3 major comments →

arxiv 2607.03250 v2 pith:OFULTT4J submitted 2026-07-03 quant-ph

Generating one-way computations with flow: flow-preserving rewriting that ignores the interpretation

Miriam Backens This is my paper
classification quant-ph MSC 68Q1281P68 PACS 03.67.Lx
keywords one-way quantum computationPauli flowgflowZX-calculusflow-preserving rewrite ruleslocal complementationgraph statescompleteness
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves a completeness theorem for flow-preserving rewriting in measurement-based quantum computation. It shows that every one-way computation that has Pauli flow—the condition guaranteeing that nondeterministic single-qubit measurements can be corrected adaptively into a deterministic overall computation—can be reduced to a trivial diagram with the same inputs and outputs using just three rewrite rules. The three rules preserve the existence of flow but not necessarily the computation's interpretation, so the reduction can be reversed: starting from the trivial diagram, the same rules generate any computation with Pauli flow, and likewise for gflow (the planar-measurement variant). A sympathetic reader cares because this turns flow-preserving rewriting from a tool for optimisation into a generator: a practical source of valid test instances for software and of ansätze for quantum machine learning, with a minimal rule set that cannot be shrunk.

Core claim

The paper's central claim is that every labelled open graph that admits Pauli flow—and therefore every ZX-diagram with Pauli flow—can be reduced, by a sequence of three flow-preserving rewrite rules, to a trivial diagram in which only outputs remain and no edges connect them. The three rules are (IO), which inserts or removes input/output dangling wires; (LC), local complementation about a non-input vertex; and (ZL), which deletes a Z-like measured vertex (left-to-right) or inserts one (right-to-left, with side conditions). Since each step preserves the existence of flow, reversing the reduction gives a recipe for generating arbitrary computations with flow from the trivial diagram. The rule

What carries the argument

The central object is the labelled open graph—a simple graph with specified input and output vertices and a measurement label on every non-output vertex—together with the algebraic characterisation of Pauli flow: a correction matrix C must satisfy M C = Id for the flow-demand matrix M, and N C must be the adjacency matrix of a DAG for the order-demand matrix N. The rewrite machinery consists of the three rules (IO), (LC), and (ZL), plus derived moves (pivots, edge toggles, merges, output-permutation) proved from them. The workhorse for the completeness proof is a lemma supplied by the companion paper [3] that gives a flow-preserving operation on two non-adjacent outputs; it fills the critica

Load-bearing premise

The proof assumes that a flow-preserving operation on two non-adjacent outputs used in the final step of the normalisation, taken from an unpublished companion paper, is valid exactly as stated; if that lemma carries hidden side conditions, the claim that every labelled open graph with Pauli flow can be trivialised does not follow.

What would settle it

Enumerate all labelled open graphs with up to six vertices that admit Pauli flow, then attempt the five-step trivialisation using only (IO), (LC), and (ZL); any graph that cannot be brought to the trivial normal form—or a graph where the Step-4c operation of replacing one output's neighbourhood N(a) by N(a) Δ N(b) for non-adjacent outputs a,b destroys flow—would refute the completeness theorem.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any MBQC pattern or ZX-diagram with Pauli flow can be rewritten to a trivial diagram (disconnected outputs) using only (IO), (LC), and (ZL), and the reverse sequence generates it back.
  • The three-rule set is minimal: dropping any one rule makes some diagrams with flow unreachable, so no smaller local rule set suffices.
  • Restricting to gflow (planar measurements) works by simply never inserting Pauli-measured vertices during generation.
  • Restricting to all-XY measurements is possible via composed derived rules, so XY-only computations—universal for unitary embeddings—can be generated while preserving flow.
  • Using the output-splitting construction of Section 5, one can generate arbitrary XY-only diagrams with gflow without keeping track of a flow at all, and the number of choices per insertion depends on the fixed number of outputs, not the growing total qubit count.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: because the rules ignore the interpretation, the generated diagrams are not constrained to realise a particular unitary; this turns the procedure into a tunable sampler over the space of MBQC patterns with flow, which could be used to stress-test flow-finding algorithms or to explore ansatz families for quantum machine learning.
  • Editorial extension: the paper's observation that the missing rules in the full interpretation-preserving set are all phase-managing suggests that the three-rule result may be the minimal structural core of any complete flow-preserving rewriting system.
  • Editorial extension: a concrete experiment would be to implement the output-splitting generator and measure the sampling bias described in Example 5.6; since the probability of generating a target diagram is proportional to the number of totalisations of its gflow partial order, one could deliberately bias the generator by choosing insertions non-uniformly.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies flow-preserving rewriting of labelled open graphs underlying measurement-based quantum computations, dropping the requirement that the interpretation be preserved. Its main claim is that three rewrite rules — (IO), (LC), and (ZL) — are complete generators: any labelled open graph with Pauli flow or gflow can be reduced, in a flow-preserving way, to a trivial graph with the same numbers of inputs and outputs, so every such graph can be generated from the trivial one by reversing the steps. The paper also argues the three-rule set is minimal, and it proposes a practical generation procedure for all-XY diagrams that avoids explicitly tracking a gflow.

Significance. If the main theorem is correct, this is a clean and useful result: it reduces the generation of all MBQC patterns with flow to three simple local rules, with concrete applications to test-instance generation for flow software and to QML ansatz design. The paper is well organised, explicitly separates derived rules from the basic rule set, and contains a concrete trivialisation algorithm rather than only an abstract completeness argument. The minimality argument is short but plausible. However, the completeness proof depends in an essential place on Lemma 3.6, which is imported from an unpublished companion paper, and one preparatory step (removal of Pauli measurements) is handled informally. The main theorem is therefore not self-contained as it stands.

major comments (3)
  1. [Section 3.2 (Lemma 3.6) and Section 4.1, Step 4c] Lemma 3.6 is stated as an unproved result from the author's own unpublished companion paper [3]. It is then used to prove Lemma 3.7, which is the key operation in Step 4c of the trivialisation procedure. If Lemma 3.6 has hidden side conditions on, e.g., inputs in N(a)∪N(b), overlapping neighbourhoods, or connectivity, then Step 4c cannot be applied to arbitrary gflow graphs and the completeness theorem does not follow. The manuscript should either include a full proof of Lemma 3.6, or make the companion paper available with the exact statement and hypotheses, and explicitly confirm that the lemma applies to every pair o', o used in Step 4c.
  2. [Section 4.1, Step 1] The elimination of Pauli measurements is not fully formal. The bullet points 'local complement and delete all Y-measurements', 'pivot on this pair', and 'pick one of the boundary neighbours and extend its dangling wire so it is no longer a boundary' are terse and only loosely supported by references to [12]. Since this first step is necessary to reduce an arbitrary Pauli-flow graph to the gflow setting used in the rest of the algorithm, the paper should spell out the exact sequence of rules or give precise theorem references for each sub-case, including the case where the chosen neighbour is an input or output with an arbitrary measurement label.
  3. [Section 4.1, Step 4b] The statement that a single-neighbour input or output 'can be merged using (IO)' is not immediate from the rule as described, since (IO) is said to insert or remove degree-2 vertices along a path graph starting at a boundary. For an adjacent input--output pair, neither endpoint is degree-2. Please spell out the exact application of (IO), or introduce a derived merge rule and prove it flow-preserving; this step is load-bearing for termination of the trivialisation procedure.
minor comments (5)
  1. [Throughout] There are small typos: 'they they' in the Introduction; Step 4 says 'partition I\O and I\O', which should presumably read 'I\O and O\I'; and 'with nqubits' should be 'with n qubits'.
  2. [Abstract and Introduction] The paper claims to handle 'any ZX-diagram with Pauli flow', but the formal development concerns labelled open graphs and ZX-flow is only cited, not defined or proved here. Please clarify the intended scope of the completeness theorem.
  3. [Lemma 3.7 proof] The proof of Lemma 3.7 is presented as a sequence of diagrams with terse labels such as '3.3'. A short verbal description of which vertices are added/removed at each step would make the argument much easier to verify.
  4. [References] Reference [3] is listed as 'To appear'. If it is essential to the proof, the version of record or an arXiv identifier should be supplied so reviewers and readers can check Lemma 3.6.
  5. [Section 5.2] The probability discussion in Example 5.6 assumes that all choices in the generation procedure are uniformly random. This should be stated explicitly, since the claim about relative likelihoods is model-dependent.

Circularity Check

1 steps flagged

Completeness proof is not definitionally circular, but its key Step 4c rests on an unpublished companion-paper lemma by the same author.

specific steps
  1. self citation load bearing [Section 3.2 (Lemmas 3.6, 3.7), applied in Section 4.1 Step 4c]
    "Lemma 3.6([3]). Let Γ=(G,I,O,λ) be a labelled open graph which has gflow. Suppose a,b∈O are not adjacent to each other, then the following operation is flow-preserving... Lemma 3.7. Let Γ=(G,I,O,λ) be a labelled open graph which has gflow. Suppose a,b∈O are not adjacent to each other. Then replacing the neighbourhood of a by the symmetric difference N G(a)ΔN G(b) preserves the existence of gflow. Proof. This follows by simplifying the end result of Lemma 3.6 in non-interpretation-preserving ways."

    The trivialisation step that reduces the neighbourhood of an input to a single output applies Lemma 3.7 to every other output neighbour. Lemma 3.7 is not proved from the paper's own three rules; its proof is only the sentence 'This follows by simplifying the end result of Lemma 3.6', and Lemma 3.6 is quoted from [3], an unpublished companion paper by the same author ('Completeness for flow-preserving rewrite rules. To appear'). The completeness/generation theorem for arbitrary diagrams with gflow is therefore load-bearing on an unverified self-citation: if Lemma 3.6 has hidden side conditions or is invalid, Step 4c fails and the central claim is not established. This is a self-citation chain rather than a definitional equivalence, and the rest of the trivialisation is structurally independ

full rationale

No step of the paper defines its target in terms of itself, and there is no fitted parameter renamed as a prediction; the three rules are genuinely flow-preserving and the trivialisation procedure is a constructive reduction. However the derivation is not self-contained at its most load-bearing point: Lemma 3.7, used in Step 4c, is obtained by simplifying Lemma 3.6, which is quoted from an unpublished companion paper by the same author. Other key ingredients, such as the algebraic characterisation of Pauli flow [22] and the planar-insertion theorem [4], are also from the author's own prior work, although those are published and independently checkable. Because the central completeness claim depends on an unpublished self-citation for a nontrivial operation on output neighbourhoods, but the argument is structurally independent and not a definitional collapse, the appropriate score is 4.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No fitted parameters. The central theorem is an existence result about rewrite rules; it relies on prior algebraic characterisations of flow and on flow-preservation lemmas, concentrated in the author's own prior work, and on one unpublished companion lemma.

axioms (5)
  • domain assumption Algebraic formulation of Pauli flow: Γ has focused Pauli flow iff M_Γ C = Id and N_Γ C is acyclic (Theorem 2.5 from [22]).
    This is the working definition of flow throughout Sections 3 and 4; imported from [22] without re-derivation.
  • domain assumption Focused Pauli flow exists iff Pauli flow exists; same for gflow.
    Invoked when using focused flows in Lemmas 3.3/3.4 and in the trivialisation algorithm; cited to [25,20,2].
  • domain assumption Local complementation preserves gflow/Pauli flow when the centre is not an input.
    Used for rule (LC) and derived rules; cited to [2, Lemma 4.3] and [25, Lemma D.15].
  • domain assumption Z-like deletion always preserves flow; Z-like insertion preserves flow under the conditions of Theorem 3.1.
    Used in rule (ZL), Step 2 of trivialisation, and Proposition 5.1; cited to [2], [25], [18], [4].
  • ad hoc to paper Lemma 3.6: the flow-preserving output-neighbourhood symmetric-difference operation stated in [3] holds as written.
    No proof is given in this manuscript; [3] is a to-appear paper by the same author, so this is not independently verifiable from the submitted text.

pith-pipeline@v1.3.0-alltime-deepseek · 18438 in / 15930 out tokens · 159460 ms · 2026-08-02T08:51:21.033063+00:00 · methodology

0 comments
read the original abstract

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\"atze 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.

Figures

Figures reproduced from arXiv: 2607.03250 by Miriam Backens.

Figure 1
Figure 1. Figure 1: The complete flow-preserving (but not necessarily interpretation-preserving) rule set. The [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 3 linked inside Pith

  1. [1]

    093021, doi:10.1088/1367-2630/16/9/093021

    Miriam Backens (2014):The ZX-calculus is complete for stabilizer quantum mechanics.New Journal of Physics16(9), p. 093021, doi:10.1088/1367-2630/16/9/093021

    doi:10.1088/1367-2630/16/9/093021 2014

  2. [2]

    421, doi:10.22331/q- 2021-03-25-421

    Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski & John van de Wetering (2021):There and Back Again: A Circuit Extraction Tale.Quantum5, p. 421, doi:10.22331/q- 2021-03-25-421

    doi:10.22331/q- 2021

  3. [3]

    To appear

    Miriam Backens & Simon Perdrix (2026):Completeness for flow-preserving rewrite rules. To appear. 17

    2026

  4. [4]

    100–126, doi:10.4204/EPTCS.426.4

    Miriam Backens & Thomas Perez (2025):Inserting Planar-Measured Qubits into MBQC Patterns While Preserving Flow.Electronic Proceedings in Theoretical Computer Science426, pp. 100–126, doi:10.4204/EPTCS.426.4

    doi:10.4204/eptcs.426.4 2025

  5. [5]

    de Beaudrap, Aleks Kissinger & John van de Wetering (2022):Circuit Extraction for ZX- Diagrams Can Be #P-Hard

    N. de Beaudrap, Aleks Kissinger & John van de Wetering (2022):Circuit Extraction for ZX- Diagrams Can Be #P-Hard. In Miko laj Boja´nczyk, Emanuela Merelli & David P. Woodruff, editors: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022),Leibniz International Proceedings in Informatics (LIPIcs)229, Schloss Dagstuhl – Leibniz-...

    doi:10.4230/lipics.icalp.2022.119 2022

  6. [6]

    2489–2510, doi:10.1016/j.tcs.2008.12.046

    Anne Broadbent & Elham Kashefi (2009):Parallelizing Quantum Circuits.Theoretical Computer Science410(26), pp. 2489–2510, doi:10.1016/j.tcs.2008.12.046

    doi:10.1016/j.tcs.2008.12.046 2009

  7. [7]

    Browne, Elham Kashefi, Mehdi Mhalla & Simon Perdrix (2007):Generalized Flow and Determinism in Measurement-Based Quantum Computation.New Journal of Physics9(8), p

    Daniel E. Browne, Elham Kashefi, Mehdi Mhalla & Simon Perdrix (2007):Generalized Flow and Determinism in Measurement-Based Quantum Computation.New Journal of Physics9(8), p. 250, doi:10.1088/1367-2630/9/8/250

    doi:10.1088/1367-2630/9/8/250 2007

  8. [8]

    arXiv:2405.08319

    Luis Mantilla Calder ´on, Robert Raussendorf, Polina Feldmann & Dmytro Bondarenko (2025): Measurement-Based Quantum Machine Learning. arXiv:2405.08319

    Pith/arXiv arXiv 2025

  9. [9]

    New Journal of Physics25(10), p

    Shuxiang Cao (2023):Multi-Agent Blind Quantum Computation without Universal Cluster States. New Journal of Physics25(10), p. 103028, doi:10.1088/1367-2630/acfab6

    doi:10.1088/1367-2630/acfab6 2023

  10. [10]

    052310, doi:10.1103/PhysRevA.74.052310

    Vincent Danos & Elham Kashefi (2006):Determinism in the One-Way Model.Physical Review A 74(5), p. 052310, doi:10.1103/PhysRevA.74.052310

    doi:10.1103/physreva.74.052310 2006

  11. [11]

    Vincent Danos, Elham Kashefi & Prakash Panangaden (2007):The measurement calculus.Journal of the ACM (JACM)54(2), pp. 8–es

    2007

  12. [12]

    279, doi:10.22331/q-2020- 06-04-279

    Ross Duncan, Aleks Kissinger, Simon Perdrix & John van de Wetering (2020):Graph-Theoretic Simplification of Quantum Circuits with the ZX-calculus.Quantum4, p. 279, doi:10.22331/q-2020- 06-04-279

    doi:10.22331/q-2020- 2020

  13. [13]

    34, doi:10.1007/s42484- 025-00264-6

    Tom Ewen, Ivica Turkalj, Patrick Holzer & Mark-Oliver Wolf (2025):Application of ZX-calculus to quantum architecture search.Quantum Machine Intelligence7(1), p. 34, doi:10.1007/s42484- 025-00264-6

    doi:10.1007/s42484- 2025

  14. [14]

    In:Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science - LICS ’18, ACM Press, Oxford, United Kingdom, pp

    Amar Hadzihasanovic, Kang Feng Ng & Quanlong Wang (2018):Two complete axiomatisations of pure-state qubit quantum computing. In:Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science - LICS ’18, ACM Press, Oxford, United Kingdom, pp. 502–511, doi:10.1145/3209108.3209128

    arXiv 2018

  15. [15]

    arXiv:2312.02793

    Calum Holker (2023):Causal Flow Preserving Optimisation of Quantum Circuits in the ZX- calculus, doi:10.48550/arXiv.2312.02793. arXiv:2312.02793

    Pith/arXiv arXiv doi:10.48550/arxiv.2312.02793 2023

  16. [16]

    arXiv:2603.09580

    Aleks Kissinger & John van de Wetering (2026):ZX-Flow: A Flexible Criterion for Deterministic Computation with ZX-Diagrams, doi:10.48550/arXiv.2603.09580. arXiv:2603.09580

    doi:10.48550/arxiv.2603.09580 2026

  17. [17]

    Tommy McElvanney (2025):Preservation of Determinism in MBQC under ZX-calculus Rewrites. Ph.D. thesis, University of Birmingham, Birmingham, UK. Available athttps://etheses. bham.ac.uk//id/eprint/16186/

    2025

  18. [18]

    66–82, doi:10.4204/EPTCS.394.5

    Tommy McElvanney & Miriam Backens (2023):Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements.Electronic Proceedings in Theoretical Computer Science 394, pp. 66–82, doi:10.4204/EPTCS.394.5. 18

    doi:10.4204/eptcs.394.5 2023

  19. [19]

    203–219, doi:10.4204/EPTCS.384.12

    Tommy McElvanney & Miriam Backens (2023):Flow-Preserving ZX-calculus Rewrite Rules for Optimisation and Obfuscation.Electronic Proceedings in Theoretical Computer Science384, pp. 203–219, doi:10.4204/EPTCS.384.12

    doi:10.4204/eptcs.384.12 2023

  20. [20]

    Mehdi Mhalla, Mio Murao, Simon Perdrix, Masato Someya & Peter S. Turner (2014):Which Graph States Are Useful for Quantum Information Processing?In Dave Bacon, Miguel Martin-Delgado & Martin Roetteler, editors:Theory of Quantum Computation, Communication, and Cryptography, Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp. 174–187, doi:10.1...

    doi:10.1007/978-3- 2014

  21. [21]

    In Luca Aceto, Ivan Damg˚ard, Leslie Ann Goldberg, Magn´ us M

    Mehdi Mhalla & Simon Perdrix (2008):Finding Optimal Flows Efficiently. In Luca Aceto, Ivan Damg˚ard, Leslie Ann Goldberg, Magn´ us M. Halld´orsson, Anna Ing´olfsd´ottir & Igor Walukiewicz, editors:Automata, Languages and Programming, Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp. 857–868, doi:10.1007/978-3-540-70575-8 70

    doi:10.1007/978-3-540-70575-8 2008

  22. [22]

    035301, doi:10.1088/1751-8121/ae2999

    Piotr Mitosek & Miriam Backens (2026):An Algebraic Formulation of Pauli Flow, Leading to Faster Flow-Finding Algorithms.Journal of Physics A: Mathematical and Theoretical59(3), p. 035301, doi:10.1088/1751-8121/ae2999

    doi:10.1088/1751-8121/ae2999 2026

  23. [23]

    022316, doi:10.1103/PhysRevA.69.022316

    Maarten Van den Nest, Jeroen Dehaene & Bart De Moor (2004):Graphical description of the action of local Clifford transformations on graph states.Physical Review A69(2), p. 022316, doi:10.1103/PhysRevA.69.022316

    doi:10.1103/physreva.69.022316 2004

  24. [24]

    Briegel (2001):A One-Way Quantum Computer.Physical Review Letters86(22), pp

    Robert Raussendorf & Hans J. Briegel (2001):A One-Way Quantum Computer.Physical Review Letters86(22), pp. 5188–5191, doi:10.1103/PhysRevLett.86.5188

    doi:10.1103/physrevlett.86.5188 2001

  25. [25]

    50–101, doi:10.4204/EPTCS.343.4

    Will Simmons (2021):Relating Measurement Patterns to Circuits via Pauli Flow.Electronic Proceedings in Theoretical Computer Science343, pp. 50–101, doi:10.4204/EPTCS.343.4

    doi:10.4204/eptcs.343.4 2021

  26. [26]

    In:2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp

    Renaud Vilmart (2019):A Near-Minimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics. In:2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1–10, doi:10.1109/LICS.2019.8785765

    arXiv 2019

  27. [27]

    arXiv:2012.13966

    John van de Wetering (2020):ZX-calculus for the working quantum computer scientist. arXiv:2012.13966. 19

    Pith/arXiv arXiv 2020