{"id":"30ba96c1-8e33-4ebf-986a-be57df95b9ef","arxiv_id":"2608.13035","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The flow-preserving rewrite rules of Figure 2 are complete for all MBQC-form ZX-diagrams with Pauli flow.","lead":"This paper proves a small set of picture-changing rules can transform any two equivalent measurement-based quantum computations that have a 'flow' property into each other without ever losing that property. It gives quantum circuit optimizers a guaranteed way to reason graphically about a broad class of computations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reverse of the spider nest rule (SN) is never proved flow-preserving, yet Theorem 74 needs it to translate the reverse of circuit rule (I).","rationale":"The reader's weakest assumption was the reliance on the imported circuit completeness result (Theorem 59) and the unproved Observation 65. My reading agrees that the external import is a risk, but the more specific and load-bearing gap is internal: the proof needs the reverse of the spider nest rule (SN) to translate the reverse of circuit rule (I), yet (SN) is only stated and proved in the deletion direction. This is a concrete missing step in the argument connecting circuit completeness to ZX completeness. If the reverse of (SN) is not flow-preserving, then even a fully verified circuit completeness theorem would not imply Theorem 74. The concern is addressable—either by proving the reverse direction of Lemma 28 under suitable conditions, or by finding a circuit completeness derivation that avoids using (I) in reverse—so the verdict remains conditional rather than reject. I do not see evidence that the central claim is false; the gap is in the proof as written.","tokens_in":40704,"tokens_out":22579,"duration_ms":218694,"concrete_test":"Start with the minimal extended-causal-flow diagram consisting of four disjoint XY-measured wires (or the ZX translation of four identity wires). Attempt to add the full 2π spider nest on four qubits, i.e., 15 YZ-measured phase gadgets with phases ±2π/8, one at a time, using the reverse of (SN). At each insertion, check whether the labelled open graph still has extended causal flow, e.g., by verifying the conditions of Theorem 22 and Corollary 37 for each new YZ-measured vertex. If any insertion step creates a cycle in the induced partial order or violates (C.YZ), the reverse of (SN) is not flow-preserving, and the proof of Theorem 74 is incomplete. Alternatively, attempt to derive the reverse of (SN) for n=4 from the other rules of Figure 2; if no derivation exists, the gap is confirmed.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 28 and Figure 2 introduce the spider nest rule (SN) only as a one-way deletion: a full 2π spider nest may be removed while preserving flow, but the reverse direction—adding a full 2π spider nest—is not proved. This matters because Theorem 59's completeness proof explicitly reverses every rule of Figure 5, including rule (I), which removes a 2π multi-controlled phase gate. Proposition 73 claims to translate all equations of Figure 5 into flow-preserving ZX rewrites, and Lemma 72 serves as the proof for (I). However, Lemma 72 only shows the forward direction: it derives the ZX-translation of (I) by applying (SN) left-to-right. For a circuit derivation that uses the reverse of (I), one would need to add a full spider nest, i.e., the reverse of (SN). The paper does not establish that this addition preserves extended causal flow, gflow, or Pauli flow. For n≥4 the phases in the full nest are not multiples of π/2, so the reverse cannot be obtained from the Clifford-complete rules (IO), (LC), and (ZL) that handle smaller cases. Consequently, the reduction from circuit completeness to ZX completeness has a gap at a step where the circuit completeness theorem is allowed to use (I) in reverse.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a completeness theorem for a set of flow-preserving ZX-calculus rewrite rules (Figure 2). The main result, Theorem 74, states that any two MBQC-form ZX-diagrams that both have Pauli flow and represent the same linear embedding can be transformed into each other using only rules that preserve the existence of flow. The proof has two parts. Section 4 gives a flow-preserving circuit extraction algorithm, showing that any MBQC-form diagram with Pauli flow can be rewritten, using only the Figure 2 rules, into a diagram with extended causal flow; this is done via a phase-gadget form and a notion of pseudo-focused gflow, with explicit correction-function updates. Section 5 reduces completeness for extended-causal-flow diagrams to a completeness theorem for quantum circuits with initialisation (Theorem 59). The ZX-translations of the circuit rules are shown to be derivable from Figure 2 (Proposition 73), and a causal-subdiagram formalism (Proposition 71) is introduced to lift local rewrites to arbitrary contexts. New ingredients include the phase-fusion rule (PF), the Euler rule (EZX), and the spider-nest rule (SN).","tokens_in":40963,"tokens_out":12296,"duration_ms":126584,"significance":"If the main theorem is correct, this is a significant advance: it extends complete flow-preserving rewriting from the Clifford fragment to all MBQC-form diagrams with Pauli flow, and it provides a manifestly flow-preserving circuit extraction procedure that may be useful for circuit optimization. The paper is careful and detailed: correction-function updates are given explicitly in Lemmas 52 and 55, the pseudo-focused flow machinery is well developed, and the paper honestly states which rule directions are conditional. The central claim, however, currently rests on two under-supported steps: the reverse direction of the spider-nest rule (SN) is not proved, and Observation 65, which lifts circuit rewrites to causal subdiagrams, is asserted rather than proved. These are fixable, but they are load-bearing for Theorem 74, so the result is not yet established as written.","major_comments":[{"comment":"Theorem 74 simulates circuit derivations that may use rule (I) of Figure 5 in reverse, because Theorem 59 proves that every rule of Figure 5 can be reversed. However, Lemma 28 proves only the deletion direction of the spider-nest rule (SN), and Lemma 72 only derives the forward direction of (I) by applying (SN). The reverse of (I) would require adding a full 2π spider nest, i.e. the reverse of (SN), which the paper never shows to be flow-preserving. Lemma 36 handles n≤3 using Clifford rules, but for n≥4 the nest contains phases that are not multiples of π/2, so that argument does not apply. Consequently the reduction from circuit completeness to ZX completeness is incomplete at exactly the step where a circuit derivation uses (I) in reverse; this is load-bearing for Theorem 74.","section":"§3.2 (Lemma 28) and §5.3 (Lemma 72)"},{"comment":"Observation 65 asserts, without proof, that any subcircuit to which a circuit rewrite rule can be applied translates to a causal subdiagram in the sense of Definition 64. This is load-bearing: Theorem 74 uses it to conclude that any sequence of circuit rewrites lifts to a sequence of valid flow-preserving ZX rewrites via Proposition 71. The surrounding text gives intuition and one example, but no proof is given that Conditions 1–4 of Definition 64 always hold, including for rules such as the right-to-left direction of (C) which act on possibly disconnected parts, and for circuits with initialisation where the 'past' may be empty. A formal construction of Vpast, VD, and Vfuture for each circuit rewrite rule, or a proof by induction on circuit structure, should be supplied.","section":"§5.2, Observation 65"}],"minor_comments":[{"comment":"The completeness proof imports the core unitary-circuit completeness from [7] and the initialisation extension from [8]. Please state the specific theorem numbers and explicitly justify that the theory from [8], which allows both initialisation and termination, specialises to the initialisation-only setting used here; since Theorem 74 inherits this result, a precise statement would help the reader.","section":"§5.1, Theorem 59"},{"comment":"The line 'We sometimes refer to S:=V\\S as the set of unextracted vertices' defines a set as its own complement because S is already the set of extracted vertices; use an overline or a different letter for the complement.","section":"Definition 43"},{"comment":"Line 5 introduces the variable T for the set of non-extracted vertices, while the surrounding text and Lemmas 52–55 use S for the same concept; aligning these notations would avoid confusion.","section":"Algorithm 1"},{"comment":"The right-to-left condition reads 'extended causal flow is preserved if The conditions...', which appears to be a typographical error; the sentence should be rephrased.","section":"Lemma 32"}],"recommendation":"major_revision","confidential_remarks":"This is a strong and relevant paper, and the overall proof strategy is plausible. The two gaps above are the main obstacles: the reverse spider-nest direction and the unproved status of Observation 65. The reverse-SN issue is likely fixable by proving that a full 2π spider nest can be inserted in a flow-preserving way, e.g. using the YZ-insertion characterisation of Theorem 22, or by restructuring the argument to avoid reversing (I). I would support publication after a careful revision addressing these points. The paper also relies heavily on the authors' own prior circuit-completeness results [7,8]; the editor may wish to confirm that the cited theorems indeed match the exact fragment used here."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a serious paper and likely the right result: complete flow-preserving rewrites for MBQC-form ZX-diagrams with Pauli flow. The new rules (PF, EZX, SN) and the extraction argument are real contributions. The proof that Pauli flow can be brought to extended causal flow while preserving flow is detailed and convincing; I read the diagram lemmas carefully and the flow bookkeeping checks out.\n\nWhat is actually new: previous completeness stopped at the Clifford fragment, and this extends it to Pauli flow. The strategy of using quantum circuit completeness as the engine, instead of proving ZX completeness directly, is novel. Sections 3 and 4 are the strongest part; the extraction algorithm is carefully argued and genuinely manifestly flow-preserving in a way I have not seen before.\n\nThe soft spot is the handoff in Section 5. Theorem 74 leans on Theorem 59, which imports completeness from [7,8,9] with only a sketch. That is not fatal by itself, but the translation of circuit derivations into ZX rewrites is not fully demonstrated. In particular, rule (I) is translated only in the deleting direction via SN; the reverse of (I) would require adding a full 2π spider nest, and the reverse of SN is never proved. The paper says only the deletion direction is needed, but the circuit completeness proof explicitly reverses every rule, including (I). The derivation of reverse (I) in the circuit calculus introduces a 4π gate and then removes one 2π copy; translating that seems to need either reverse SN or a derivation the paper does not supply. For n≥4 the phases are not Clifford, so the Clifford-complete rules will not cover it. This is a genuine gap in the written proof, not a fatal flaw — I suspect reverse SN is true, or the derivation can be rearranged, but it needs to be shown.\n\nObservation 65, the context-lifting claim, is also asserted rather than proved. The argument is plausible and probably fixable, but it is load-bearing for the claim that local circuit rewrites lift to arbitrary contexts.\n\nBottom line: the paper is for people working on ZX-calculus completeness and MBQC circuit optimization. It deserves a serious referee, but the referee should ask for a complete proof of the circuit-to-ZX translation, especially the (I) direction, before acceptance.","headline":"A strong, careful completeness proof for flow-preserving ZX rewriting that reduces to circuit completeness; the reduction has a genuine gap around the reverse of the spider-nest rule, but the main theorem is plausible and worth refereeing.","tokens_in":41430,"tokens_out":8193,"would_cite":true,"duration_ms":89675,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The flow-preserving rewrite rules of Figure 2 are complete: any two equivalent MBQC-form ZX-diagrams with Pauli flow can be transformed into each other while keeping a flow.","keywords":["ZX-calculus","measurement-based quantum computing","Pauli flow","gflow","causal flow","circuit extraction","flow-preserving rewriting","quantum circuits with initialisation"],"falsifier":"Run an exhaustive search over all MBQC-form ZX-diagrams up to a small size that admit Pauli flow, grouping them by their linear map; if any two in the same group are not connected by the Figure 2 rules applied under their stated flow conditions, Theorem 74 is false. A cheaper check targets the imported circuit completeness: verify the Figure 5 rules by direct matrix computation on all circuits with, say, up to three qubits and a bounded number of gates.","tokens_in":40527,"feed_emoji":"🔀","tokens_out":7401,"duration_ms":71220,"temperature":0.7,"pith_summary":"The paper claims that the rewrite rules of Figure 2 are complete for flow-preserving transformations of measurement-based quantum computations: any two MBQC-form ZX-diagrams that both have Pauli flow and represent the same linear map can be rewritten into each other using only rules that preserve the existence of a flow. This extends the previously known complete flow-preserving calculus for the Clifford fragment to the full Pauli-flow fragment, and it is the first time quantum-circuit completeness results are used to prove a ZX-calculus completeness theorem. The proof works by making circuit extraction itself flow-preserving and then translating a complete equational theory for quantum circuits with initialisation into ZX rewrites. The result matters because Pauli flow is the standard certificate that a measurement-based computation is deterministic and can be efficiently turned into a quantum circuit, so a complete flow-preserving calculus lets one reason graphically without ever leaving the class of efficiently extractable diagrams.","feed_headline":"Flow-preserving rewrites now complete for measurement-based diagrams","feed_subtitle":"Equivalent measurement-based computations with Pauli flow can be linked by rewrite steps that never destroy the flow.","key_machinery":"The central machinery is the triple of flow notions — Pauli flow, gflow, and extended causal flow — organised by correction sets that are subsets of the inputs. The load-bearing construction is 'extracted vertices' and their frontier (Definition 43): a growing set at the top of the dependency order whose correction sets have size one, with a frontier that is always as large as the number of outputs. Each extraction step applies YZ-insertion followed by a pivot, mimicking a CNOT or Hadamard push into the circuit while preserving the existence of gflow; once all vertices are extracted, correction sets have size one and the diagram has extended causal flow, meaning every non-output vertex is corrected by a single neighbouring vertex. Around this, the causal-subdiagram lemma lets a rewrite inside a small subdiagram be replaced in any context without destroying extended causal flow, and the spider-nest rule removes full phase-gadget nests that implement a trivial 2π phase.","core_discovery":"The central claim is Theorem 74: the flow-preserving rule set of Figure 2 — input/output unfusion, phase fusion, Z-insertion/deletion, local complementation, Euler decomposition, and the spider-nest rule — is complete for MBQC-form ZX-diagrams that admit Pauli flow. In concrete terms, whenever two such diagrams denote the same linear embedding, there is a sequence of these rewrites connecting them, and every intermediate diagram also has a flow. The proof has two stages. First, a manifestly flow-preserving circuit-extraction algorithm turns any diagram with Pauli flow into a diagram with extended causal flow, using YZ-insertions and pivots that never increase the number of unextracted vertices and maintain a pseudo-focused gflow. Second, the paper shows that the ZX-translations of a complete set of rewrite rules for quantum circuits with initialisation are derivable from Figure 2; a causal-subdiagram lemma (Definition 64, Proposition 71) allows those derivations to be lifted from local contexts to arbitrary diagrams. The completeness of the flow-preserving calculus therefore reduces to the completeness of circuit rewriting.","pith_inferences":["The reduction makes the main theorem conditional on the cited circuit-completeness results; independently re-checking those proofs, or formalising them, would directly test the foundation of Theorem 74.","A similar recipe could yield flow-preserving completeness elsewhere: choose a complete circuit calculus and find flow-preserving ZX translations for its rules, as done here for initialisation; qudit MBQC or diagrams with ZX-flow are natural next targets.","The spider-nest identity suggests a concrete optimisation heuristic: search for full phase-gadget nests whose phases sum to 2π and delete them; because the rule preserves flow, such optimisation could be safely interleaved with circuit extraction."],"forward_implications":["Any two equivalent MBQC-form ZX-diagrams with Pauli flow are connected by flow-preserving rewrites; no deterministic measurement-based computation needs to leave the flow-preserving fragment to be compared with another.","Circuit extraction becomes a diagrammatic derivation: every diagram with Pauli flow can be rewritten, using only the Figure 2 rules, into an extended-causal-flow diagram that is directly readable as a quantum circuit with initialisation, with at most O(n^2) new vertices.","The non-Clifford part of the calculus is handled by the Euler decomposition rule and the spider-nest rule, which together absorb all real phase angles; this is what extends the earlier Clifford-completeness result.","Any equality between two circuits with initialisation can be proved in the ZX-calculus without ever destroying the flow, because every circuit rewrite of Figure 5 has a flow-preserving ZX counterpart."],"supporting_citations":[{"why":"Provides the complete equational theory for unitary quantum circuits on which the initialisation extension in Theorem 59 is built.","marker":"[9]"},{"why":"Proves the completeness of the unitary-circuit fragment E0 that Theorem 59 imports as a black box.","marker":"[7]"},{"why":"Extends the unitary completeness to quantum circuits with qubit initialisation, the exact fragment used in the reduction.","marker":"[8]"},{"why":"Supplies the extended-gflow circuit extraction algorithm and the flow-preserving local complementation and Z-deletion lemmas that the new extraction refines.","marker":"[2]"},{"why":"Contributes the graph-theoretic simplification and extraction methods that the flow-preserving extraction algorithm follows.","marker":"[14]"},{"why":"Establishes completeness of flow-preserving rewriting for the Clifford fragment, on which the new non-Clifford rules build.","marker":"[20]"},{"why":"Defines gflow and Pauli flow, the determinism certificates that the whole rewriting framework preserves.","marker":"[6]"},{"why":"Provides the YZ-insertion theorem with its flow conditions, used throughout the extraction and causal-subdiagram arguments.","marker":"[3]"}],"fun_headline_variants":["Complete flow-preserving rewrites for MBQC diagrams","ZX-calculus rules now complete for Pauli flow","All Pauli-flow diagrams linked by safe rewrites","Flow-preserving completeness proof for ZX-calculus","Safe rewrites connect all equivalent flow diagrams"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main theorem inherits the completeness of the imported equational theory for quantum circuits with qubit initialisation; if that circuit-completeness theorem has any flaw, the ZX completeness result collapses with it.","fun_headline_variants_meta":{"raw":{"variants":["Complete flow-preserving rewrites for MBQC diagrams","ZX-calculus rules now complete for Pauli flow","All Pauli-flow diagrams linked by safe rewrites","Flow-preserving completeness proof for ZX-calculus","Safe rewrites connect all equivalent flow diagrams"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00028,"raw_usage":{"total_tokens":1664,"prompt_tokens":953,"completion_tokens":711,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":635}},"tokens_in":569,"tokens_out":711,"duration_ms":6953,"temperature":1.0,"reasoning_tokens":635,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:07:29.867049+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search over all MBQC-form ZX-diagrams up to a small size that admit Pauli flow, grouping them by their linear map; if any two in the same group are not connected by the Figure 2 rules applied under their stated flow conditions, Theorem 74 is false. A cheaper check targets the imported circuit completeness: verify the Figure 5 rules by direct matrix computation on all circuits with, say, up to three qubits and a bounded number of gates.","supporting_citations":[],"review_version":1}