Document Open Access Logo

Completeness of Graphical Languages for Mixed States Quantum Mechanics (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Titouan Carette, Emmanuel Jeandel , Simon Perdrix , Renaud Vilmart

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.108.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Titouan Carette
  • Université de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France
Emmanuel Jeandel
  • Université de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France
Simon Perdrix
  • Université de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France
Renaud Vilmart
  • Université de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France

Funding

This work is funded by ANR-17-CE25-0009 SoftQPro and PIA-GDN/Quantex.

Cite AsGet BibTex

Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 108:1-108:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.108

Abstract

There exist several graphical languages for quantum information processing, like quantum circuits, ZX-Calculus, ZW-Calculus, etc. Each of these languages forms a dagger-symmetric monoidal category (dagger-SMC) and comes with an interpretation functor to the dagger-SMC of (finite dimension) Hilbert spaces. In the recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of the extension of these languages beyond pure quantum mechanics, in order to reason on mixed states and general quantum operations, i.e. completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map which allows one to get rid of a quantum system, operation which is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction, which transforms any dagger-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However this construction fails for some fringe cases like the Clifford+T quantum mechanics, as the category does not have enough isometries.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Theory of computation → Quantum computation theory
  • Theory of computation → Logic
Keywords
  • Quantum Computing
  • Quantum Categorical Mechanics
  • Category Theory
  • Mixed States
  • Completely Positive Maps

Metrics

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

Related Versions

References

  1. Matthew Amy, Jianxin Chen, and Neil J. Ross. A Finite Presentation of CNOT-Dihedral Operators. 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 84-97. Open Publishing Association, 2018. URL: http://dx.doi.org/10.4204/EPTCS.266.5.
  2. Koenraad M. R. Audenaert and Martin B. Plenio. Entanglement on Mixed Stabilizer States: Normal Forms and Reduction Procedures. New Journal of Physics, 7:170-170, August 2005. URL: http://dx.doi.org/10.1088/1367-2630/7/1/170.
  3. Miriam Backens. The ZX-Calculus is Complete for Stabilizer Quantum Mechanics. New Journal of Physics, 16(9):093021, September 2014. URL: http://dx.doi.org/10.1088/1367-2630/16/9/093021.
  4. Miriam Backens. The ZX-Calculus is Complete for the Single-Qubit Clifford+T group. Electronic Proceedings in Theoretical Computer Science, 172:293-303, December 2014. URL: http://dx.doi.org/10.4204/eptcs.172.21.
  5. Miriam Backens and Ali Nabi Duman. A Complete Graphical Calculus for Spekkens' Toy Bit Theory. Foundations of Physics, pages 1-34, 2014. URL: http://dx.doi.org/10.1007/s10701-015-9957-7.
  6. Miriam Backens and Aleks Kissinger. ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity. In Peter Selinger and Giulio Chiribella, editors, rm Proceedings of the 15th International Conference on Quantum Physics and Logic, rm Halifax, Canada, 3-7th June 2018, volume 287 of Electronic Proceedings in Theoretical Computer Science, pages 23-42. Open Publishing Association, 2019. URL: http://dx.doi.org/10.4204/EPTCS.287.2.
  7. John C. Baez, Brandon Coya, and Franciscus Rebro. Props in Network Theory. In Theory and Applications of Categories, volume 33 (25), pages 727-783, July 2017. URL: http://arxiv.org/abs/1707.08321.
  8. Michael Barr and Charles Wells. Toposes, Triples and Theories. Springer-Verlag, New York, 1985. URL: http://www.tac.mta.ca/tac/reprints/articles/12/tr12abs.html.
  9. Nicholas Chancellor, Aleks Kissinger, Joschka Roffe, Stefan Zohren, and Dominic Horsman. Graphical Structures for Design and Verification of Quantum Error Correction. last revised Jan. 2018, 2016. URL: http://arxiv.org/abs/1611.08012.
  10. Bob Coecke. Axiomatic Description of Mixed States from Selinger’s CPM-Construction. Electronic Notes in Theoretical Computer Science, 210:3-13, 2008. Proceedings of the 4th International Workshop on Quantum Programming Languages (QPL 2006). URL: http://dx.doi.org/10.1016/j.entcs.2008.04.014.
  11. Bob Coecke and Ross Duncan. Interacting Quantum Observables: Categorical Algebra and Diagrammatics. New Journal of Physics, 13(4):043016, April 2011. URL: http://dx.doi.org/10.1088/1367-2630/13/4/043016.
  12. Bob Coecke and Chris Heunen. Pictures of Complete Positivity in Arbitrary Dimension. Information and Computation, 250:50-58, 2016. Google Scholar
  13. Bob Coecke and Aleks Kissinger. The Compositional Structure of Multipartite Quantum Entanglement. In Automata, Languages and Programming, pages 297-308. Springer Berlin Heidelberg, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14162-1_25.
  14. Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. URL: http://dx.doi.org/10.1017/9781316219317.
  15. 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: http://dx.doi.org/10.2168/LMCS-8(4:14)2012.
  16. Bob Coecke and Quanlong Wang. ZX-rules for 2-qubit Clifford+T quantum circuits, 2018. Google Scholar
  17. Niel de Beaudrap and Dominic Horsman. The ZX-Calculus is a Language for Surface Code Lattice Surgery. CoRR, abs/1704.08670, 2017. URL: http://arxiv.org/abs/1704.08670.
  18. Ross Duncan. A Graphical Approach to Measurement-Based Quantum Computing. In Quantum Physics and Linguistics, pages 50-89. Oxford University Press, February 2013. URL: http://dx.doi.org/10.1093/acprof:oso/9780199646296.003.0003.
  19. Ross Duncan and Kevin Dunne. Interacting Frobenius Algebras Are Hopf. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016, pages 535-544, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2933575.2934550.
  20. 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. Open Publishing Association, 2018. URL: http://dx.doi.org/10.4204/EPTCS.266.10.
  21. Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus, 2019. Google Scholar
  22. Ross Duncan and Maxime Lucas. Verifying the Steane code with Quantomatic. Electronic Proceedings in Theoretical Computer Science, 171:33-49, December 2014. URL: http://dx.doi.org/10.4204/eptcs.171.4.
  23. Ross Duncan and Simon Perdrix. Rewriting Measurement-Based Quantum Computations with Generalised Flow. Lecture Notes in Computer Science, 6199:285-296, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14162-1_24.
  24. Ross Duncan and Simon Perdrix. Pivoting Makes the ZX-Calculus Complete for Real Stabilizers. In QPL 2013, Electronic Proceedings in Theoretical Computer Science, pages 50-62, 2013. URL: http://dx.doi.org/10.4204/EPTCS.171.5.
  25. Brett Giles and Peter Selinger. Exact Synthesis of Multiqubit Clifford+T Circuits. Phys. Rev. A, 87:032332, March 2013. URL: http://dx.doi.org/10.1103/PhysRevA.87.032332.
  26. Amar Hadzihasanovic. A Diagrammatic Axiomatisation for Qubit Entanglement. In 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 573-584, July 2015. URL: http://dx.doi.org/10.1109/LICS.2015.59.
  27. Amar Hadzihasanovic. The Algebra of Entanglement and the Geometry of Composition. PhD thesis, University of Oxford, 2017. URL: http://arxiv.org/abs/1709.08086.
  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. URL: http://dx.doi.org/10.1145/3209108.3209128.
  29. Clare Horsman. Quantum Picturalism for Topological Cluster-State Computing. New Journal of Physics, 13(9):095011, September 2011. URL: http://dx.doi.org/10.1088/1367-2630/13/9/095011.
  30. Mathieu Huot and Sam Staton. Universal Properties in Quantum Theory. In Peter Selinger and Giulio Chiribella, editors, Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018, volume 287 of Electronic Proceedings in Theoretical Computer Science, pages 213-223. Open Publishing Association, 2019. URL: http://dx.doi.org/10.4204/EPTCS.287.12.
  31. 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: http://dx.doi.org/10.1145/3209108.3209131.
  32. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness, 2018. Google Scholar
  33. 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: http://dx.doi.org/10.1145/3209108.3209139.
  34. A. Kissinger and John van de Wetering. PyZX, 2018. URL: https://github.com/Quantomatic/pyzx.
  35. Aleks Kissinger and Sander Uijlen. A categorical semantics for causal structure. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12. IEEE, 2017. Google Scholar
  36. Aleks Kissinger and Vladimir Zamdzhiev. Quantomatic: A Proof Assistant for Diagrammatic Reasoning. In Amy P. Felty and Aart Middeldorp, editors, Automated Deduction - CADE-25, pages 326-336, Cham, 2015. Springer International Publishing. URL: http://dx.doi.org/10.1007/978-3-319-21401-6_22.
  37. Ken Matsumoto and Kazuyuki Amano. Representation of Quantum Circuits with Clifford and π/8 Gates, June 2008. Google Scholar
  38. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: http://dx.doi.org/10.1017/CBO9780511976667.
  39. Peter Selinger. Towards a Quantum Programming Language. Mathematical. Structures in Comp. Sci., 14(4):527-586, August 2004. URL: http://dx.doi.org/10.1017/S0960129504004256.
  40. Peter Selinger. Dagger Compact Closed Categories and Completely Positive Maps. Electronic Notes in Theoretical Computer Science, 170:139-163, March 2007. URL: http://dx.doi.org/10.1016/j.entcs.2006.12.018.
  41. Peter Selinger. A Survey of Graphical Languages for Monoidal Categories. In New structures for physics, pages 289-355. Springer, 2010. Google Scholar
  42. Peter Selinger. Generators and Relations for n-qubit Clifford Operators. Logical Methods in Computer Science, Volume 11, Issue 2, June 2015. URL: http://dx.doi.org/10.2168/LMCS-11(2:10)2015.
  43. Peter Selinger and Xiaoning Bian. Relations for Clifford+T Operators on Two Qubits, 2015. URL: https://www.mathstat.dal.ca/~xbian/talks/.
  44. Renaud Vilmart. A Near-Optimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics, 2018. Google Scholar
  45. Fabio Zanasi. Interacting Hopf Algebras - the theory of linear systems. PhD thesis, Université de Lyon, 2015. URL: http://www.zanasi.com/fabio/#/publications.html.
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 Imprint Privacy Contact