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^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.
Users
Please
log in to take part in the discussion (add own reviews or comments).