Document Open Access Logo

Geometry of Interaction for ZX-Diagrams

Authors Kostia Chardonnet, Benoît Valiron , Renaud Vilmart

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.30.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Kostia Chardonnet
  • Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, 91190, Gif-sur-Yvette, France
  • Université de Paris, CNRS, IRIF, F-75006, Paris, France
Benoît Valiron
  • Université Paris-Saclay, CNRS, CentraleSupélec, ENS Paris-Saclay, LMF, 91190, Gif-sur-Yvette, France
Renaud Vilmart
  • Université Paris-Saclay, CNRS, ENS Paris-Saclay, Inria, LMF, 91190, Gif-sur-Yvette, France

Funding

This work was supported in part by the French National Research Agency (ANR) under the research project SoftQPRO ANR-17-CE25-0009-02, and by the DGE of the French Ministry of Industry under the research project PIA-GDN/QuantEx P163746-484124.

Cite As Get BibTex

Kostia Chardonnet, Benoît Valiron, and Renaud Vilmart. Geometry of Interaction for ZX-Diagrams. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.30

Abstract

ZX-Calculus is a versatile graphical language for quantum computation equipped with an equational theory. Getting inspiration from Geometry of Interaction, in this paper we propose a token-machine-based asynchronous model of both pure ZX-Calculus and its extension to mixed processes. We also show how to connect this new semantics to the usual standard interpretation of ZX-diagrams. This model allows us to have a new look at what ZX-diagrams compute, and give a more local, operational view of the semantics of ZX-diagrams.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Linear logic
  • Theory of computation → Equational logic and rewriting
