Shadow Pauli Flow: Characterising Determinism in MBQCs involving Pauli Measurements

Mehdi Mhalla; Simon Perdrix; Luc Sanselme

doi:10.22331/q-2026-07-16-2163

Shadow Pauli Flow: Characterising Determinism in MBQCs involving Pauli Measurements

Mehdi Mhalla¹, Simon Perdrix², and Luc Sanselme^2,3

¹Université Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France
²Inria Mocqua, LORIA, CNRS, Université de Lorraine, F-54000 Nancy, France
³Lycée Poincaré

Published:	2026-07-16, volume 10, page 2163
Eprint:	arXiv:2207.09368v5
Doi:	https://doi.org/10.22331/q-2026-07-16-2163
Citation:	Quantum 10, 2163 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce a new characterisation of determinism in Measurement-Based Quantum Computing (MBQC). The one-way model consists in performing local measurements over a large entangled state represented by a graph. The ability to perform an overall deterministic computation requires a correction strategy because of the non-determinism of each measurement. The existence of such a correction strategy depends on the underlying open graph, which is a description of the resource state together with the basis of the performed measurements. GFlow is a well-known graphical characterisation of robust determinism in MBQC when every measurement is performed in some specific planes of the Bloch sphere. While Pauli measurements are ubiquitous in MBQC, GFlow fails to be necessary for determinism when a measurement-based quantum computation involves Pauli measurements. Pauli Flow was designed as a generalisation of GFlow to handle MBQC with Pauli measurements, and guarantees robust determinism, however, it has been shown more recently that it fails to be a necessary condition. Our contribution is twofold. First, we demonstrate that Pauli flow is actually necessary for robust determinism in a weaker sense: given an open graph, i.e. a resource state, a deterministic computation can be driven iff it has a Pauli flow. However, the Pauli flows do not reflect all the possible correction strategies over a particular resource state, and properties like measurement order or computational depth are not necessarily reflected by a Pauli flow. Thus, to characterise determinism in full generality, we introduce a further extension called Shadow Pauli Flow that we prove necessary and sufficient for robust determinism: An MBQC is robustly deterministic if and only if its correction strategy is consistent with a Shadow Pauli flow. Furthermore, we show that Shadow Pauli flow can be computed in polynomial time.

► BibTeX data

@article{Mhalla2026shadowpauliflow,
  doi = {10.22331/q-2026-07-16-2163},
  url = {https://doi.org/10.22331/q-2026-07-16-2163},
  title = {Shadow {P}auli {F}low: {C}haracterising {D}eterminism in {MBQC}s involving {P}auli {M}easurements},
  author = {Mhalla, Mehdi and Perdrix, Simon and Sanselme, Luc},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2163},
  month = jul,
  year = {2026}
}

► References

[1] M. Backens, H. Miller-Bakewell, G. De Felice, L. Lobski, and J. Van De Wetering, ``There and back again: A circuit extraction tale'' Quantum 5, 421 (2021).
https://doi.org/10.22331/q-2021-03-25-421

[2] S. Bartolucci, P. Birchall, H. Bombin, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, and M. Pant, ``Fusion-based quantum computation'' Nature Communications 14, 912 (2023).
https://doi.org/10.1038/s41467-023-36493-1

[3] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, ``Measurement-based quantum computation'' Nature Physics 5, 19–26 (2009).
https://doi.org/10.1038/nphys1157

[4] D. Browne, E. Kashefi, and S. Perdrix, ``Computational depth complexity of measurement-based quantum computation'' Proceedings of the Conference on Quantum Computation, Communication, and Cryptography 35–46 (2010).
https://doi.org/10.1007/978-3-642-18073-6_4

[5] D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, ``Generalized flow and determinism in measurement-based quantum computation'' New Journal of Physics 9, 250 (2007).
https://doi.org/10.48550/arXiv.quant-ph/0702212

[6] V. Danosand E. Kashefi ``Determinism in the one-way model'' Physical Review A 74, 052310 (2006).
https://doi.org/10.1103/PHYSREVA.74.052310

