Reference. How to Bake a Quantum Π

We construct a computationally universal quantum programming language Quantum Π from two copies of Π , the internal language of rig groupoids. The first step constructs a pure (measurement-free) term language by interpreting each copy of Π in a generalisation of the category Unitary in which every morphism is “rotated” by a particular angle, and the two copies are amalgamated using a free categorical construction expressed as a computational effect. The amalgamated language only exhibits quantum behaviour for specific values of the rotation angles, a property which is enforced by imposing a small number of equations on the resulting category. The second step in the construction introduces measurements by layering an additional computational effect.

Cite

Cite as @carette-2024-how (helia, typst) · \cite{carette-2024-how} (LaTeX)
BibTeX
bibtex · 1 line
@article{carette-2024-how, title={How to Bake a Quantum Π}, volume={8}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3674625}, DOI={10.1145/3674625}, number={ICFP}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Carette, Jacques and Heunen, Chris and Kaarsgaard, Robin and Sabry, Amr}, year={2024}, month=Aug, pages={1–29} }
hayagriva YAML (typst)
yaml · 20 lines
carette-2024-how:
  type: article
  title: How to Bake a Quantum Π
  author:
  - Carette, Jacques
  - Heunen, Chris
  - Kaarsgaard, Robin
  - Sabry, Amr
  date: 2024-08
  page-range: 1-29
  url: http://dx.doi.org/10.1145/3674625
  serial-number:
    doi: 10.1145/3674625
    issn: 2475-1421
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    publisher: Association for Computing Machinery (ACM)
    issue: ICFP
    volume: 8
Cited by (1)

Compositional Reversible Computation carette-2024-compositional

DOI · arXiv
Cites 57 works (1 here)
With notes (1)

With a Few Square Roots, Quantum Computing Is as Easy as Pi carette-2024-with

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.
PDF · DOI · arXiv · pldb
External (56)
carette-2024-how reference entries/refs/carette-2024-how/carette-2024-how.hel