Geometry of abstraction in quantum computation

Abstract

Quantum algorithms are sequences of abstract operations, performed on non-existent computers. They are in obvious need of categorical semantics. We present some steps in this direction, following earlier contributions of Abramsky, Coecke and Selinger. In particular, we analyze function abstraction in quantum computation, which turns out to characterize its classical interfaces. Some quantum algorithms provide feasible solutions of important hard problems, such as factoring and discrete log (which are the building blocks of modern cryptography). It is of a great practical interest to precisely characterize the computational resources needed to execute such quantum algorithms. There are many ideas how to build a quantum computer. Can we prove some necessary conditions? Categorical semantics help with such questions. We show how to implement an important family of quantum algorithms using just abelian groups and relations.

29 pages, 42 figures; Clifford Lectures 2008 (main speaker Samson Abramsky); this version fixes a pstricks problem in a diagram

References in corpus (3)

• A Structural Approach to Reversible Computation
• Toy quantum categories
• Quantum measurements and finite geometry

Cited by in corpus (18)

• The Topology of Quantum Algorithms
• Dilation of states and processes in operational-probabilistic theories
• Categorical Probabilistic Theories
• Bridging the gap between general probabilistic theories and the device-independent framework for nonlocality and contextuality
• Reversibility and the structure of the local state space
• Reversible monadic computing
• A Graphical Calculus for Lagrangian Relations
• Separability Criterion for Quantum Effects
• Differentiating and Integrating ZX Diagrams with Applications to Quantum Machine Learning
• Monads on dagger categories
• Elliptic complexes over $C^{\ast }$-algebras of compact operators
• A dataflow programming framework for linear optical distributed quantum computing
• Spectral Presheaves, Kochen-Specker Contextuality, and Quantale-Valued Relations
• On the Structure of Abstract H*-Algebras
• Lambek pregroups are Frobenius spiders in preorders
• Monoidal computer I: Basic computability by string diagrams
• Causality and deceit: Do androids watch action movies?
• Some remarks on multicategories and additive categories