1University of Birmingham
2University of Oxford
3ILLC, University of Amsterdam (until 2020)
4Radboud University Nijmegen
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Translations between the quantum circuit model and the measurement-based one-way model are useful for verification and optimisation of quantum computations. They make crucial use of a property known as gflow. While gflow is defined for one-way computations allowing measurements in three different planes of the Bloch sphere, most research so far has focused on computations containing only measurements in the XY-plane. Here, we give the first circuit-extraction algorithm to work for one-way computations containing measurements in all three planes and having gflow. The algorithm is efficient and the resulting circuits do not contain ancillae. One-way computations are represented using the ZX-calculus, hence the algorithm also represents the most general known procedure for extracting circuits from ZX-diagrams. In developing this algorithm, we generalise several concepts and results previously known for computations containing only XY-plane measurements. We bring together several known rewrite rules for measurement patterns and formalise them in a unified notation using the ZX-calculus. These rules are used to simplify measurement patterns by reducing the number of qubits while preserving both the semantics and the existence of gflow. The results can be applied to circuit optimisation by translating circuits to patterns and back again.
Popular summary
Translations between these two models are useful for optimisation (e.g. time taken or number of gates used) and for verification (i.e. confirming that the computation does indeed perform the desired procedure). While it is easy to translate from circuits to measurement-based computations, previous algorithms for translating measurement-based computations into circuits did not work in all cases.
In this work we give the first translation algorithm that works for all measurement-based computations with a property called extended gflow, which encompasses all the computations that are usually studied. We then use the algorithm to optimise quantum circuits by translating them into the measurement-based model and back. The translations are performed using the ZX-calculus, a graphical language that can express both quantum circuits and measurement-based 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] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32 (6): 818–830, 2013. 10.1109/TCAD.2013.2244643.
https://doi.org/10.1109/TCAD.2013.2244643
[3] Matthew Amy, Dmitri Maslov, and Michele Mosca. Polynomial-time T-depth optimization of Clifford+ T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33 (10): 1476–1489, 2014. 10.1109/TCAD.2014.2341953.
https://doi.org/10.1109/TCAD.2014.2341953
[4] Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. New Journal of Physics, 16 (9): 093021, 2014. ISSN 1367-2630. 10.1088/1367-2630/16/9/093021.
https://doi.org/10.1088/1367-2630/16/9/093021
[5] Miriam Backens. Making the stabilizer ZX-calculus complete for scalars. In Chris Heunen, Peter Selinger, and Jamie Vicary, editors, Proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015), volume 195 of Electronic Proceedings in Theoretical Computer Science, pages 17–32, 2015. 10.4204/EPTCS.195.2.
https://doi.org/10.4204/EPTCS.195.2
[6] Gregory Bard. Achieving a log(n) speed up for boolean matrix operations and calculating the complexity of the dense linear algebra step of algebraic stream ciper attacks and of integer factorization methods. IACR Cryptology ePrint Archive, 2006: 163, 01 2006.
[7] Xiaoning Bian and Peter Selinger. Relations for 2-qubit Clifford+T operator group, 2015. URL https://mathstat.dal.ca/ xbian/talks/slide_cliffordt2.pdf.
https://mathstat.dal.ca/~xbian/talks/slide_cliffordt2.pdf
[8] Anne Broadbent and Elham Kashefi. Parallelizing quantum circuits. Theoretical Computer Science, 410 (26): 2489–2510, 2009. 10.1016/j.tcs.2008.12.046.
https://doi.org/10.1016/j.tcs.2008.12.046
[9] 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
[10] Daniel E. Browne, Elham Kashefi, and Simon Perdrix. Computational depth complexity of measurement-based quantum computation. In Theory of Quantum Computation, Communication, and Cryptography (TQC’10), volume 6519, pages 35–46. LNCS, 2011. 10.1007/978-3-642-18073-6_4.
https://doi.org/10.1007/978-3-642-18073-6_4
[11] 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
[12] Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. ISBN 9781107104228. 10.1017/9781316219317.
https://doi.org/10.1017/9781316219317
[13] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, and Seyon Sivarajah. Phase Gadget Synthesis for Shallow Circuits. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 213–228. Open Publishing Association, 2020a. 10.4204/EPTCS.318.13.
https://doi.org/10.4204/EPTCS.318.13
[14] Alexander Cowtan, Will Simmons, and Ross Duncan. A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz. arXiv preprint arXiv:2007.10515, 2020b.
arXiv:2007.10515
[15] Raphael Dias da Silva and Ernesto F Galvão. Compact quantum circuits from one-way quantum computation. Physical Review A, 88 (1): 012319, 2013. 10.1103/physreva.88.012319.
https://doi.org/10.1103/physreva.88.012319
[16] Raphael Dias da Silva, Einar Pius, and Elham Kashefi. Global quantum circuit optimization. arXiv:1301.0351, 2013.
arXiv:1301.0351
[17] V. Danos and E. Kashefi. Determinism in the one-way model. Phys. Rev. A, 74 (052310), 2006. 10.1103/PhysRevA.74.052310.
https://doi.org/10.1103/PhysRevA.74.052310
[18] Vincent Danos, Elham Kashefi, and Prakash Panangaden. The measurement calculus. J. ACM, 54 (2), April 2007. 10.1145/1219092.1219096.
https://doi.org/10.1145/1219092.1219096
[19] Vincent Danos, Elham Kashefi, Prakash Panangaden, and Simon Perdrix. Extended Measurement Calculus, pages 235–310. Cambridge University Press, 2009. 10.1017/CBO9781139193313.008.
https://doi.org/10.1017/CBO9781139193313.008
[20] Niel de Beaudrap. Unitary-circuit semantics for measurement-based computations. International Journal of Quantum Information, 8 (01n02): 1–91, 2010. 10.1142/s0219749910006113.
https://doi.org/10.1142/s0219749910006113
[21] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Techniques to Reduce $pi/4$-Parity-Phase Circuits, Motivated by the ZX Calculus. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 131–149. Open Publishing Association, 2020. 10.4204/EPTCS.318.9.
https://doi.org/10.4204/EPTCS.318.9
[22] Olivia Di Matteo and Michele Mosca. Parallelizing quantum circuit synthesis. Quantum Science and Technology, 1 (1): 015003, 2016. 10.1088/2058-9565/1/1/015003.
https://doi.org/10.1088/2058-9565/1/1/015003
[23] Ross Duncan and Simon Perdrix. Graph states and the necessity of Euler decomposition. Mathematical Theory and Computational Practice, pages 167–177, 2009. 10.1007/978-3-642-03073-4_18.
https://doi.org/10.1007/978-3-642-03073-4_18
[24] Ross Duncan and Simon Perdrix. Rewriting measurement-based quantum computations with generalised flow. In International Colloquium on Automata, Languages, and Programming, pages 285–296. Springer, 2010. 10.1007/978-3-642-14162-1_24.
https://doi.org/10.1007/978-3-642-14162-1_24
[25] Ross Duncan and Simon Perdrix. Pivoting makes the ZX-calculus complete for real stabilizers. In Bob Coecke and Matty Hoban, editors, Proceedings of the 10th International Workshop on Quantum Physics and Logic (QPL), volume 171 of Electronic Proceedings in Theoretical Computer Science, pages 50–62. Open Publishing Association, 2014. 10.4204/EPTCS.171.5.
https://doi.org/10.4204/EPTCS.171.5
[26] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum, 4: 279, 6 2020. ISSN 2521-327X. 10.22331/q-2020-06-04-279.
https://doi.org/10.22331/q-2020-06-04-279
[27] Maryam Eslamy, Mahboobeh Houshmand, Morteza Saheb Zamani, and Mehdi Sedighi. Optimization of one-way quantum computation measurement patterns. International Journal of Theoretical Physics, 57 (11): 3296–3317, 2018. 10.1007/s10773-018-3844-x.
https://doi.org/10.1007/s10773-018-3844-x
[28] Amar Hadzihasanovic, Kang Feng Ng, and Quanlong Wang. Two Complete Axiomatisations of Pure-state Qubit Quantum Computing. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages 502–511, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5583-4. 10.1145/3209108.3209128.
https://doi.org/10.1145/3209108.3209128
[29] Nidhal Hamrit and Simon Perdrix. Reversibility in extended measurement-based quantum computation. In Jean Krivine and Jean-Bernard Stefani, editors, Reversible Computation, pages 129–138. Springer International Publishing, 2015. ISBN 978-3-319-20860-2. 10.1007/978-3-319-20860-2_8.
https://doi.org/10.1007/978-3-319-20860-2_8
[30] M. Hein, J. Eisert, and H. J. Briegel. Multiparty entanglement in graph states. Physical Review A, 69 (6): 062311, 2004. 10.1103/PhysRevA.69.062311.
https://doi.org/10.1103/PhysRevA.69.062311
[31] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M Nest, and H-J Briegel. Entanglement in graph states and its applications. In G. Casati, D. L. Shepelyansky, P. Zoller, and G. Benenti, editors, Quantum Computers, Algorithms and Chaos, volume 162 of Proceedings of the International School of Physics “Enrico Fermi”, pages 115–218. IOS Press Books, 2006. 10.3254/978-1-61499-018-5-115.
https://doi.org/10.3254/978-1-61499-018-5-115
[32] Mahboobeh Houshmand, Mehdi Sedighi, Morteza Saheb Zamani, and Kourosh Marjoei. Quantum circuit synthesis targeting to improve one-way quantum computation pattern cost metrics. ACM Journal on Emerging Technologies in Computing Systems (JETC), 13 (4): 55, 2017. 10.1145/3064834.
https://doi.org/10.1145/3064834
[33] Monireh Houshmand, Mahboobeh Houshmand, and Joseph F Fitzsimons. Minimal qubit resources for the realization of measurement-based quantum computation. Physical Review A, 98 (1): 012318, 2018. 10.1103/physreva.98.012318.
https://doi.org/10.1103/physreva.98.012318
[34] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Diagrammatic Reasoning Beyond Clifford+T Quantum Mechanics. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages 569–578, New York, NY, USA, 2018a. ACM. 10.1145/3209108.3209139.
https://doi.org/10.1145/3209108.3209139
[35] 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, LICS ’18, pages 559–568, New York, NY, USA, 2018b. ACM. 10.1145/3209108.3209131.
https://doi.org/10.1145/3209108.3209131
[36] Aleks Kissinger and Arianne Meijer-van de Griend. CNOT circuit extraction for topologically-constrained quantum memories. Quantum Information and Computation, 20: 581–596, 2020. 10.26421/QIC20.7-8.
https://doi.org/10.26421/QIC20.7-8
[37] Aleks Kissinger and John van de Wetering. Universal MBQC with generalised parity-phase interactions and Pauli measurements. Quantum, 3: 134, 2019. 10.22331/q-2019-04-26-134.
https://doi.org/10.22331/q-2019-04-26-134
[38] Aleks Kissinger and John van de Wetering. PyZX: Large Scale Automated Diagrammatic Reasoning. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 229–241. Open Publishing Association, 2020a. 10.4204/EPTCS.318.14.
https://doi.org/10.4204/EPTCS.318.14
[39] Aleks Kissinger and John van de Wetering. Reducing the number of non-Clifford gates in quantum circuits. Physical Review A, Vol.102-2, 102: 022406, 8 2020b. 10.1103/PhysRevA.102.022406.
https://doi.org/10.1103/PhysRevA.102.022406
[40] Vadym Kliuchnikov and Dmitri Maslov. Optimization of Clifford circuits. Phys. Rev. A, 88: 052307, 2013. 10.1103/PhysRevA.88.052307.
https://doi.org/10.1103/PhysRevA.88.052307
[41] Anton Kotzig. Eulerian lines in finite 4-valent graphs and their transformations. In Colloqium on Graph Theory Tihany 1966, pages 219–230. Academic Press, 1968.
[42] Mehdi Mhalla and Simon Perdrix. Finding optimal flows efficiently. In the 35th International Colloquium on Automata, Languages and Programming (ICALP), LNCS, volume 5125, pages 857–868, 2008. 10.1007/978-3-540-70575-8_70.
https://doi.org/10.1007/978-3-540-70575-8_70
[43] Mehdi Mhalla and Simon Perdrix. Graph states, pivot minor, and universality of (X, Z)-measurements. International Journal of Unconventional Computing, 9 (1–2): 153–171, 2012. https://arxiv.org/abs/1202.6551.
arXiv:1202.6551
[44] Mehdi Mhalla, Mio Murao, Simon Perdrix, Masato Someya, and Peter S Turner. Which graph states are useful for quantum information processing? In Conference on Quantum Computation, Communication, and Cryptography, pages 174–187. Springer, 2011. 10.1007/978-3-642-54429-3_12.
https://doi.org/10.1007/978-3-642-54429-3_12
[45] Jisho Miyazaki, Michal Hajdušek, and Mio Murao. Analysis of the trade-off between spatial and temporal resources for measurement-based quantum computation. Physical Review A, 91 (5): 052302, 2015. 10.1103/physreva.91.052302.
https://doi.org/10.1103/physreva.91.052302
[46] Kang Feng Ng and Quanlong Wang. A universal completion of the ZX-calculus. arXiv:1706.09877, 2017.
arXiv:1706.09877
[47] M. A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 10.1119/1.1463744.
https://doi.org/10.1119/1.1463744
[48] R. Raussendorf, D.E. Browne, and H.J. Briegel. Measurement-based quantum computation on cluster states. Physical Review A, 68 (2): 22312, 2003. 10.1103/physreva.68.022312.
https://doi.org/10.1103/physreva.68.022312
[49] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86: 5188–5191, 2001. 10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188
[50] M. Van den Nest, J. Dehaene, and B. De Moor. Graphical description of the action of local Clifford transformations on graph states. Physical Review A, 69 (2): 9422, 2004. 10.1103/physreva.69.022316.
https://doi.org/10.1103/physreva.69.022316
[51] Renaud Vilmart. A Near-Minimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–10, 2019. 10.1109/LICS.2019.8785765.
https://doi.org/10.1109/LICS.2019.8785765
Cited by
[1] Aleks Kissinger and John van de Wetering, “Reducing the number of non-Clifford gates in quantum circuits”, Physical Review A 102 2, 022406 (2020).
[2] Louis Lemonnier, John van de Wetering, and Aleks Kissinger, “Hypergraph simplification: Linking the path-sum approach to the ZH-calculus”, arXiv:2003.13564.
[3] Chen Zhao and Xiao-Shan Gao, “Analyzing the barren plateau phenomenon in training quantum neural network with the ZX-calculus”, arXiv:2102.01828.
[4] Richard D. P. East, John van de Wetering, Nicholas Chancellor, and Adolfo G. Grushin, “AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states”, arXiv:2012.01219.
[5] Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering, and Sal Wolffs, “Completeness of the ZH-calculus”, arXiv:2103.06610.
[6] John van de Wetering, “Quantum Theory from Principles, Quantum Software from Diagrams”, arXiv:2101.03608.
[7] Alexis Toumi, Richie Yeung, and Giovanni de Felice, “Diagrammatic Differentiation for Quantum Machine Learning”, arXiv:2103.07960.
[8] 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)”, arXiv:2102.10984.
The above citations are from SAO/NASA ADS (last updated successfully 2021-03-25 15:11:53). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-03-25 15:11:52: Could not fetch cited-by data for 10.22331/q-2021-03-25-421 from Crossref. This is normal if the DOI was registered recently.
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.
Coinsmart. Beste Bitcoin-Börse in Europa
Source: https://quantum-journal.org/papers/q-2021-03-25-421/
