{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T21:45:11Z","timestamp":1755035111757,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T00:00:00Z","timestamp":1640044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SoftQPro","award":["ANR-17-CE25-0009"],"award-info":[{"award-number":["ANR-17-CE25-0009"]}]},{"name":"VanQuTe","award":["ANR-17-CE24-0035"],"award-info":[{"award-number":["ANR-17-CE24-0035"]}]},{"name":"PIA-GDN\/Quantex"},{"name":"LUE\/UOQ"},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["951821"],"award-info":[{"award-number":["951821"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>There exist several graphical languages for quantum information processing, like quantum circuits, ZX-calculus, ZW-calculus, and so on. Each of these languages forms a \u2020-symmetric monoidal category (\u2020-SMC) and comes with an interpretation functor to the \u2020-SMC of finite-dimensional Hilbert spaces. In 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.<\/jats:p>\n          <jats:p>\n            We address the question of how to extend these languages beyond pure quantum mechanics to reason about mixed states and general quantum operations, i.e.,\u00a0completely positive maps. Intuitively, such an extension relies on the axiomatisation of a\n            <jats:italic>discard<\/jats:italic>\n            map that allows one to get rid of a quantum system, an operation that is not allowed in pure quantum mechanics.\n          <\/jats:p>\n          <jats:p>\n            We introduce a new construction, the\n            <jats:italic>discard construction<\/jats:italic>\n            , which transforms any \u2020-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal.\n          <\/jats:p>\n          <jats:p>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 Clifford+T quantum mechanics, as the category does not have enough isometries.<\/jats:p>","DOI":"10.1145\/3464693","type":"journal-article","created":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T16:43:51Z","timestamp":1640105031000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Completeness of Graphical Languages for Mixed\u00a0State Quantum Mechanics"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1618-4081","authenticated-orcid":false,"given":"Titouan","family":"Carette","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7236-2906","authenticated-orcid":false,"given":"Emmanuel","family":"Jeandel","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1808-2409","authenticated-orcid":false,"given":"Simon","family":"Perdrix","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8828-4671","authenticated-orcid":false,"given":"Renaud","family":"Vilmart","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CNRS, LRI, 91405, Orsay, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,21]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"84","volume-title":"Proceedings of the 14th International Conference on Quantum Physics and Logic","volume":"266","author":"Amy Matthew","year":"2018","unstructured":"Matthew Amy, Jianxin Chen, and Neil J. Ross. 2018. A finite presentation of CNOT-dihedral operators. In Proceedings of the 14th International Conference on Quantum Physics and Logic, Bob Coecke and Aleks Kissinger (Eds.), Electronic Proceedings in Theoretical Computer Science, Vol. 266. 84\u201397. DOI:https:\/\/doi.org\/10.4204\/EPTCS.266.5"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/7\/1\/170"},{"key":"e_1_3_3_4_2","first-page":"093021","volume-title":"New Journal of Physics","author":"Backens Miriam","year":"2014","unstructured":"Miriam Backens. 2014. The ZX-calculus is complete for stabilizer quantum mechanics. In New Journal of Physics, Vol. 16. IOP Publishing, 093021. DOI:https:\/\/doi.org\/10.1088\/1367-2630\/16\/9\/093021"},{"key":"e_1_3_3_5_2","series-title":"Proceedings of the 11th Workshop on Quantum Physics and Logic","first-page":"293","volume":"172","author":"Backens Miriam","year":"2014","unstructured":"Miriam Backens. 2014. The ZX-calculus is complete for the single-qubit Clifford+T group. In Proceedings of the 11th Workshop on Quantum Physics and Logic, Bob Coecke, Ichiro Hasuo, and Prakash Panangaden (Eds.), Electronic Proceedings in Theoretical Computer Science,Vol. 172. 293\u2013303. DOI:https:\/\/doi.org\/10.4204\/EPTCS.172.21"},{"key":"e_1_3_3_6_2","first-page":"1","article-title":"A complete graphical calculus for spekkens\u2019 toy bit theory","author":"Backens Miriam","year":"2014","unstructured":"Miriam Backens and Ali Nabi Duman. 2014. A complete graphical calculus for spekkens\u2019 toy bit theory. Found. Phys. 46, 70 (2016), 1\u201334. DOI:https:\/\/doi.org\/10.1007\/s10701-015-9957-7arXiv:arXiv:1411.1618","journal-title":"Found. Phys. 46, 70 (2016)"},{"key":"e_1_3_3_7_2","series-title":"Proceedings of the 15th International Conference on Quantum Physics and Logic","first-page":"23","volume":"287","author":"Backens Miriam","year":"2019","unstructured":"Miriam Backens and Aleks Kissinger. 2019. ZH: A complete graphical calculus for quantum computations involving classical non-linearity. In Proceedings of the 15th International Conference on Quantum Physics and Logic, Peter Selinger and Giulio Chiribella (Eds.), Electronic Proceedings in Theoretical Computer Science,Vol. 287. 23\u201342. DOI:https:\/\/doi.org\/10.4204\/EPTCS.287.2"},{"key":"e_1_3_3_8_2","first-page":"727","volume-title":"Theory and Applications of Categories","author":"Baez John C.","year":"2017","unstructured":"John C. Baez, Brandon Coya, and Franciscus Rebro. 2017. Props in network theory. In Theory and Applications of Categories, Vol. 33. 727\u2013783. http:\/\/arxiv.org\/abs\/1707.08321."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-0021-0"},{"key":"e_1_3_3_10_2","unstructured":"Nicholas Chancellor Aleks Kissinger Joschka Roffe Stefan Zohren and Dominic Horsman. 2016. Graphical Structures for Design and Verification of Quantum Error Correction. arXiv:1611.08012. Retrieved from https:\/\/arxiv.org\/abs\/1611.08012."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.04.014"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/13\/4\/043016"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.02.007"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/978-3-642-14162-1_25","volume-title":"Automata, Languages and Programming","author":"Coecke Bob","year":"2010","unstructured":"Bob Coecke and Aleks Kissinger. 2010. The compositional structure of multipartite quantum entanglement. In Automata, Languages and Programming. Springer, Berlin, 297\u2013308. DOI:https:\/\/doi.org\/10.1007\/978-3-642-14162-1_25"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781316219317"},{"key":"e_1_3_3_16_2","article-title":"Environment and classical channels in categorical quantum mechanics","volume":"8","author":"Coecke Bob","year":"2012","unstructured":"Bob Coecke and Simon Perdrix. 2012. Environment and classical channels in categorical quantum mechanics. Logic. Methods Comput. Sci. 8, 4 (Nov. 2012). DOI:https:\/\/doi.org\/10.2168\/LMCS-8(4:14)2012","journal-title":"Logic. Methods Comput. Sci."},{"key":"e_1_3_3_17_2","doi-asserted-by":"crossref","unstructured":"Bob Coecke and Quanlong Wang. 2018. ZX-rules for 2-qubit Clifford+T quantum circuits. arXiv:1804.05356. Retrieved from https:\/\/arxiv.org\/abs\/1804.05356.","DOI":"10.1007\/978-3-319-99498-7_10"},{"key":"e_1_3_3_18_2","article-title":"The ZX& calculus: A complete graphical calculus for classical circuits using spiders","author":"Comfort Cole","year":"2020","unstructured":"Cole Comfort. 2020. The ZX& calculus: A complete graphical calculus for classical circuits using spiders. arXiv:2004.05287. Retrieved from https:\/\/arxiv.org\/abs\/2004.05287.","journal-title":"arXiv:2004.05287"},{"key":"e_1_3_3_19_2","article-title":"Purity through factorisation","author":"Cunningham Oscar","year":"2017","unstructured":"Oscar Cunningham and Chris Heunen. 2017. Purity through factorisation. arXiv:1705.07652. Retrieved from https:\/\/arxiv.org\/abs\/1705.07652.","journal-title":"arXiv:1705.07652"},{"key":"e_1_3_3_20_2","unstructured":"Niel de Beaudrap and Dominic Horsman. 2017. The ZX-calculus is a language for surface code lattice surgery. arXiv:1704.08670. Retrieved from http:\/\/arxiv.org\/abs\/1704.08670."},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1093\/acprof:oso\/9780199646296.003.0003","volume-title":"Quantum Physics and Linguistics","author":"Duncan Ross","year":"2013","unstructured":"Ross Duncan. 2013. A graphical approach to measurement-based quantum computing. In Quantum Physics and Linguistics. Oxford University Press, 50\u201389. DOI:https:\/\/doi.org\/10.1093\/acprof:oso\/9780199646296.003.0003"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934550"},{"key":"e_1_3_3_23_2","series-title":"Proceedings of the 14th International Conference on Quantum Physics and Logic","first-page":"147","volume":"266","author":"Duncan Ross","year":"2018","unstructured":"Ross Duncan and Liam Garvie. 2018. Verifying the smallest interesting colour code with quantomatic. In Proceedings of the 14th International Conference on Quantum Physics and Logic, Bob Coecke and Aleks Kissinger (Eds.), Electronic Proceedings in Theoretical Computer Science,Vol. 266. 147\u2013163. DOI:https:\/\/doi.org\/10.4204\/EPTCS.266.10"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","unstructured":"Ross Duncan Aleks Kissinger Simon Perdrix and John van de Wetering. 2019. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. arXiv:1902.03178. Retrieved from https:\/\/arxiv.org\/abs\/1902.03178.","DOI":"10.22331\/q-2020-06-04-279"},{"key":"e_1_3_3_25_2","series-title":"Proceedings of the 10th International Workshop on Quantum Physics and Logic","first-page":"33","volume":"171","author":"Duncan Ross","year":"2014","unstructured":"Ross Duncan and Maxime Lucas. 2014. Verifying the Steane code with Quantomatic. In Proceedings of the 10th International Workshop on Quantum Physics and Logic, Bob Coecke and Matty Hoban (Eds.), Electronic Proceedings in Theoretical Computer Science,Vol. 171. Open Publishing Association, 33\u201349. DOI:https:\/\/doi.org\/10.4204\/EPTCS.171.4"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14162-1_24"},{"key":"e_1_3_3_27_2","series-title":"Proceedings of the 10th International Workshop on Quantum Physics and Logic","first-page":"50","volume":"171","author":"Duncan Ross","year":"2014","unstructured":"Ross Duncan and Simon Perdrix. 2014. Pivoting makes the ZX-calculus complete for real stabilizers. In Proceedings of the 10th International Workshop on Quantum Physics and Logic), Bob Coecke and Matty Hoban (Eds.), Electronic Proceedings in Theoretical Computer Science,Vol. 171. 50\u201362. DOI:https:\/\/doi.org\/10.4204\/EPTCS.171.5"},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"032332","DOI":"10.1103\/PhysRevA.87.032332","article-title":"Exact synthesis of multiqubit Clifford+T circuits","volume":"87","author":"Giles Brett","year":"2013","unstructured":"Brett Giles and Peter Selinger. 2013. Exact synthesis of multiqubit Clifford+T circuits. Phys. Rev. A 87, 3 (Mar. 2013), 032332. DOI:https:\/\/doi.org\/10.1103\/PhysRevA.87.032332","journal-title":"Phys. Rev. A"},{"key":"e_1_3_3_29_2","article-title":"A bestiary of sets and relations","author":"Gogioso Stefano","year":"2015","unstructured":"Stefano Gogioso. 2015. A bestiary of sets and relations. arXiv:1506.05025. Retrieved from https:\/\/arxiv.org\/abs\/1506.05025.","journal-title":"arXiv:1506.05025"},{"key":"e_1_3_3_30_2","first-page":"573","volume-title":"Proceedings of the 30th Annual ACM\/IEEE Symposium on Logic in Computer Science","author":"Hadzihasanovic Amar","year":"2015","unstructured":"Amar Hadzihasanovic. 2015. A diagrammatic axiomatisation for qubit entanglement. In Proceedings of the 30th Annual ACM\/IEEE Symposium on Logic in Computer Science. 573\u2013584. DOI:https:\/\/doi.org\/10.1109\/LICS.2015.59"},{"key":"e_1_3_3_31_2","volume-title":"The Algebra of Entanglement and the Geometry of Composition","author":"Hadzihasanovic Amar","year":"2017","unstructured":"Amar Hadzihasanovic. 2017. The Algebra of Entanglement and the Geometry of Composition. Ph.D. Dissertation. University of Oxford."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209128"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/13\/9\/095011"},{"key":"e_1_3_3_34_2","series-title":"Proceedings of the 15th International Conference on Quantum Physics and Logic","first-page":"213","volume":"287","author":"Huot Mathieu","year":"2019","unstructured":"Mathieu Huot and Sam Staton. 2019. Universal properties in quantum theory. In Proceedings of the 15th International Conference on Quantum Physics and Logic, Peter Selinger and Giulio Chiribella (Eds.), Electronic Proceedings in Theoretical Computer Science,Vol. 287. 213\u2013223. DOI:https:\/\/doi.org\/10.4204\/EPTCS.287.12"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209131"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209139"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/3470152.3470196"},{"key":"e_1_3_3_38_2","unstructured":"Martti Karvonen. 2019. The way of the dagger. arXiv preprint arXiv:1904.10805 ."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330030"},{"key":"e_1_3_3_40_2","unstructured":"Aleks Kissinger and John van de Wetering. 2018. PyZX. Retrieved from https:\/\/github.com\/Quantomatic\/pyzx."},{"key":"e_1_3_3_41_2","first-page":"326","volume-title":"Proceedings of the International Conference on Automated Deduction (CADE-25)","author":"Kissinger Aleks","year":"2015","unstructured":"Aleks Kissinger and Vladimir Zamdzhiev. 2015. Quantomatic: A proof assistant for diagrammatic reasoning. In Proceedings of the International Conference on Automated Deduction (CADE-25), Amy P. Felty and Aart Middeldorp (Eds.). Springer International Publishing, Cham, 326\u2013336. DOI:https:\/\/doi.org\/10.1007\/978-3-319-21401-6_22"},{"key":"e_1_3_3_42_2","article-title":"A graph theoretic perspective on CPM (Rel)","author":"Marsden Daniel","year":"2015","unstructured":"Daniel Marsden. 2015. A graph theoretic perspective on CPM (Rel). arXiv:1504.07003. Retrieved from https:\/\/arxiv.org\/abs\/1504.07003.","journal-title":"arXiv:1504.07003"},{"key":"e_1_3_3_43_2","unstructured":"Ken Matsumoto and Kazuyuki Amano. 2008. Representation of quantum circuits with Clifford and  gates. arXiv:quant-ph\/0806.3834. Retrieved from https:\/\/arxiv.org\/abs\/0806.3834."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129504004256"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.12.018"},{"key":"e_1_3_3_47_2","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/978-3-642-12821-9_4","volume-title":"New Structures for Physics","author":"Selinger Peter","year":"2010","unstructured":"Peter Selinger. 2010. A survey of graphical languages for monoidal categories. In New Structures for Physics. Springer, 289\u2013355."},{"key":"e_1_3_3_48_2","article-title":"Generators and relations for n-qubit clifford operators","volume":"11","author":"Selinger Peter","year":"2015","unstructured":"Peter Selinger. 2015. Generators and relations for n-qubit clifford operators. Logic. Methods Comput. Sci. 11, 2 (Jun. 2015). DOI:https:\/\/doi.org\/10.2168\/LMCS-11(2:10)2015","journal-title":"Logic. Methods Comput. Sci."},{"key":"e_1_3_3_49_2","unstructured":"Peter Selinger and Xiaoning Bian. 2015. Relations for Clifford+T Operators on Two Qubits. Retrieved from https:\/\/www.mathstat.dal.ca\/xbian\/talks\/."},{"key":"e_1_3_3_50_2","article-title":"A near-optimal axiomatisation of zx-calculus for pure qubit quantum mechanics","author":"Vilmart Renaud","year":"2018","unstructured":"Renaud Vilmart. 2018. A near-optimal axiomatisation of zx-calculus for pure qubit quantum mechanics. arXiv:1812.09114. Retrieved from https:\/\/arxiv.org\/abs\/1812.09114.","journal-title":"arXiv:1812.09114"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/3470152.3470198"},{"key":"e_1_3_3_52_2","volume-title":"Interacting Hopf Algebras\u2014The Theory of Linear Systems","author":"Zanasi Fabio","year":"2015","unstructured":"Fabio Zanasi. 2015. Interacting Hopf Algebras\u2014The Theory of Linear Systems. Ph.D. Dissertation. Universit\u00e9 de Lyon."}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464693","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3464693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:11Z","timestamp":1750191431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,21]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3464693"],"URL":"https:\/\/doi.org\/10.1145\/3464693","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"type":"print","value":"2643-6809"},{"type":"electronic","value":"2643-6817"}],"subject":[],"published":{"date-parts":[[2021,12,21]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}