# Universal MBQC with generalised parity-phase interactions and Pauli measurements

### 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.

Much like in classical computation, a quantum program can be described using different programming paradigms. By far the most common such paradigm in the quantum world is the circuit model, which is roughly the quantum analogue of a low-level procedural language. Here, one or more quantum registers are prepared in a fixed initial state, acted upon by a sequence of primitive quantum gates, and measured at the end to produce the output of a computation.

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.

### ► 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] 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).

[2] Masahito Hayashi and Yuki Takeuchi, "Verifying commuting quantum computations via fidelity estimation of weighted graph states", New Journal of Physics 21 9, 093060 (2019).

The above citations are from Crossref's cited-by service (last updated 2019-11-13 08:35:36). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data (last attempt 2019-11-13 08:35:36): cURL error 28: Operation timed out after 10000 milliseconds with 0 bytes received