pith. sign in

arxiv: 2606.30525 · v1 · pith:J4BAFHMEnew · submitted 2026-06-29 · 🪐 quant-ph · cs.DS

Working with measurement-based computations on qudits

Piotr Mitosek , Miriam Backens This is my paper

Pith reviewed 2026-06-30 06:02 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS
keywords qudit flowmeasurement-based quantum computationgraph statesflow-finding algorithmadaptive correctionsprime dimension
0
0 comments X

The pith

A simpler definition of qudit flow supports an O(n^3) finding algorithm for prime-dimensional graph states.

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

The paper introduces a streamlined definition of flow for measurement-based computations on prime-dimensional qudits. Flow indicates when adaptive measurement corrections can make the overall procedure deterministic. The new definition draws directly from the qubit case, which simplifies prior qudit versions and allows proofs of focusability and canonicity. It yields an algorithm that locates flows in cubic time relative to the number of qudits, plus several transformations that preserve flow. A reader would care because the change lowers the cost of handling adaptivity and supplies concrete tools for building and optimizing qudit computations.

Core claim

By defining qudit flow through a pair of functions on the vertices that satisfy the same correction and commutation relations used for qubits, the authors prove that focused flow is canonical, refine the algebraic description of focused flow, and obtain an O(n^3) algorithm that finds whether a flow exists; they further exhibit flow-preserving pivots, vertex insertions and removals, and reversibility.

What carries the argument

The simpler qudit flow, a pair of functions on graph vertices obeying correction and commutation conditions that guarantee a deterministic adaptive strategy exists for the measurements.

If this is right

  • Focused flow is the canonical representative for any given computation.
  • The cubic-time algorithm matches the best qubit result and improves the prior quartic bound for qudits.
  • Pivoting, insertion and removal of certain vertices, and flow reversal all preserve the existence of flow and can be used to rewrite computations.
  • An algorithmic generator can systematically produce large families of qudit computations that admit flow.

Where Pith is reading between the lines

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

  • The transformations could be composed into a search procedure that finds resource-efficient graph states for a target computation.
  • The generation method supplies training data for machine-learning models that predict or enforce flow.
  • The cubic scaling makes exhaustive checks feasible for graphs an order of magnitude larger than before.
  • The same simplification might apply to other resource states beyond graph states once the prime-dimension assumption is relaxed.

Load-bearing premise

The definition, its properties, and the algorithm apply when the entangled resource is a prime-dimensional qudit graph state.

What would settle it

A concrete prime-dimensional qudit graph state and measurement pattern for which a valid deterministic correction strategy exists but the O(n^3) algorithm reports that no flow is present.

Figures

Figures reproduced from arXiv: 2606.30525 by Miriam Backens, Piotr Mitosek.

