Universal MBQC with generalised parity-phase interactions and Pauli measurements
Radboud University Nijmegen
| Published: | 2019-04-26, volume 3, page 134 |
| Eprint: | arXiv:1704.06504v3 |
| Doi: | https://doi.org/10.22331/q-2019-04-26-134 |
| Citation: | Quantum 3, 134 (2019). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form $\exp(-i\frac{\pi}{2^{n}} Z\otimes Z)$. When $n = 2$, these are equivalent, up to local Clifford unitaries, to graph states. However, when $n \gt 2$, their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli $Z$ and $X$ measurements and feed-forward. Even though, for $n \gt 2$, the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every $n \gt 2$ this family is capable of producing all Clifford gates and all diagonal gates in the $n$-th level of the Clifford hierarchy.
Popular summary
However, other paradigms exist for defining quantum programs, some of which having no classical analogue. One such paradigm is measurement-based quantum computing (MBQC). In MBQC, one starts with a fixed state on many qubits and simply measures it one qubit at a time. The key point, however, is one is free to choose single-qubit measurements (which can be pictured as an axis in 3D space) on the fly, and adapt those choices based on previous measurement outcomes. Using this adaptation, known as feed-forward, one can obtain models for computation which are deterministic (always perform the desired computation) and universal (just as powerful as the circuit model).
Since its introduction in 2001, the one-way model has been a paradigmatic example of a scheme for universal MBQC. It relies crucially on the initial state being a certain kind of highly-entangled stabilizer state called a graph state. Stabilizer states are a well-understood class of quantum states which can be efficiently characterised and manipulated in terms of an associated group called its stabilizer subgroup. In particular, the generators of this group can be used to compute how measurements should be adapted during a computation to obtain the desired outcome with 100% success.
While stabilizer techniques are powerful and very well-understood, once one considers models based on more general families of (non-stabilizer) states, these techniques no longer apply. Furthermore, if one restricts to "stabilizer" measurements (i.e. qubit measurements along the X, Y, and Z axes), the outcome of the entire computation is efficient to compute on a classical computer. Hence, all of the "quantumness" on the one-way model comes from choosing measurements which do not lie on the X, Y, or Z axes.
In this paper, we introduce a new family of models for MBQC where this extra "quantumness" is baked into the initial state, and hence it is no longer a stabilizer state. As a result, this model is universal even when restricting measurements to just the X and Z axes. Moreover, our model is still deterministic, and can implement the popular Clifford+T gate set natively.
In order to reason with non-stabilizer states, we need a more powerful language then just the stabilizer formalism: the ZX-calculus. The ZX-calculus can be seen as a sort of "supercharged stabilizer theory", which represents quantum states and transformations using particular tensor networks called ZX-diagrams. These diagrams satisfy graphical transformation rules which subsume the equations provable by stabilizer techniques and go quite some distance beyond. For our purposes, the ZX-calculus gives us a much richer and more flexible notion of "feed-forward" than the one provided by stabilizer theory and opens the door to previously unconsidered ways of doing universal, deterministic quantum computations.
► BibTeX data
► References
[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328
[2] Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. New Journal of Physics, 16 (9): 093021, 2014. 10.1088/1367-2630/16/9/093021.
https://doi.org/10.1088/1367-2630/16/9/093021
[3] Miriam Backens and Aleks Kissinger. ZH: A complete graphical calculus for quantum computations involving classical non-linearity. arXiv preprint arXiv:1805.02175, 2018. 10.4204/EPTCS.287.2.
https://doi.org/10.4204/EPTCS.287.2
arXiv:1805.02175
[4] CJ Ballance, TP Harty, NM Linke, MA Sepiol, and DM Lucas. High-Fidelity Quantum Logic Gates Using Trapped-Ion Hyperfine Qubits. Physical Review Letters, 117 (6): 060504, 2016. 10.1103/PhysRevLett.117.060504.
https://doi.org/10.1103/PhysRevLett.117.060504
[5] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103/PhysRevA.71.022316.
https://doi.org/10.1103/PhysRevA.71.022316
[6] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal Blind Quantum Computation. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 517–526. IEEE, 2009. 10.1109/FOCS.2009.36.
https://doi.org/10.1109/FOCS.2009.36
[7] Daniel 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, 2007. 10.1088/1367-2630/9/8/250.
https://doi.org/10.1088/1367-2630/9/8/250
[8] B. Coecke and R. Duncan. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13: 043016, 2011. 10.1088/1367-2630/13/4/043016. arXiv:quant-ph/09064725.
https://doi.org/10.1088/1367-2630/13/4/043016
arXiv:quant-ph/09064725
[9] B. Coecke and A. Kissinger. Picturing Quantum Processes. Cambridge University Press, 2017. ISBN 9781107104228. 10.1017/9781316219317.
https://doi.org/10.1017/9781316219317
[10] Shawn X Cui, Daniel Gottesman, and Anirudh Krishna. Diagonal gates in the Clifford hierarchy. Physical Review A, 95 (1): 012329, 2017. 10.1103/PhysRevA.95.012329.
https://doi.org/10.1103/PhysRevA.95.012329
[11] R. Duncan and S. Perdrix. Rewriting Measurement-Based Quantum Computations with Generalised Flow. In Proceedings of ICALP, Lecture Notes in Computer Science, pages 285–296. Springer, 2010. 10.1007/978-3-642-14162-1_24.
https://doi.org/10.1007/978-3-642-14162-1_24
[12] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. arXiv preprint arXiv:1902.03178, 2019.
arXiv:1902.03178
[13] Mariami Gachechiladze, Otfried Gühne, and Akimasa Miyake. Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states. arXiv preprint arXiv:1805.12093, 2018.
arXiv:1805.12093
[14] JP Gaebler, TR Tan, Y Lin, Y Wan, R Bowler, AC Keith, S Glancy, K Coakley, E Knill, D Leibfried, et al. High-Fidelity Universal Gate Set for Be 9+ Ion Qubits. Physical Review Letters, 117 (6): 060505, 2016. 10.1103/PhysRevLett.117.060505.
https://doi.org/10.1103/PhysRevLett.117.060505
[15] Mercedes Gimeno-Segovia, Pete Shadbolt, Dan E Browne, and Terry Rudolph. From Three-Photon Greenberger-Horne-Zeilinger States to Ballistic Universal Quantum Computation. Physical review letters, 115 (2): 020502, 2015. 10.1103/PhysRevLett.115.020502.
https://doi.org/10.1103/PhysRevLett.115.020502
[16] D. Gottesman and I. L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390–393, 1999. 10.1038/46503.
https://doi.org/10.1038/46503
[17] D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia. Measurement-based quantum computation beyond the one-way model. Phys. Rev. A, 76: 052315, Nov 2007. 10.1103/PhysRevA.76.052315.
https://doi.org/10.1103/PhysRevA.76.052315
[18] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Complete Axiomatisation of the ZX-calculus for Clifford+T Quantum Mechanics. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 559–568. ACM, 2018. 10.1145/3209108.3209131.
https://doi.org/10.1145/3209108.3209131
[19] Aleks Kissinger and John van de Wetering. Pyzx: Large scale automated diagrammatic reasoning. arXiv preprint arXiv:1904.04735, 2019.
arXiv:1904.04735
[20] Aleks Kissinger and Vladimir Zamdzhiev. Quantomatic: A proof assistant for diagrammatic reasoning. In International Conference on Automated Deduction, pages 326–336. Springer, 2015. 10.1007/978-3-319-21401-6_22.
https://doi.org/10.1007/978-3-319-21401-6_22
[21] Damian Markham and Elham Kashefi. Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation, pages 427–453. Lecture Notes in Computer Science. Springer International Publishing, 2014. ISBN 978-3-319-06879-4. 10.1007/978-3-319-06880-0_22.
https://doi.org/10.1007/978-3-319-06880-0_22
[22] Jacob Miller and Akimasa Miyake. Hierarchy of universal entanglement in 2D measurement-based quantum computation. npj Quantum Information, 2: 16036, 2016. 10.1038/npjqi.2016.36.
https://doi.org/10.1038/npjqi.2016.36
[23] Sam Morley-Short, Sara Bartolucci, Mercedes Gimeno-Segovia, Pete Shadbolt, Hugo Cable, and Terry Rudolph. Physical-depth architectural requirements for generating universal photonic cluster states. Quantum Science and Technology, 3 (1): 015005, 2017. 10.1088/2058-9565/aa913b.
https://doi.org/10.1088/2058-9565/aa913b
[24] K. F. Ng and Q. Wang. A universal completion of the ZX-calculus. ArXiv e-prints, jun 2017.
[25] JS Otterbach, R Manenti, N Alidoust, A Bestwick, M Block, B Bloom, S Caldwell, N Didier, E Schuyler Fried, S Hong, et al. Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771, 2017.
arXiv:1712.05771
[26] R. Penrose. Applications of negative dimensional tensors. In Combinatorial Mathematics and its Applications, pages 221–244. Academic Press, 1971.
[27] R. Raussendorf, D.E. Browne, and H.J. Briegel. Measurement-based quantum computation on cluster states. Physical Review A, 68 (2): 22312, 2003. ISSN 1094-1622. 10.1103/PhysRevA.68.022312.
https://doi.org/10.1103/PhysRevA.68.022312
[28] Robert Raussendorf and Hans J. Briegel. A One-Way Quantum Computer. Phys. Rev. Lett., 86: 5188–5191, May 2001. 10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188
[29] Yaoyun Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computation. arXiv preprint quant-ph/0205115, 2002.
arXiv:quant-ph/0205115
[30] Anders Sørensen and Klaus Mølmer. Quantum computation with ions in thermal motion. Physical review letters, 82 (9): 1971, 1999. 10.1103/PhysRevLett.82.1971.
https://doi.org/10.1103/PhysRevLett.82.1971
[31] Yuki Takeuchi, Tomoyuki Morimae, and Masahito Hayashi. Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements. arXiv preprint arXiv:1809.07552, 2018.
arXiv:1809.07552
[32] R Versluis, S Poletto, N Khammassi, N Haider, DJ Michalak, A Bruno, K Bertels, and L DiCarlo. Scalable Quantum Circuit and Control for a Superconducting Surface Code. arXiv preprint arXiv:1612.08208, 2016. 10.1103/PhysRevApplied.8.034021.
https://doi.org/10.1103/PhysRevApplied.8.034021
arXiv:1612.08208
[33] P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. Aspelmeyer, and A. Zeilinger. Experimental one-way quantum computing. Nature, 434: 169–176, 2005. 10.1038/nature03347.
https://doi.org/10.1038/nature03347
Cited by
[1] Selma Dündar-Coecke, Lia Yeh, Caterina Puca, Sieglinde M.-L. Pfaendler, Muhammad Hamza Waseem, Thomas Cervoni, Aleks Kissinger, Stefano Gogioso, and Bob Coecke, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 21 (2023) ISBN:979-8-3503-4323-6.
[2] John van de Wetering, "Constructing quantum circuits with global gates", New Journal of Physics 23 4, 043015 (2021).
[3] Quan Junyu, Wang Yuxun, Li Peishan, Yanyan Feng, and Qin Li, "Strictly universal hypergraph states for measurement-based blind quantum computation", (2026).
[4] Darren W. Moore, "Quantum hypergraph states in continuous variables", Physical Review A 100 6, 062301 (2019).
[5] Junyu Quan, Yuxun Wang, Peishan Li, Yanyan Feng, and Qin Li, "Strictly universal hypergraph states for measurement-based blind quantum computation", Optics & Laser Technology 203, 115531 (2026).
[6] Aleks Kissinger and John van de Wetering, "Reducing the number of non-Clifford gates in quantum circuits", Physical Review A 102 2, 022406 (2020).
[7] Hironari Nagayoshi, Warit Asavanant, Ryuhoh Ide, Kosuke Fukui, Atsushi Sakaguchi, Jun-ichi Yoshikawa, Nicolas C. Menicucci, and Akira Furusawa, "ZX graphical calculus for continuous-variable quantum processes", Physical Review Research 7 3, 033141 (2025).
[8] Richard D.P. East, John van de Wetering, Nicholas Chancellor, and Adolfo G. Grushin, "AKLT-States as ZX-Diagrams: Diagrammatic Reasoning for Quantum States", PRX Quantum 3 1, 010302 (2022).
[9] Mithün Paul, Tiju Cherian John, and Nithin Raveendran, Communications in Computer and Information Science 2659, 93 (2026) ISBN:978-3-032-13882-8.
[10] Yuki Takeuchi, "Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation", Physical Review Letters 133 5, 050601 (2024).
[11] Yuki Takeuchi, Tomoyuki Morimae, and Masahito Hayashi, "Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements", Scientific Reports 9 1, 13585 (2019).
[12] Sebastiano Corli and Enrico Prati, "Measurement-based quantum compiling via gauge invariance", Physical Review Applied 25 4, 044068 (2026).
[13] Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering, and Sal Wolffs, "Completeness of the ZH-calculus", Compositionality 5, 5 (2023).
[14] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao, and Shashank Virmani, "Efficient classical simulation of cluster state quantum circuits with alternative inputs", Quantum 8, 1243 (2024).
[15] Aleks Kissinger and John van de Wetering, "PyZX: Large Scale Automated Diagrammatic Reasoning", Electronic Proceedings in Theoretical Computer Science 318, 229 (2020).
[16] Bob Coecke, Dominic Horsman, Aleks Kissinger, and Quanlong Wang, "Kindergarden quantum mechanics graduates ...or how I learned to stop gluing LEGO together and love the ZX-calculus", Theoretical Computer Science 897, 1 (2022).
[17] Masahito Hayashi and Yuki Takeuchi, "Verifying commuting quantum computations via fidelity estimation of weighted graph states", New Journal of Physics 21 9, 093060 (2019).
[18] Boldizsár Poór, Quanlong Wang, Razin A. Shaikh, Lia Yeh, Richie Yeung, and Bob Coecke, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 1 (2023) ISBN:979-8-3503-3587-3.
[19] Sebastiano Corli and Enrico Prati, "Gauge freedom in measurement based quantum compiling", Journal of Physics: Conference Series 3017 1, 012043 (2025).
[20] Yanbin Chen, Innocenzo Fulginiti, and Christian B. Mendl, Lecture Notes in Computer Science 15911, 150 (2025) ISBN:978-3-031-97569-1.
[21] 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 (2021).
[22] Tuomas Laakkonen, Konstantinos Meichanetzidis, and John van de Wetering, "Picturing Counting Reductions with the ZH-Calculus", Electronic Proceedings in Theoretical Computer Science 384, 89 (2023).
[23] Harashta Tatimma Larasati and Byung-Soo Choi, "Circuit-based vs. measurement-based quantum computing: a comparative analysis, layered metrics, and decision flow for approach selection", EPJ Quantum Technology 13 1, 39 (2026).
[24] Anna Schroeder, Matthias Heller, and Mariami Gachechiladze, "Deterministic Ansätze for the measurement-based variational quantum eigensolver", New Journal of Physics 26 6, 063019 (2024).
[25] Tobias Stollenwerk and Stuart Hadfield, 2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) 1115 (2024) ISBN:979-8-3503-6460-6.
[26] Quanlong Wang, Richie Yeung, and Mark Koch, "Differentiating and Integrating ZX Diagrams with Applications to Quantum Machine Learning", Quantum 8, 1491 (2024).
[27] Shuxiang Cao, "Multi-agent blind quantum computation without universal cluster states", New Journal of Physics 25 10, 103028 (2023).
[28] Selma Dündar-Coecke, Lia Yeh, Emmanuel Pothos, Muhammad Hamza Waseem, and Bob Coecke, "Beyond symbolic algebra with quantum picturalism", Frontiers in Cognition 5, 1790789 (2026).
[29] Boldizsár Poór, Quanlong Wang, Razin A. Shaikh, Lia Yeh, Richie Yeung, and Bob Coecke, "Completeness for arbitrary finite dimensions of ZXW-calculus, a unifying calculus", arXiv:2302.12135, (2023).
[30] Quanlong Wang, Richard D. P. East, Razin A. Shaikh, Lia Yeh, Boldizsár Poór, and Bob Coecke, "Beyond Penrose tensor diagrams with the ZX calculus: Applications to quantum computing, quantum machine learning, condensed matter physics, and quantum gravity", arXiv:2511.06012, (2025).
[31] Richard D. P. East, Pierre Martin-Dussaud, and John Van de Wetering, "Spin-networks in the ZX-calculus", arXiv:2111.03114, (2021).
[32] Haytham McDowall-Rose, Razin A. Shaikh, and Lia Yeh, "From Fermions to Qubits: A ZX-Calculus Perspective", arXiv:2505.06212, (2025).
[33] Quanlong Wang, Boldizsár Poór, and Razin A. Shaikh, "Completeness of qufinite ZXW calculus, a graphical language for finite-dimensional quantum theory", arXiv:2309.13014, (2023).
[34] Titouan Carette, Dominic Horsman, and Simon Perdrix, "SZX-calculus: Scalable Graphical Quantum Reasoning", arXiv:1905.00041, (2019).
[35] Emmanuel Jeandel, Simon Perdrix, and Margarita Veshchezerova, "Addition and Differentiation of ZX-diagrams", arXiv:2202.11386, (2022).
[36] John van de Wetering, "Quantum Theory from Principles, Quantum Software from Diagrams", arXiv:2101.03608, (2021).
[37] Tuomas Laakkonen, Konstantinos Meichanetzidis, and John van de Wetering, "Picturing Counting Reductions with the ZH-Calculus", arXiv:2304.02524, (2023).
[38] Aleks Kissinger and John van de Wetering, "ZX-Flow: A Flexible Criterion for Deterministic Computation with ZX-Diagrams", arXiv:2603.09580, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 13:48:55) and SAO/NASA ADS (last updated successfully 2026-07-15 13:49:00). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.