[7] V. Danos, E. Kashefi, and P. Panangaden, ``The measurement calculus'' Journal of the ACM (JACM) 54, 8–es (2007).
https://doi.org/10.1145/1219092.1219096

[8] R. Duncanand S. Perdrix ``Rewriting measurement-based quantum computations with generalized flow'' Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) 285–296 (2010).
https://doi.org/10.1007/978-3-642-14162-1_24

[9] R. Duncan, A. Kissinger, S. Perdrix, and J. Van De Wetering, ``Graph-theoretic simplification of quantum circuits with the ZX-calculus'' Quantum 4, 279 (2020).
https://doi.org/10.22331/q-2020-06-04-279

[10] R. R. Ferguson, L. Dellantonio, A. A. Balushi, K. Jansen, W. Dür, and C. A. Muschik, ``Measurement-based variational quantum eigensolver'' Physical Review Letters 126, 220501 (2021).
https://doi.org/10.1103/PhysRevLett.126.220501

[11] D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia, ``Measurement-based quantum computation beyond the one-way model'' Physical Review A 76, 052315 (2007).
https://doi.org/10.1103/PhysRevA.76.052315

[12] T. McElvanneyand M. Backens ``Complete flow-preserving rewrite rules for MBQC patterns with Pauli measurements'' QPL 2022, arXiv preprint arXiv:2205.02009 (2022).
https://doi.org/10.4204/EPTCS.394.5

[13] M. Mhallaand S. Perdrix ``Graph States, Pivot Minor, and Universality of (X,Z)-Measurements'' International Journal of Unconventional Computing 9, 181–198 (2013).
https://doi.org/10.48550/arXiv.1202.6551

[14] M. Mhalla, M. Murao, S. Perdrix, M. Someya, and P. S. Turner, ``Which graph states are useful for quantum information processing?'' Theory of Quantum Computation, Communication, and Cryptography: 6th Conference, TQC 2011, Madrid, Spain, May 24-26, 2011, Revised Selected Papers 6 174–187 (2014).
https://doi.org/10.48550/arXiv.1006.2616

[15] Piotr Mitosekand Miriam Backens ``An algebraic formulation of Pauli flow, leading to faster flow-finding algorithms'' Journal of Physics A: Mathematical and Theoretical 59, 035301 (2026).
https://doi.org/10.1088/1751-8121/ae2999

[16] S. Perdrixand L. Sanselme ``Determinism and computational power of real measurement-based quantum computation'' Proceedings of the International Symposium on Fundamentals of Computation Theory 395–408 (2017).
https://doi.org/10.1007/978-3-662-55751-8_31

[17] R. Raussendorf ``Measurement-based quantum computation with cluster states'' International Journal of Quantum Information 7, 1053–1203 (2009).
https://doi.org/10.1103/PhysRevA.68.022312

[18] R. Raussendorfand H. J. Briegel ``A one-way quantum computer'' Physical Review Letters 86, 5188–5191 (2001).
https://doi.org/10.1103/PhysRevLett.86.5188

[19] R. Raussendorfand H. J. Briegel ``Quantum computing via measurements only'' arXiv preprint quant-ph/0010033 (2000).
https://doi.org/10.48550/arXiv.quant-ph/0010033

[20] R. Raussendorf, J. Harrington, and K. Goyal, ``Topological fault-tolerance in cluster state quantum computation'' New Journal of Physics 9, 199 (2007).
https://doi.org/10.1088/1367-2630/9/6/199

[21] A. Schroeder, M. Heller, and M. Gachechiladze, ``Deterministic Ansätze for the measurement-based variational quantum eigensolver'' New Journal of Physics (2023).
https://doi.org/10.1088/1367-2630/ad51e5

[22] W. Simmons ``Relating measurement patterns to circuits via Pauli flow'' QPL 2021, arXiv preprint arXiv:2109.05654 (2021).
https://doi.org/10.4204/EPTCS.343.4

Cited by

Could not fetch Crossref cited-by data during last attempt 2026-07-16 10:00:34: Could not fetch cited-by data for 10.22331/q-2026-07-16-2163 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-07-16 10:00:34: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.