一句话：给 rig groupoid 增加两个映射和三条等式，即可得到量子计算通用语义及可靠完备等式理论。
论文研究经典可逆语言 Π 的语义模型 rig groupoid 能否扩展到量子计算。作者证明，只要在 rig groupoid 上加入两个映射及三条等式：单位对象 1 上恒等态射的 8 次根，以及 1+1 上对称态射的平方根，即可得到量子计算的语义模型。由于平方根可能不唯一甚至平凡，作者引入非退化公理约束这两个映射，并将其与 Hadamard 门的 Euler 分解联系起来。该构造被转化为 Π 的量子扩展，形成计算通用的量子编程语言，并具有相对 Clifford 门集、限制在 ≤2 qubit 的 Clifford+T 门集以及计算通用的 Gaussian Clifford+T 门集的可靠且完备等式理论。
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.
@article{paperbot2602,
title = {With a Few Square Roots, Quantum Computing Is as Easy as Pi},
author = {Jacques Carette and Chris Heunen and Robin Kaarsgaard and Amr Sabry},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {POPL},
year = {2024},
doi = {10.1145/3632861}
}