With a Few Square Roots, Quantum Computing is as Easy as Π

Abstract

Rig groupoids provide a semantic model of \PiLang, 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 $8^{\text{th}}$ 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 \PiLang, called \SPiLang, 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 $\le 2$ qubits, and the computationally universal Gaussian Clifford+T gate set.

References in corpus (13)

• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Interacting Quantum Observables: Categorical Algebra and Diagrammatics
• Exact synthesis of multiqubit Clifford+T circuits
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
• Generators and relations for n-qubit Clifford operators
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• Formalizing of Category Theory in Agda
• Pulse-engineered Controlled-V gate and its applications on superconducting quantum device
• Circuit Extraction for ZX-diagrams can be #P-hard
• Reversible effects as inverse arrows
• Symmetries in Reversible Programming: From Symmetric Rig Groupoids to Reversible Programming Languages

Cited by in corpus (4)

• Axioms for the category of Hilbert spaces and linear contractions
• Free Quantum Computing
• Quantum Circuits Are Just a Phase
• Compositional Reversible Computation