Keywords
  • Quantum Computation
  • Linear Logic
  • ZX-Calculus
  • Geometry of Interaction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Matthew Amy. Towards Large-scale Functional Verification of Universal Quantum Circuits. In Peter Selinger and Giulio Chiribella, editors, Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, Halifax, Canada, 3-7th June 2018, volume 287 of EPTCS, pages 1-21, 2018. URL: https://doi.org/10.4204/EPTCS.287.1.
  2. Andrea Asperti and Cosimo Laneve. Paths, computations and labels in the λ-calculus. Theoretical Computer Science, 142(2):277-297, 1995. Google Scholar
  3. Miriam Backens. The ZX-Calculus is Complete for Stabilizer Quantum Mechanics. New Journal of Physics, 16(9):093021, 2014. URL: https://doi.org/10.1088/1367-2630/16/9/093021.
  4. Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering. There and back again: A circuit extraction tale, 2020. URL: http://arxiv.org/abs/2003.01664.
  5. Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 108:1-108:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.108.
  6. Christophe Chareton, Sébastien Bardin, François Bobot, Valentin Perrelle, and Benoît Valiron. A Deductive Verification Framework for Circuit-building Quantum Programs. https://arxiv.org/abs/2003.05841. To appear in Proceedings of ESOP'21.
  7. Bob Coecke and Ross Duncan. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13(4):043016, 2011. Google Scholar
  8. Bob Coecke and Simon Perdrix. Environment and Classical Channels in Categorical Quantum Mechanics. Logical Methods in Computer Science, Volume 8, Issue 4, November 2012. URL: https://doi.org/10.2168/LMCS-8(4:14)2012.
  9. Dal Lago, Ugo and Faggian, Claudia and Valiron, Benoît and Yoshimizu, Akira. The geometry of parallelism: Classical, probabilistic, and quantum effects. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, page 833–845, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3009837.3009859.
  10. Vincent Danos and Laurent Regnier. Reversible, irreversible and optimal λ-machines. Theoretical Computer Science, 227(1-2):79-97, 1999. Google Scholar
  11. Niel de Beaudrap, Ross Duncan, Dominic Horsman, and Simon Perdrix. Pauli Fusion: a computational model to realise quantum transformations from ZX terms. In QPL'19 : International Conference on Quantum Physics and Logic, Los Angeles, United States, 2019. 12 pages + appendices. URL: https://hal.archives-ouvertes.fr/hal-02413388.
  12. Niel de Beaudrap and Dominic Horsman. The ZX calculus is a language for surface code lattice surgery. Quantum, 4:218, 2020. URL: https://doi.org/10.22331/q-2020-01-09-218.
  13. Ross Duncan and Liam Garvie. Verifying the smallest interesting colour code with quantomatic. In Bob Coecke and Aleks Kissinger, editors, rm Proceedings 14th International Conference on Quantum Physics and Logic, rm Nijmegen, The Netherlands, 3-7 July 2017, volume 266 of Electronic Proceedings in Theoretical Computer Science, pages 147-163, 2018. URL: https://doi.org/10.4204/EPTCS.266.10.
  14. Ross Duncan, Aleks Kissinger, Simon Perdrix, and John Van De Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum, 4:279, 2020. Google Scholar
  15. Ross Duncan and Maxime Lucas. Verifying the Steane code with Quantomatic. In Bob Coecke and Matty Hoban, editors, rm Proceedings of the 10th International Workshop on Quantum Physics and Logic, rm Castelldefels (Barcelona), Spain, 17th to 19th July 2013, volume 171 of Electronic Proceedings in Theoretical Computer Science, pages 33-49. Open Publishing Association, 2014. URL: https://doi.org/10.4204/EPTCS.171.4.
  16. Ross Duncan and Simon Perdrix. Rewriting Measurement-Based Quantum Computations with Generalised Flow. Lecture Notes in Computer Science, 6199:285-296, 2010. URL: https://doi.org/10.1007/978-3-642-14162-1_24.
  17. Elizabeth Gibney. Quantum gold rush: the private funding pouring into quantum start-ups. Nature, 574:22-24, 2019. URL: https://doi.org/10.1038/d41586-019-02935-4.
  18. Jean-Yves Girard. Linear logic. Theoretical computer science, 50(1):1-101, 1987. Google Scholar
  19. Jean-Yves Girard. Geometry of interaction II: deadlock-free algorithms. In International Conference on Computer Logic, pages 76-93. Springer, 1988. Google Scholar
  20. Jean-Yves Girard. Geometry of interaction I: interpretation of System F. In Studies in Logic and the Foundations of Mathematics, volume 127, pages 221-260. Elsevier, 1989. Google Scholar
  21. Jean-Yves Girard. Towards a geometry of interaction. Contemporary Mathematics, 92(69-108):6, 1989. Google Scholar
  22. Jean-Yves Girard. Geometry of interaction III: accommodating the additives. London Mathematical Society Lecture Note Series, pages 329-389, 1995. Google Scholar
  23. Jean-Yves Girard. Proof-nets: the parallel syntax for proof-theory. Lecture Notes in Pure and Applied Mathematics, pages 97-124, 1996. Google Scholar
  24. 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. URL: https://doi.org/10.1145/3209108.3209128.
  25. Anne Hillebrand. Quantum Protocols involving Multiparticle Entanglement and their Representations. Master’s thesis, University of Oxford, 2011. URL: https://www.cs.ox.ac.uk/people/bob.coecke/Anne.pdf.
  26. 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, 2018. ACM. URL: https://doi.org/10.1145/3209108.3209131.
  27. 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, 2018. ACM. URL: https://doi.org/10.1145/3209108.3209139.
  28. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-10, June 2019. URL: https://doi.org/10.1109/LICS.2019.8785754.
  29. Alexandre Ménard, Ivan Ostojic, Mark Patel, and Daniel Volz. A game plan for quantum computing. McKinsey Quaterly, 2020. Google Scholar
  30. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2002. Google Scholar
  31. Qureca.com. Overview on quantum initiatives worldwide. https://www.qureca.com/overview-on-quantum-initiatives-worldwide/, January 2021.
  32. Peter Selinger. Dagger compact closed categories and completely positive maps. Electronic Notes in Theoretical computer science, 170:139-163, 2007. Google Scholar
  33. 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, June 2019. URL: https://doi.org/10.1109/LICS.2019.8785765.
  34. Renaud Vilmart. ZX-Calculi for Quantum Computing and their Completeness. Theses, Université de Lorraine, 2019. URL: https://hal.archives-ouvertes.fr/tel-02395443.
  35. Renaud Vilmart. The Structure of Sum-Over-Paths, its Consequences, and Completeness for Clifford, 2020. URL: http://arxiv.org/abs/2003.05678.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact