With a Few Square Roots, Quantum Computing Is as Easy as Pi

Jacques Carette, Chris Heunen, Robin Kaarsgaard, Amr Sabry

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Article number19
Pages (from-to)546-574
Number of pages29
JournalProceedings of the ACM on Programming Languages
Issue numberPOPL
Publication statusPublished - 5 Jan 2024
Event51st ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2024) - London, United Kingdom
Duration: 17 Jan 202419 Jan 2024
Conference number: 51


Dive into the research topics of 'With a Few Square Roots, Quantum Computing Is as Easy as Pi'. Together they form a unique fingerprint.

Cite this