Figure 1
Figure 1. Figure 1: Running example of a labelled open F𝑑-graph with 𝑑 = 5. 1a: a labelled open F𝑑-graph with one input 𝑖 and two outputs 𝑜1 and 𝑜2. The measurement labels of non-outputs are given near the names of the vertices. Edge weights are denoted by numbers near the middles of the edges. 1b: the corresponding adjacency matrix. The dotted lines subdivide input, internal, and output vertices for improved readability but … view at source ↗
Figure 2
Figure 2. Figure 2: The algebraic formulation of the labelled open [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The labelled open F𝑑-graph from [PITH_FULL_IMAGE:figures/full_fig_p041_3.png] view at source ↗
read the original abstract

Measurement-based quantum computing is a universal model of quantum computation in which successive product measurements of an entangled resource state drive the computation. The non-deterministic nature of measurements necessitates adaptivity to ensure an overall deterministic computation. Flow structures characterise cases in which such an adaptive correction procedure is possible. Recently, flow has been defined in a setting where the resource states are prime-dimensional qudit graph states rather than the usual qubit graph states. Yet, this qudit flow definition is more burdensome to work with than analogous definitions for qubits. Here, we give a simpler definition of qudit flow and consider various useful properties of this flow, drawing on results for the qubit case. In particular, we show how to focus qudit flow and argue that focused flow is canonical. We improve the previous algebraic formulation to capture focused flow and use it to obtain an $O(n^3)$ flow-finding algorithm (where $n$ is the number of qudits), matching the best known complexity for qubit flows and improving on the previous $O(n^4)$ result for qudits. Furthermore, we explore multiple flow-preserving transformations, thus opening a pathway to using flow for optimisation. These transformations include pivoting, removal and insertion of certain types of vertices, and reversibility of flow. Lastly, we propose an algorithmic approach to generating large qudit computations with flow, for testing or machine learning.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces a simpler definition of flow for measurement-based quantum computation on prime-dimensional qudit graph states. It establishes that this flow is focusable and that focused flow is canonical, improves an algebraic formulation to obtain an O(n^3) flow-finding algorithm, explores flow-preserving transformations (pivoting, vertex removal/insertion, reversibility), and proposes an algorithmic method for generating large qudit computations with flow.

Significance. If the results hold, the work lowers the barrier to applying flow in qudit MBQC, matches the best-known qubit complexity, and supplies concrete tools for optimization and systematic generation of computations. These contributions are directly useful for extending adaptive-correction techniques beyond qubits.

minor comments (2)
  1. Abstract: the statement that the new definition 'inherits focusability and canonicity from the qubit case' would be strengthened by a one-sentence pointer to the specific qubit result being invoked.
  2. The manuscript would benefit from an explicit statement, early in the development, of the precise conditions under which the O(n^3) bound holds (e.g., whether it requires the resource state to be a prime-dimensional graph state).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work on a simplified definition of flow for qudit MBQC, the O(n^3) algorithm, flow-preserving operations, and the generation method. We appreciate the recommendation for minor revision and the assessment that the contributions lower the barrier for applying flow in this setting.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central contributions—a simpler definition of qudit flow, its focusability and canonicity properties, and the O(n^3) flow-finding algorithm—are obtained by direct algebraic reformulation of the new definition into linear equations over GF(p) followed by standard Gaussian elimination. These steps rely on explicit mappings from the established qubit flow literature and generic complexity bounds for linear algebra, without any reduction of the claimed results to fitted parameters, self-citations, or definitional tautologies. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard mathematical properties of graph states and flow in the qubit case, extended to prime-dimensional qudits; no free parameters, new physical entities, or ad-hoc axioms are introduced.

axioms (1)
  • domain assumption Resource states are prime-dimensional qudit graph states whose flow properties extend from the qubit case
    Invoked when the new definition and algorithm are stated to apply to these states.

pith-pipeline@v0.9.1-grok · 5772 in / 1253 out tokens · 30454 ms · 2026-06-30T06:02:58.687196+00:00 · methodology

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

57 extracted references · 37 canonical work pages · 4 internal anchors

  1. [1]

    The ZX-calculus is complete for stabilizer quantum mechanics

    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. arXiv:1307.7025

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1088/1367-2630/16/9/093021 2014

  2. [2]

    To appear

    MiriamBackens(2026):Generatingone-waycomputationswithflow: flow-preservingrewritingthatignores the interpretation. To appear

    2026

  3. [3]

    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. arXiv:2003.01664

    work page doi:10.22331/q-2021-03-25-421 2021

  4. [4]

    To appear

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

    2026

  5. [5]

    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, p. 100–126, doi:10.4204/eptcs.426.4

    work page doi:10.4204/eptcs.426.4 2025

  6. [6]

    Graph States Under the Action of Local Clifford Group in Non-Binary Case

    Mohsen Bahramgiri & Salman Beigi (2006):Graph States Under the Action of Local Clifford Group in Non-Binary Case.arXiv:quant-ph/0610267. arXiv:quant-ph/0610267

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  7. [7]

    Booth & Titouan Carette (2022):Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions

    Robert I. Booth & Titouan Carette (2022):Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions. In Stefan Szeider, Robert Ganian & Alexandra Silva, editors:47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022),Leibniz International Proceedings in Informatics (LIPIcs)241, Schloss Dagstuhl – Leibniz-Zentr...

    work page doi:10.4230/lipics.mfcs.2022.24 2022

  8. [8]

    Robert I. Booth, Aleks Kissinger, Damian Markham, Clément Meignant & Simon Perdrix (2023):Outcome DeterminisminMeasurement-BasedQuantumComputationwithQudits.Journal of Physics A: Mathematical and Theoretical56(11), p. 115303, doi:10.1088/1751-8121/acbace. arXiv:2109.13810

    work page doi:10.1088/1751-8121/acbace 2023

  9. [9]

    Booth & Damian Markham (2023):Flow conditions for continuous variable measurement-based quantum computing.Quantum7, p

    Robert I. Booth & Damian Markham (2023):Flow conditions for continuous variable measurement-based quantum computing.Quantum7, p. 1146, doi:10.22331/q-2023-10-19-1146

    work page doi:10.22331/q-2023-10-19-1146 2023

  10. [10]

    RobertIvanBooth(2022):Measurement-BasedQuantumComputationbeyondQubits.Ph.D.thesis,Sorbonne Université

    2022

  11. [11]

    2020 roadmap on plasma accelera- tors,

    DanielE.Browne,ElhamKashefi,MehdiMhalla&SimonPerdrix(2007):GeneralizedFlowandDetermin- ism in Measurement-Based Quantum Computation.New Journal of Physics9(8), p. 250, doi:10.1088/1367- 2630/9/8/250

    work page doi:10.1088/1367- 2007

  12. [12]

    103028, doi:10.1088/1367-2630/acfab6

    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

    work page doi:10.1088/1367-2630/acfab6 2023

  13. [13]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein (2022):Introduction to Algorithms, Fourth Edition. MIT Press

    2022

  14. [14]

    052310, doi:10.1103/PhysRevA.74.052310

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

    work page doi:10.1103/physreva.74.052310 2006

  15. [15]

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

    N. de Beaudrap (2007):A Complete Algorithm to Find Flows in the One-Way Measurement Model, doi:10.48550/arXiv.quant-ph/0603072. arXiv:quant-ph/0603072

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.quant-ph/0603072 2007

  16. [16]

    de Beaudrap (2008):Finding Flows in the One-Way Measurement Model.Physical Review A77(2), p

    N. de Beaudrap (2008):Finding Flows in the One-Way Measurement Model.Physical Review A77(2), p. 022328, doi:10.1103/PhysRevA.77.022328. 14Working with measurement-based computations on qudits

    work page doi:10.1103/physreva.77.022328 2008

  17. [17]

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

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

    work page doi:10.22331/q-2020-06-04-279 2020

  18. [18]

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

    TomEwen,IvicaTurkalj,PatrickHolzer&Mark-OliverWolf(2025):ApplicationofZX-calculustoquantum architecture search.Quantum Machine Intelligence7(1), p. 34, doi:10.1007/s42484-025-00264-6

    work page doi:10.1007/s42484-025-00264-6 2025

  19. [19]

    Gashkov & Igor S

    Sergey B. Gashkov & Igor S. Sergeev (2013):Complexity of Computation in Finite Fields.Journal of Mathematical Sciences191(5), pp. 661–685, doi:10.1007/s10958-013-1350-5

    work page doi:10.1007/s10958-013-1350-5 2013

  20. [20]

    505–509, doi:10.1016/j.physleta.2013.12.009

    Vlad Gheorghiu (2014):Standard form of qudit stabilizer groups.Physics Letters A378(5), pp. 505–509, doi:10.1016/j.physleta.2013.12.009

    work page doi:10.1016/j.physleta.2013.12.009 2014

  21. [21]

    563–617, doi:10.4007/annals.2021.193.2.4

    DavidHarvey&JorisvanderHoeven(2021):IntegerMultiplicationinTime$O(N\mathrm{log}\,n)$.Annals of Mathematics193(2), pp. 563–617, doi:10.4007/annals.2021.193.2.4

    work page doi:10.4007/annals.2021.193.2.4 2021

  22. [22]

    DavidHarvey&JorisvanderHoeven(2022):PolynomialMultiplicationoverFiniteFieldsinTime𝑂(𝑛log𝑛. J. ACM69(2), doi:10.1145/3505584

    work page doi:10.1145/3505584 2022

  23. [23]

    A quantum compiler for qudits of prime dimension greater than 3

    LukeE.Heyfron&EarlCampbell(2019):Aquantumcompilerforquditsofprimedimensiongreaterthan3. arXiv:1902.05634

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  24. [24]

    arXiv:2312.02793

    Calum Holker (2024):Causal flow preserving optimisation of quantum circuits in the ZX-calculus. arXiv:2312.02793

    work page arXiv 2024

  25. [25]

    Stabilizer states and clifford operations for systems of arbitrary dimensions and modular arithmetic.Phys

    Erik Hostens, Jeroen Dehaene & Bart De Moor (2005):Stabilizer states and Clifford operations for systems of arbitrary dimensions and modular arithmetic.Physical Review A71(4), p. 042315, doi:10.1103/PhysRevA.71.042315

    work page doi:10.1103/physreva.71.042315 2005

  26. [26]

    022406, doi:10.1103/PhysRevA.102.022406

    Aleks Kissinger & John van de Wetering (2020):Reducing T-count with the ZX-calculus.Physical Review A 102(2), p. 022406, doi:10.1103/PhysRevA.102.022406. arXiv:1903.10477

    work page doi:10.1103/physreva.102.022406 2020

  27. [27]

    66–82, doi:10.4204/EPTCS.394.5

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

    work page doi:10.4204/eptcs.394.5 2023

  28. [28]

    203–219, doi:10.4204/EPTCS.384.12

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

    work page doi:10.4204/eptcs.384.12 2023

  29. [29]

    174–187, doi:10.1007/978-3-642-54429-3_12

    MehdiMhalla,MioMurao,SimonPerdrix,MasatoSomeya&PeterS.Turner(2014):WhichGraphStatesAre Useful for Quantum Information Processing?In Dave Bacon, Miguel Martin-Delgado & Martin Roetteler, editors:Theory of Quantum Computation, Communication, and Cryptography, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 174–187, doi:10.1007/978-3-642-54429-3_12

    work page doi:10.1007/978-3-642-54429-3_12 2014

  30. [30]

    ArXiv:2207.09368 [quant-ph]

    Mehdi Mhalla, Simon Perdrix & Luc Sanselme (2025):Shadow Pauli Flow: Characterising Determinism in MBQCs involving Pauli Measurements, doi:10.48550/arXiv.2207.09368. ArXiv:2207.09368 [quant-ph]

    work page doi:10.48550/arxiv.2207.09368 2025

  31. [31]

    117–136, doi:10.4204/EPTCS.406.6

    PiotrMitosek(2024):PauliFlowonOpenGraphswithUnknownMeasurementLabels.Electronic Proceed- ings in Theoretical Computer Science406, pp. 117–136, doi:10.4204/EPTCS.406.6. arXiv:2408.06059

    work page doi:10.4204/eptcs.406.6 2024

  32. [32]

    Piotr Mitosek & Miriam Backens (2026):An algebraic formulation of Pauli flow, leading to faster flow- findingalgorithms.Journal of Physics A: Mathematical and Theoretical59(3),p.035301,doi:10.1088/1751- 8121/ae2999

    work page doi:10.1088/1751- 2026

  33. [33]

    Stefano Paesani, Jacob F. F. Bulmer, Alex E. Jones, Raffaele Santagati & Anthony Laing (2021):Scheme for UniversalHigh-DimensionalQuantumComputationwithLinearOptics.Physical Review Letters126(23),p. 230504, doi:10.1103/PhysRevLett.126.230504

    work page doi:10.1103/physrevlett.126.230504 2021

  34. [34]

    Boldizsár Poór, Robert I. Booth, Titouan Carette, John Van De Wetering & Lia Yeh (2023):The Qupit StabiliserZX-travaganza: SimplifiedAxioms,NormalFormsandGraph-TheoreticSimplification.Electronic Proceedings in Theoretical Computer Science384, pp. 220–264, doi:10.4204/EPTCS.384.13

    work page doi:10.4204/eptcs.384.13 2023

  35. [35]

    111–118, doi:10.1002/rsa.3240040108

    Dana Randall (1993):Efficient Generation of Random Nonsingular Matrices.Random Structures & Algo- rithms4(1), pp. 111–118, doi:10.1002/rsa.3240040108. P . Mitosek & M. Backens15

    work page doi:10.1002/rsa.3240040108 1993

  36. [36]

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

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

    work page doi:10.1103/physrevlett.86.5188 2001

  37. [37]

    015054, doi:10.1088/2058-9565/ae3b6f

    Alena Romanova & Wolfgang Dür (2026):Measurement-based quantum computing with qudit stabilizer states.Quantum Science and Technology11(1), p. 015054, doi:10.1088/2058-9565/ae3b6f

    work page doi:10.1088/2058-9565/ae3b6f 2026

  38. [38]

    The Electronic Journal of Linear Algebra [electronic only]16, pp

    Irene Sciriha (2007):A characterization of singular graphs.ELA. The Electronic Journal of Linear Algebra [electronic only]16, pp. 451–462. Available athttp://eudml.org/doc/129125

    2007

  39. [39]

    50–101, doi:10.4204/EPTCS.343.4

    WillSimmons(2021):RelatingMeasurementPatternstoCircuitsviaPauliFlow.Electronic Proceedings in Theoretical Computer Science343, pp. 50–101, doi:10.4204/EPTCS.343.4. arXiv:2109.05654

    work page doi:10.4204/eptcs.343.4 2021

  40. [40]

    29–45, doi:10.4204/EPTCS.394.3

    KorbinianStaudacher,TobiasGuggemos,SophiaGrundner-Culemann&WolfgangGehrke(2023):Reducing 2-QuBit Gate Count for ZX-Calculus Based Quantum Circuit Optimization.Electronic Proceedings in Theoretical Computer Science394, pp. 29–45, doi:10.4204/EPTCS.394.3

    work page doi:10.4204/eptcs.394.3 2023

  41. [41]

    Available at https://math.mit.edu/classes/18.783/2025/LectureNotes3.pdf.Accessed: 28thFebruary2025

    Andrew Sutherland (2025):Lecture Notes: Mathematics 18.783 – Elliptic Curves, Lecture #3. Available at https://math.mit.edu/classes/18.783/2025/LectureNotes3.pdf.Accessed: 28thFebruary2025

    2025

  42. [42]

    arXiv:2103.06914

    Alex Townsend-Teague & Konstantinos Meichanetzidis (2022):Simplification Strategies for the Qutrit ZX- Calculus, doi:10.48550/arXiv.2103.06914. arXiv:2103.06914

    work page doi:10.48550/arxiv.2103.06914 2022

  43. [43]

    Quantum circuit synthesis with qudit phase gadget method,

    Shuai Yang, Lihao Xu, Guojing Tian & Xiaoming Sun (2025):Quantum circuit synthesis with qudit phase gadget method, doi:10.48550/arXiv.2504.12710. A Comparison to the qubit case Qubit MBQC and its flow properties are more widely studied and thus many readers might be familiar withqubitflow,butnotquditflow. Forsuchreaders,inthisappendix,weexplainhowvariousd...

    work page doi:10.48550/arxiv.2504.12710 2025

  44. [44]

    Multiplying by𝐶𝑢,𝑤, we get: 𝑀𝑣,𝑢 𝐶𝑢,𝑤 =𝜆 𝑍 (𝑣) −1 𝐴𝑣,𝑢 𝐶𝑢,𝑤 and hence by linearity: (𝑀𝐶) 𝑣,𝑤 =𝜆 𝑍 (𝑣) −1 (𝐴𝐶) 𝑣,𝑤 (1)

    Suppose𝜆 𝑋 (𝑣)=0and thus𝑀 𝑣,𝑢 =𝜆 𝑍 (𝑣) −1 𝐴𝑣,𝑢. Multiplying by𝐶𝑢,𝑤, we get: 𝑀𝑣,𝑢 𝐶𝑢,𝑤 =𝜆 𝑍 (𝑣) −1 𝐴𝑣,𝑢 𝐶𝑢,𝑤 and hence by linearity: (𝑀𝐶) 𝑣,𝑤 =𝜆 𝑍 (𝑣) −1 (𝐴𝐶) 𝑣,𝑤 (1)

  45. [45]

    When𝜆 𝑋 (𝑣)≠0,thennecessarily𝑣∉𝐼andthus 𝑀has a𝑣-column

    Suppose𝜆 𝑋 (𝑣)≠0andthus𝑀 𝑣,𝑢 =𝜆 𝑋 (𝑣) −1𝛿𝑣,𝑢. When𝜆 𝑋 (𝑣)≠0,thennecessarily𝑣∉𝐼andthus 𝑀has a𝑣-column. Multiplying𝑀 𝑣,𝑢 be𝐶 𝑢,𝑤, we get: 𝑀𝑣,𝑢 𝐶𝑢,𝑤 =𝜆 𝑋 (𝑣) −1𝛿𝑣,𝑢 𝐶𝑢,𝑤 which equals0unless𝑣=𝑢when it equals𝜆 𝑋 (𝑣) −1𝐶𝑣,𝑤 . Using this fact, we find that: (𝑀𝐶) 𝑣,𝑤 = ∑︁ 𝑢∈ ¯𝐼 𝑀𝑣,𝑢 𝐶𝑢,𝑤 =𝜆 𝑋 (𝑣) −1𝐶𝑣,𝑤 (2) Now we can split the proof into two directions. (⇒):Supp...

  46. [46]

    Thus (𝐴𝐶) 𝑣,𝑣 =𝜆 𝑍 (𝑣), i.e

    For all𝑣such that𝜆 𝑋 (𝑣)=0, by Equation (1), we have1=(𝑀𝐶) 𝑣,𝑣 =𝜆 𝑍 (𝑣) −1 (𝐴𝐶) 𝑣,𝑣 . Thus (𝐴𝐶) 𝑣,𝑣 =𝜆 𝑍 (𝑣), i.e. (C1) holds

  47. [47]

    Since𝜆 𝑍 (𝑣)≠0(as𝜆(𝑣)≠(0,0)), this implies(𝐴𝐶) 𝑣,𝑤 =0 and thus (FX) holds

    Furthermore, for all𝑣such that𝜆 𝑋 (𝑣)=0and for all𝑤such that𝑣≠𝑤, by Equation (1) we have 0=(𝑀𝐶) 𝑣,𝑤 =𝜆 𝑍 (𝑣) −1 (𝐴𝐶) 𝑣,𝑤 . Since𝜆 𝑍 (𝑣)≠0(as𝜆(𝑣)≠(0,0)), this implies(𝐴𝐶) 𝑣,𝑤 =0 and thus (FX) holds

  48. [48]

    Thus 𝐶𝑣,𝑣 =𝜆 𝑋 (𝑣), i.e

    For all𝑣such that𝜆 𝑋 (𝑣)≠0, by Equation (2), we have1=(𝑀𝐶) 𝑣,𝑣 =𝜆 𝑋 (𝑣) −1𝐶𝑣,𝑣 . Thus 𝐶𝑣,𝑣 =𝜆 𝑋 (𝑣), i.e. (C2) holds. P . Mitosek & M. Backens23

  49. [49]

    This implies𝐶𝑣,𝑤 =0and thus (FZ) holds

    Finally, for all𝑣such that𝜆 𝑋 (𝑣)≠0and for all𝑤such that𝑣≠𝑤, by Equation 2 we have 0=(𝑀𝐶) 𝑣,𝑤 =𝜆 𝑋 (𝑣) −1𝐶𝑣,𝑤 . This implies𝐶𝑣,𝑤 =0and thus (FZ) holds. Hence the desired properties are all satisfied. (⇐):Suppose the four properties hold. We must show that(𝑀𝐶)𝑣,𝑣 =1and(𝑀𝐶) 𝑣,𝑤 =0for all 𝑣≠𝑤∈ ¯𝑂. Observethatallfourpointsinthe(⇒)partoftheproofarereversible. ...

  50. [50]

    Then(𝑁𝐶) 𝑣,𝑣 =−𝜆 𝑍 (𝑣)𝐶 𝑣,𝑣 which equals0if and only if𝐶𝑣,𝑣 =0

    Suppose𝜆 𝑋 (𝑣)=0. Then(𝑁𝐶) 𝑣,𝑣 =−𝜆 𝑍 (𝑣)𝐶 𝑣,𝑣 which equals0if and only if𝐶𝑣,𝑣 =0. Consid- ering all𝑣with𝜆 𝑋 (𝑣)=0, we obtain equivalence of(𝑁𝐶) 𝑣,𝑣 =0to (C3)

  51. [51]

    By the assumption that𝐶satisfies (C2), we have𝐶𝑣,𝑣 =𝜆 𝑋 (𝑣)

    Suppose𝜆 𝑋 (𝑣)≠0. By the assumption that𝐶satisfies (C2), we have𝐶𝑣,𝑣 =𝜆 𝑋 (𝑣). Then: (𝑁𝐶) 𝑣,𝑣 =𝜆 𝑋 (𝑣) (𝐴𝐶) 𝑣,𝑣 −𝜆 𝑍 (𝑣)𝐶 𝑣,𝑣 =𝜆 𝑋 (𝑣) (𝐴𝐶) 𝑣,𝑣 −𝜆 𝑍 (𝑣)𝜆 𝑋 (𝑣)=𝜆 𝑋 (𝑣) ((𝐴𝐶) 𝑣,𝑣 −𝜆 𝑍 (𝑣)) whichequals0ifandonlyif(𝐴𝐶) 𝑣,𝑣 =𝜆 𝑍 (𝑣). Consideringall𝑣with𝜆 𝑋 ≠0,weobtainequivalence of(𝑁𝐶) 𝑣,𝑣 =0to (C4). Thus, the above two cases imply that the main diagonal of𝑁𝐶...

  52. [52]

    By the assumption that𝐶satisfies (FX), we have(𝐴𝐶) 𝑣,𝑤 =0

    Suppose𝜆 𝑋 (𝑣)=0. By the assumption that𝐶satisfies (FX), we have(𝐴𝐶) 𝑣,𝑤 =0. Thus the condition of (O1) does not hold. Ergo the condition of (O2) necessarily applies, leading to 𝐶𝑣,𝑤 ≠0. Therefore (3) becomes: (𝑁𝐶) 𝑣,𝑤 =𝜆 𝑋 (𝑣) (𝐴𝐶) 𝑣,𝑤 −𝜆 𝑍 (𝑣)𝐶 𝑣,𝑤 =−𝜆 𝑍 (𝑣)𝐶 𝑣,𝑤 ≠0 24Working with measurement-based computations on qudits

  53. [53]

    Bytheassumptionthat𝐶satisfies(FZ),wehave𝐶 𝑣,𝑤 =0

    Suppose𝜆 𝑋 (𝑣)≠0. Bytheassumptionthat𝐶satisfies(FZ),wehave𝐶 𝑣,𝑤 =0. Thusthecondition of (O2) does not apply. Ergo the condition of (O1) necessarily applies, leading to(𝐴𝐶)𝑣,𝑤 ≠0. Therefore (3) becomes: (𝑁𝐶) 𝑣,𝑤 =𝜆 𝑋 (𝑣) (𝐴𝐶) 𝑣,𝑤 −𝜆 𝑍 (𝑣)𝐶 𝑣,𝑤 =𝜆 𝑋 (𝑣) (𝐴𝐶) 𝑣,𝑤 ≠0 In both cases,(𝑁𝐶)𝑣,𝑤 ≠0as desired. (⇐): Suppose that(𝑁𝐶) 𝑣,𝑤 ≠0, which means: 𝜆𝑋 (𝑣) (𝐴𝐶) 𝑣,...

  54. [54]

    This implies(𝐴®𝒶) 𝑣 =0, i.e.𝑣∉supp ( 𝐴®𝒶)

    Suppose𝜆 𝑋 (𝑣)=0, then: 0=(𝑀®𝒶) 𝑣 = ∑︁ 𝑢∈ ¯𝐼 𝑀𝑣,𝑢 ®𝒶𝑢 =𝜆 𝑍 (𝑣) −1 ∑︁ 𝑢∈ ¯𝐼 𝐴𝑣,𝑢 ®𝒶𝑢 =𝜆 𝑍 (𝑣) −1 (𝐴®𝒶)𝑣 Since𝜆 𝑋 (𝑣)=0, necessarily𝜆 𝑍 (𝑣)≠0. This implies(𝐴®𝒶) 𝑣 =0, i.e.𝑣∉supp ( 𝐴®𝒶). By contra- position: if𝑣∈supp ( 𝐴®𝒶), then𝜆𝑋 (𝑣)≠0, i.e. (Fs2) holds

  55. [55]

    Since𝑀 𝑣,𝑢 =0for𝑣≠𝑢, we have: 0=(𝑀®𝒶) 𝑣 = ∑︁ 𝑢∈ ¯𝐼 𝑀𝑣,𝑢 ®𝒶𝑢 =𝜆 𝑋 (𝑣) −1 ®𝒶𝑣 Then as𝜆 𝑋 (𝑣)≠0, we have®𝒶𝑣 =0, i.e.𝑣∉supp ( ®𝒶)

    Suppose𝜆 𝑋 (𝑣)≠0. Since𝑀 𝑣,𝑢 =0for𝑣≠𝑢, we have: 0=(𝑀®𝒶) 𝑣 = ∑︁ 𝑢∈ ¯𝐼 𝑀𝑣,𝑢 ®𝒶𝑢 =𝜆 𝑋 (𝑣) −1 ®𝒶𝑣 Then as𝜆 𝑋 (𝑣)≠0, we have®𝒶𝑣 =0, i.e.𝑣∉supp ( ®𝒶). Again by contraposition: if𝑣∈supp ( 𝐴), then𝜆 𝑋 (𝑣)=0, meaning (Fs1) holds. Hence®𝒶satisfies conditions (Fs1) and (Fs2) over the set{𝑣}as required. (⇐): Let®𝒶be focused over{𝑣}. Once again, we consider two cases ...

  56. [56]

    Following the same sequence of equalities as in the first case of the(⇒)part of the proof, we find(𝑀®𝒶)𝑣 =0

    Suppose𝜆 𝑋 (𝑣)=0, then by (Fs2):𝑣∉supp ( 𝐴®𝒶), i.e.(𝐴®𝒶)𝑣 =0. Following the same sequence of equalities as in the first case of the(⇒)part of the proof, we find(𝑀®𝒶)𝑣 =0

  57. [57]

    pivot simplification

    Suppose𝜆 𝑋 (𝑣)≠0, then by (Fs1):𝑣∉supp ( ®𝒶), i.e.( ®𝒶)𝑣 =0. Following the same sequence of equalities as in the second case of the(⇒)part of the proof, we again find(𝑀®𝒶)𝑣 =0. Therefore,(𝑀®𝒶)𝑣 =0, meaning𝑣∉supp (𝑀®𝒶), ergo𝑣∈𝐹 ®𝒶, which ends the proof.□ Using the above lemma, we find that the kernel of the flow-demand matrix forms is exactly the set of fo...