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
Cited by (1)
Compositional Reversible Computation carette-2024-compositional
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.
External (56)
- Code for How to Bake a Quantum Pi (2024)
- Universal Properties of Partial Quantum Maps (2022)
- Embracing the laws of physics: Three reversible models of computation (2022)
- Symmetries in reversible programming: from symmetric rig groupoids to reversible programming languages (2022)
- Semantics for variational Quantum programming (2022)
- Quanundrum - a platform to simulate thought experiments with quantum agents (software) (2022)
- Qunity: A Unified Language for Quantum and Classical Computing (2022)
- A computational interpretation of compact closed categories: reversible programming with negative and fractional types (2021)
- Quantum information effects (2021)
- Silq: a high-level quantum language with safe uncomputation and intuitive semantics (2020)
- Quantum Programming with Inductive Datatypes: Causality and Affine Type Theory (2020)
- Classical Control, Quantum Circuits and Linear Logic in Enriched Category Theory (2020)
- Reversible Programs Have Reversible Semantics (2019)
- Categories for Quantum Theory (2019)
- Quantum channels as a categorical completion (2019)
- Circuit relations for real stabilizers: towards TOF+H (2019)
- ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity (2018)
- Reversible effects as inverse arrows (2018)
- \mathsf CoreFun : A Typed Functional Reversible Core Language (2018)
- From Symmetric Pattern-Matching to Quantum Control (2018)
- A Short Introduction to Hilbert Space Theory (2017)
- Quantum Programs as Kleisli Maps (2017)
- Computing with Semirings and Weak Rig Groupoids (2016)
- Monads on dagger categories (2016)
- QWIRE: a core language for quantum circuits (2016)
- Von Neumann Algebras Form a Model for the Quantum Lambda Calculus (2016)
- DEMONIC programming: a computational language for single-particle equilibrium thermodynamics, and its formal semantics (2015)
- Basic Category Theory (2014)
- Algebraic Effects, Linearity, and Quantum Programming Languages (2014)
- The Oxford Questions on the foundations of quantum physics (2013)
- Quipper: a Scalable Quantum Programming Language (2013)
- On the functor l^2 (2013)
- Environment and Classical Channels in Categorical Quantum Mechanics (2012)
- Monoidal indeterminates and categories of possible worlds (2012)
- Information effects (2012)
- Strong Complementarity and Non-locality in Categorical Quantum Mechanics (2012)
- Towards a reversible functional language (2011)
- The Quantum IO Monad (2009)
- Categorical semantics for arrows (2009)
- Amalgamations of Categories (2009)
- Quantum Lambda Calculus (2009)
- Interacting quantum observables : categorical algebra and diagrammatics (2008)
- Quantum Computing for Computer Scientists (2008)
- A reversible programming language and its invertible self-interpreter (2007)
- Abstract Scalars, Loops, and Free Traced and Strongly Compact Closed Categories (2005)
- Programming with Arrows (2005)
- A Lambda Calculus for Quantum Computation with Classical Control (2005)
- Towards a quantum programming language (2004)
- Both Toffoli and Controlled-NOT Need Little Help to Do Universal Quantum Computing (2003)
- A simple proof that Toffoli and Hadamard are quantum universal (2003)
- Quantum Computation and Quantum Information (2002)
- Premonoidal categories and notions of computation (1997)
- A fast quantum mechanical algorithm for database search (1996)
- Inverse categories (1979)
- Coherence for distributivity (1972)
- Natural Associativity and Commutativity (1963)