{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:45:19Z","timestamp":1780994719966,"version":"3.54.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["RGPIN-2018-05812"],"award-info":[{"award-number":["RGPIN-2018-05812"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["OMA-1936353"],"award-info":[{"award-number":["OMA-1936353"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>\n            Rig groupoids provide a semantic model of\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mo>\u03a0<\/mml:mo>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , a universal classical reversible programming language over finite types. We prove that extending rig groupoids with just two maps and three equations about them results in a model of quantum computing that is computationally universal and equationally sound and complete for a variety of gate sets. The first map corresponds to an 8th root of the identity morphism on the unit 1. The second map corresponds to a square root of the symmetry on\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mn>1<\/mml:mn>\n                  <mml:mo>+<\/mml:mo>\n                  <mml:mn>1<\/mml:mn>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            . As square roots are generally not unique and can sometimes even be trivial, the maps are constrained to satisfy a nondegeneracy axiom, which we relate to the Euler decomposition of the Hadamard gate. The semantic construction is turned into an extension of\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mo>\u03a0<\/mml:mo>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , called\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:msqrt>\n                  <mml:mo>\u03a0<\/mml:mo>\n                <\/mml:msqrt>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , that is a computationally universal quantum programming language equipped with an equational theory that is sound and complete with respect to the Clifford gate set, the standard gate set of Clifford+T restricted to\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mo>\u2264<\/mml:mo>\n                  <mml:mn>2<\/mml:mn>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            qubits, and the computationally universal Gaussian Clifford+T gate set.\n          <\/jats:p>","DOI":"10.1145\/3632861","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"546-574","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["With a Few Square Roots, Quantum Computing Is as Easy as Pi"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8993-9804","authenticated-orcid":false,"given":"Jacques","family":"Carette","sequence":"first","affiliation":[{"name":"McMaster University, Hamilton, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7393-2640","authenticated-orcid":false,"given":"Chris","family":"Heunen","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7672-799X","authenticated-orcid":false,"given":"Robin","family":"Kaarsgaard","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1025-7331","authenticated-orcid":false,"given":"Amr","family":"Sabry","sequence":"additional","affiliation":[{"name":"Indiana University, Bloomington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","unstructured":"D. Aharonov. 2003. A simple proof that Toffoli and Hadamard are quantum universal. (2003). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0301040 10.48550\/arXiv.quant-ph\/0301040.","DOI":"10.48550\/arXiv.quant-ph\/0301040"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-04-06-252"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","unstructured":"F. Arute et. al. 2019. Supplementary information for \u201cQuantum supremacy using a programmable superconducting processor\u201d. (2019). https:\/\/doi.org\/10.48550\/arXiv.1910.11333 10.48550\/arXiv.1910.11333","DOI":"10.48550\/arXiv.1910.11333"},{"key":"e_1_3_1_5_1","unstructured":"S. Awodey. 2010. Category Theory Oxford University Press."},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","unstructured":"M. Backens and A. Kissinger. 2019. ZH: A complete graphical calculus for quantum computations involving classical non-linearity. In Quantum Physics and Logic (Electronic Proceedings in Theoretical Computer Science 287). 23\u201342. https:\/\/doi.org\/10.4204\/EPTCS.287.2 10.4204\/EPTCS.287.2","DOI":"10.4204\/EPTCS.287.2"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","unstructured":"X. Bian and P. Selinger. 2021. Generators and Relations for Un(\u2124[12 i]). In Quantum Physics and Logic (Electronic Proceedings in Theoretical Computer Science Vol. 343). 145\u2013164. https:\/\/doi.org\/10.4204\/EPTCS.343.8 10.4204\/EPTCS.343.8","DOI":"10.4204\/EPTCS.343.8"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","unstructured":"X. Bian and P. Selinger. 2022. Generators and Relations for 2-qubit Clifford+T operators. In Quantum Physics and Logic (Electronic Proceedings in Theoretical Computer Science). https:\/\/doi.org\/10.48550\/arXiv.2204.02217 10.48550\/arXiv.2204.02217","DOI":"10.48550\/arXiv.2204.02217"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","unstructured":"J. Carette C. Heunen R. Kaarsgaard and A. Sabry. 2023. With a Few Square Roots Quantum Computing is as Easy as \u03a0. (2023). https:\/\/doi.org\/10.48550\/arXiv.2310.14056 10.48550\/arXiv.2310.14056 Extended version with full proofs.","DOI":"10.48550\/arXiv.2310.14056"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","unstructured":"J. Carette R. P. James and A. Sabry. 2022. Embracing the laws of physics: Three reversible models of computation. Advances in Computers Vol. 126. Elsevier 15\u201363. https:\/\/doi.org\/10.1016\/bs.adcom.2021.11.009 10.1016\/bs.adcom.2021.11.009","DOI":"10.1016\/bs.adcom.2021.11.009"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49498-1_6"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","unstructured":"V. Choudhury J. Karwowski and A. Sabry. 2022. Symmetries in Reversible Programming: From Symmetric Rig Groupoids to Reversible Programming Languages. Proc. ACM Program. Lang. 6 POPL Article 6 (1 2022) 32 pages. https:\/\/doi.org\/10.1145\/3498667 10.1145\/3498667.","DOI":"10.1145\/3498667"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2206.10577"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/13\/4\/043016"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.119"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03073-4_18"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","unstructured":"B. Giles and P. Selinger. 2013. Exact synthesis of multiqubit Clifford+\ud835\udc47 circuits. Phys. Rev. A 87 (2013). Issue 3. https:\/\/doi.org\/10.1103\/PhysRevA.87.032332 10.1103\/PhysRevA.87.032332","DOI":"10.1103\/PhysRevA.87.032332"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-54997-8_26"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.quant-ph\/9807006"},{"key":"e_1_3_1_20_1","first-page":"304","article-title":"The square root of NOT","volume":"83","author":"Hayes B.","year":"1995","unstructured":"B. Hayes. 1995. The square root of NOT. American Scientist 83 (1995), 304\u2013308. https:\/\/www.jstor.org\/stable\/29775474","journal-title":"American Scientist"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","unstructured":"C. Heunen and R. Kaarsgaard. 2022. Quantum Information Effects. Proceedings of the ACM on Programming Languages 6 POPL (2022) 1\u201327. https:\/\/doi.org\/10.1145\/3498663 10.1145\/3498663","DOI":"10.1145\/3498663"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","unstructured":"C. Heunen R. Kaarsgaard and M. Karvonen. 2018. Reversible effects as inverse arrows. In Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV) (Electronic Notes in Theoretical Computer Science Vol. 341). Elsevier 179\u2013199. https:\/\/doi.org\/10.1016\/j.entcs.2018.11.009 10.1016\/j.entcs.2018.11.009","DOI":"10.1016\/j.entcs.2018.11.009"},{"key":"e_1_3_1_23_1","doi-asserted-by":"crossref","unstructured":"C. Heunen and J. Vicary. 2019. Categories for quantum theory. Oxford University Press.","DOI":"10.1093\/oso\/9780198739623.001.0001"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","unstructured":"J. Hu and J. Carette. 2021. Formalizing Category Theory in Agda. In Proceedings of the 10th ACM SIGPLAN International Conference on Certified Programs and Proofs (Virtual Denmark) (CPP 2021). Association for Computing Machinery New York NY USA 327\u2013342. https:\/\/doi.org\/10.1145\/3437992.3439922 10.1145\/3437992.3439922","DOI":"10.1145\/3437992.3439922"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","unstructured":"R. P. James and A. Sabry. 2012. Information Effects. In POPL \u201912: Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of programming languages. ACM 73\u201384. https:\/\/doi.org\/10.1145\/2103656.2103667 10.1145\/2103656.2103667","DOI":"10.1145\/2103656.2103667"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","unstructured":"N. Johnson and D. Yau. 2021. Bimonoidal Categories En-Monoidal Categories and Algebraic \ud835\udc3e-Theory. (2021). https:\/\/doi.org\/10.48550\/arXiv.2107.10526 10.48550\/arXiv.2107.10526","DOI":"10.48550\/arXiv.2107.10526"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0059555"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0097608"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1972505"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2022.3170008"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","unstructured":"P. Selinger. 2015. Generators and relations for n-qubit Clifford operators. Logical Methods in Computer Science Volume 11 Issue 2 (June 2015). https:\/\/doi.org\/10.2168\/LMCS-11(2:10)2015 10.2168\/LMCS-11(2:10)2015","DOI":"10.2168\/LMCS-11(2:10)2015"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","unstructured":"T. Sleator and H. Weinfurter. 1995. Realizable Universal Quantum Logic Gates. Phys. Rev. Lett. 74 (5 1995) 4087\u20134090. Issue 20. https:\/\/doi.org\/10.1103\/PhysRevLett.74.4087 10.1103\/PhysRevLett.74.4087","DOI":"10.1103\/PhysRevLett.74.4087"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","unstructured":"S. Staton. 2015. Algebraic Effects Linearity and Quantum Programming Languages. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL \u201915). ACM 395\u2013406. https:\/\/doi.org\/10.1145\/2676726.2676999 10.1145\/2676726.2676999.","DOI":"10.1145\/2676726.2676999"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20860-2_13"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10003-2_104"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813887"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09005-9_3"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632861","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:03:15Z","timestamp":1751659395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":36,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632861"],"URL":"https:\/\/doi.org\/10.1145\/3632861","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}