Cited By
View all- Heunen CKornell Avan der Schaaf N(2024)Axioms for the category of Hilbert spaces and linear contractionsBulletin of the London Mathematical Society10.1112/blms.1301056:4(1532-1549)Online publication date: 24-Feb-2024
With a Few Square Roots, Quantum Computing Is as Easy as Pi
Article No.: 19, Pages 546 - 574
Abstract
Rig groupoids provide a semantic model of Π, 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 1+1. 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 Π, called √Π, 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 ≤2 qubits, and the computationally universal Gaussian Clifford+T gate set.
References
[1]
D. Aharonov. 2003. A simple proof that Toffoli and Hadamard are quantum universal. https://doi.org/10.48550/arXiv.quant-ph/0301040
[2]
M. Amy, A. N. Glaudell, and N. J. Ross. 2020. Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits. Quantum, 4 (2020), April, 252. issn:2521-327X https://doi.org/10.22331/q-2020-04-06-252
[3]
F. Arute et. al. 2019. Supplementary information for "Quantum supremacy using a programmable superconducting processor". https://doi.org/10.48550/arXiv.1910.11333
[4]
S. Awodey. 2010. Category Theory. Oxford University Press. isbn:9780199237180
[5]
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–42. https://doi.org/10.4204/EPTCS.287.2
[6]
X. Bian and P. Selinger. 2021. Generators and Relations for 𝑈𝑛(Z[1/2,𝑖]). In Quantum Physics and Logic (Electronic Proceedings in Theoretical Computer Science, Vol. 343). 145–164. https://doi.org/10.4204/EPTCS.343.8
[7]
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
[8]
J. Carette, C. Heunen, R. Kaarsgaard, and A. Sabry. 2023. With a Few Square Roots, Quantum Computing is as Easy as Π. https://doi.org/10.48550/arXiv.2310.14056 Extended version with full proofs
[9]
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–63. issn:0065-2458 https://doi.org/10.1016/bs.adcom.2021.11.009
[10]
J. Carette and A. Sabry. 2016. Computing with Semirings and Weak Rig Groupoids. In Programming Languages and Systems, P. Thiemann (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 123–148. isbn:978-3-662-49498-1 https://doi.org/10.1007/978-3-662-49498-1_6
[11]
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 (2022), Article 6, 1, 32 pages. https://doi.org/10.1145/3498667
[12]
A. Clément, N. Heurtel, S. Mansfield, S. Perdrix, and B. Valiron. 2023. A complete equational theory for quantum circuits. In Logic in Computer Science. https://doi.org/10.48550/arXiv.2206.10577
[13]
B. Coecke and R. Duncan. 2011. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13 (2011), 043016. https://doi.org/10.1088/1367-2630/13/4/043016
[14]
N. de Beaudrap, A. Kissinger, and J. van de Wetering. 2022. Circuit extraction for ZX-diagrams can be #P-hard. In ICALP. 119:1–119:19. https://doi.org/10.4230/LIPIcs.ICALP.2022.119
[15]
R. Duncan and S. Perdrix. 2009. Graph states and the necessity of Euler decomposition. In Computability in Europe (Lecture Notes in Computer Science, Vol. 5635). Springer, 167–177. https://doi.org/10.1007/978-3-642-03073-4_18
[16]
B. Giles and P. Selinger. 2013. Exact synthesis of multiqubit Clifford+T circuits. Phys. Rev. A, 87 (2013), https://doi.org/10.1103/PhysRevA.87.032332
[17]
R. Glück, R. Kaarsgaard, and T. Yokoyama. 2019. Reversible programs have reversible semantics. In Formal Methods. FM 2019 International Workshops (Lecture Notes in Computer Science, Vol. 12232). 413–427. https://doi.org/10.1007/978-3-030-54997-8_26
[18]
D. Gottesman. 1999. The Heisenberg representation of quantum computers. In Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics. 32–43. https://doi.org/10.48550/arXiv.quant-ph/9807006
[19]
B. Hayes. 1995. The square root of NOT. American Scientist, 83 (1995), 304–308. https://www.jstor.org/stable/29775474
[20]
C. Heunen and R. Kaarsgaard. 2022. Quantum Information Effects. Proceedings of the ACM on Programming Languages, 6, POPL (2022), 1–27. https://doi.org/10.1145/3498663
[21]
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–199. https://doi.org/10.1016/j.entcs.2018.11.009
[22]
C. Heunen and J. Vicary. 2019. Categories for quantum theory. Oxford University Press. isbn:9780198739616
[23]
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 (CPP 2021). Association for Computing Machinery, New York, NY, USA. 327–342. isbn:9781450382991 https://doi.org/10.1145/3437992.3439922
[24]
R. P. James and A. Sabry. 2012. Information Effects. In POPL ’12: Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of programming languages. ACM, 73–84. https://doi.org/10.1145/2103656.2103667
[25]
N. Johnson and D. Yau. 2021. Bimonoidal Categories, E_n-Monoidal Categories, and Algebraic K-Theory. https://doi.org/10.48550/arXiv.2107.10526
[26]
M. L. Laplaza. 1972. Coherence for distributivity. In Coherence in categories (Lecture Notes in Mathematics, 281). Springer, 29–65. https://doi.org/10.1007/BFb0059555
[27]
J. P. May. 1977. E_∞ Ring Spaces and E_∞ Ring Spectra. Springer. isbn:978-3-540-08136-4
[28]
M. A. Nielsen and I. Chuang. 2010. Quantum Computation and Quantum Information. Cambridge University Press. isbn:9781107002173
[29]
T. Satoh, S. Oomura, M. Sugawara, and N. Yamamoto. 2022. Pulse-engineered controlled-V gate and its applications on superconducting quantum device. IEEE Transactions on Quantum Engineering, 3 (2022), 3101610. https://doi.org/10.1109/TQE.2022.3170008
[30]
P. Selinger. 2015. Generators and relations for n-qubit Clifford operators. Logical Methods in Computer Science, Volume 11, Issue 2 (2015), June, https://doi.org/10.2168/LMCS-11(2:10)2015
[31]
T. Sleator and H. Weinfurter. 1995. Realizable Universal Quantum Logic Gates. Phys. Rev. Lett., 74 (1995), 5, 4087–4090. https://doi.org/10.1103/PhysRevLett.74.4087
[32]
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 ’15). ACM, 395–406. https://doi.org/10.1145/2676726.2676999
[33]
M. K. Thomsen, R. Kaarsgaard, and M. Soeken. 2015. Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics. In Reversible Computation. Springer International Publishing, 200–215. https://doi.org/10.1007/978-3-319-20860-2_13
[34]
T. Toffoli. 1980. Reversible computing. In Automata, Languages and Programming, J. de Bakker and J. van Leeuwen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 632–644. isbn:978-3-540-39346-7 https://doi.org/10.1007/3-540-10003-2_104
[35]
N. Yanofsky and M. A. Mannucci. 2008. Quantum Computing for Computer Scientists. Cambridge University Press. https://doi.org/10.1017/CBO9780511813887
[36]
L. Yeh and J. van de Wetering. 2022. Constructing All Qutrit Controlled Clifford+T gates in Clifford+T. In Reversible Computation. Springer, 28–50. https://doi.org/10.1007/978-3-031-09005-9_3
Index Terms
- With a Few Square Roots, Quantum Computing Is as Easy as Pi
Recommendations
Enriched Presheaf Model of Quantum FPC
Selinger gave a superoperator model of a first-order quantum programming language and proved that it is fully definable and hence fully abstract. This paper proposes an extension of the superoperator model to higher-order programs based on modules over ...
How to Bake a Quantum Π
We construct a computationally universal quantum programming language QuantumΠ from two copies of Π, the internal language of rig groupoids. The first step constructs a pure (measurement-free) term language by interpreting each copy of Π in a ...
The equational theory of Kleene lattices
Languages and families of binary relations are standard interpretations of Kleene algebras. It is known that the equational theories of these interpretations coincide and that the free Kleene algebra is representable both as a relation and as a language ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2024
2820 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 January 2024
Published in PACMPL Volume 8, Issue POPL
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSERC
- US National Science Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 463Total Downloads
- Downloads (Last 12 months)463
- Downloads (Last 6 weeks)78
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
Cited By
View all- Heunen CKornell Avan der Schaaf N(2024)Axioms for the category of Hilbert spaces and linear contractionsBulletin of the London Mathematical Society10.1112/blms.1301056:4(1532-1549)Online publication date: 24-Feb-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in