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^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 $2$ qubits, and the computationally universal
Gaussian Clifford+T gate set.
Description
[2310.14056] With a Few Square Roots, Quantum Computing is as Easy as Π
%0 Generic
%1 carette2023square
%A Carette, Jacques
%A Heunen, Chris
%A Kaarsgaard, Robin
%A Sabry, Amr
%D 2023
%K programming quantum_computing
%T With a Few Square Roots, Quantum Computing is as Easy as \Pi
%U http://arxiv.org/abs/2310.14056
%X 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^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 $2$ qubits, and the computationally universal
Gaussian Clifford+T gate set.
@misc{carette2023square,
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.},
added-at = {2023-10-24T13:23:23.000+0200},
author = {Carette, Jacques and Heunen, Chris and Kaarsgaard, Robin and Sabry, Amr},
biburl = {https://www.bibsonomy.org/bibtex/2bde0172ca238f9ea6ff0ab2ad7c1b174/tabularii},
description = {[2310.14056] With a Few Square Roots, Quantum Computing is as Easy as Π},
interhash = {64206b9d5201d97446649da1209ca0c1},
intrahash = {bde0172ca238f9ea6ff0ab2ad7c1b174},
keywords = {programming quantum_computing},
note = {cite arxiv:2310.14056},
timestamp = {2023-10-24T13:23:23.000+0200},
title = {With a Few Square Roots, Quantum Computing is as Easy as {\Pi}},
url = {http://arxiv.org/abs/2310.14056},
year = 2023
}