Abstract
We show that the formalism of “Sum-Over-Path” (SOP), used for symbolically representing linear maps or quantum operators, together with a proper rewrite system, has the structure of a dagger-compact PROP. Several consequences arise from this observation:
– Morphisms of SOP are very close to the diagrams of the graphical calculus called ZH-Calculus, so we give a system of interpretation between the two
– A construction, called the discard construction, can be applied to enrich the formalism so that, in particular, it can represent the quantum measurement.
We also enrich the rewrite system so as to get the completeness of the Clifford fragments of both the initial formalism and its enriched version.
This work was made during a Postdoc funded by the project PIA-GDN/Quantex. Proofs can be found at arXiv:2003.05678
Chapter PDF
Similar content being viewed by others
Keywords
References
Amy, M.: Towards large-scale functional verification of universal quantum circuits. In: Selinger, P., Chiribella, G. (eds.) Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018. Electronic Proceedings in Theoretical Computer Science, vol. 287, pp. 1–21 (2019). https://doi.org/10.4204/EPTCS.287.1
Backens, M.: The ZX-calculus is complete for stabilizer quantum mechanics. In: New Journal of Physics. vol. 16, p. 093021. IOP Publishing (Sep 2014). https://doi.org/10.1088/1367-2630/16/9/093021, https://doi.org/10.1088%2F1367-2630%2F16%2F9%2F093021
Backens, M., Kissinger, A.: ZH: A complete graphical calculus for quantum computations involving classical non-linearity. In: Selinger, P., Chiribella, G. (eds.) Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018. Electronic Proceedings in Theoretical Computer Science, vol. 287, pp. 23–42 (2019). https://doi.org/10.4204/EPTCS.287.2
de Beaudrap, N., Bian, X., Wang, Q.: Fast and effective techniques for t-count reduction via spider nest identities (2020)
Carette, T., Jeandel, E., Perdrix, S., Vilmart, R.: Completeness of Graphical Languages for Mixed States Quantum Mechanics. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 108:1–108:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.108, http://drops.dagstuhl.de/opus/volltexte/2019/10684
Chareton, C., Bardin, S., Bobot, F., Perrelle, V., Valiron, B.: A deductive verification framework for circuit-building quantum programs (2020)
Coecke, B., Duncan, R.: Interacting quantum observables: Categorical algebra and diagrammatics. New Journal of Physics 13(4), 043016 (Apr 2011). https://doi.org/10.1088/1367-2630/13/4/043016, https://doi.org/10.1088%2F1367-2630%2F13%2F4%2F043016
Coecke, B., Kissinger, A.: The compositional structure of multipartite quantum entanglement. In: Automata, Languages and Programming, pp. 297–308. Springer Berlin Heidelberg (2010). https://doi.org/10.1007/978-3-642-14162-1_25, https://doi.org/10.1007%2F978-3-642-14162-1_25
Duncan, R., Perdrix, S.: Pivoting makes the ZX-calculus complete for real stabilizers. In: Coecke, B., Hoban, M. (eds.) Proceedings of the 10th International Workshop on Quantum Physics and Logic, Castelldefels (Barcelona), Spain, 17th to 19th July 2013. Electronic Proceedings in Theoretical Computer Science, vol. 171, pp. 50–62 (2014). https://doi.org/10.4204/EPTCS.171.5
Hadzihasanovic, A.: A diagrammatic axiomatisation for qubit entanglement. In: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science. pp. 573–584 (Jul 2015). https://doi.org/10.1109/LICS.2015.59
Hadzihasanovic, A., Ng, K.F., Wang, Q.: Two complete axiomatisations of pure-state qubit quantum computing. In: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. pp. 502–511. LICS ’18, ACM, New York, NY, USA (2018). https://doi.org/10.1145/3209108.3209128, https://doi.org/10.1145/3209108.3209128
Kissinger, A., van de Wetering, J.: Reducing T-count with the ZX-calculus (2019)
Lack, S.: Composing PROPs. In: Theory and Applications of Categories. vol. 13, pp. 147–163 (2004), http://www.tac.mta.ca/tac/volumes/13/9/13-09abs.html
Lemonnier, L.: Relating high-level frameworks for quantum circuits. Master’s thesis, Radbound University (2019), https://www.cs.ox.ac.uk/people/aleks.kissinger/papers/lemonnier-high-level.pdf
Lemonnier, L., van de Wetering, J., Kissinger, A.: Hypergraph simplification: Linking the path-sum approach to the zh-calculus (2020), arXiv:2003.13564
Mac Lane, S.: Categories for the Working Mathematician, vol. 5. Springer Science & Business Media (2013)
Selinger, P.: Dagger compact closed categories and completely positive maps. Electronic Notes in Theoretical Computer Science 170, 139–163 (Mar 2007). https://doi.org/10.1016/j.entcs.2006.12.018, https://doi.org/10.1016%2Fj.entcs.2006.12.018
Selinger, P.: A survey of graphical languages for monoidal categories. In: New Structures for Physics, pp. 289–355. Springer (2010)
Vilmart, R.: 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). pp. 1–10 (June 2019). https://doi.org/10.1109/LICS.2019.8785765
Zanasi, F.: Interacting Hopf Algebras – the theory of linear systems. Ph.D. thesis, Université de Lyon (2015), http://www.zanasi.com/fabio/#/publications.html
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2021 The Author(s)
About this paper
Cite this paper
Vilmart, R. (2021). The Structure of Sum-Over-Paths, its Consequences, and Completeness for Clifford. In: Kiefer, S., Tasson, C. (eds) Foundations of Software Science and Computation Structures. FOSSACS 2021. Lecture Notes in Computer Science(), vol 12650. Springer, Cham. https://doi.org/10.1007/978-3-030-71995-1_27
Download citation
DOI: https://doi.org/10.1007/978-3-030-71995-1_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71994-4
Online ISBN: 978-3-030-71995-1
eBook Packages: Computer ScienceComputer Science (R0)