Physics, Topology, Logic and Computation: A Rosetta Stone

Abstract

In physics, Feynman diagrams are used to reason about quantum processes. In the 1980s, it became clear that underlying these diagrams is a powerful analogy between quantum physics and topology: namely, a linear operator behaves very much like a "cobordism". Similar diagrams can be used to reason about logic, where they represent proofs, and computation, where they represent programs. With the rise of interest in quantum cryptography and quantum computation, it became clear that there is extensive network of analogies between physics, topology, logic and computation. In this expository paper, we make some of these analogies precise using the concept of "closed symmetric monoidal category". We assume no prior knowledge of category theory, proof theory or computer science.

73 pages, 8 encapsulated postscript figures

References in corpus (7)

• Anyons and the quantum Hall effect - a pedagogical review
• A Lambda Calculus for Quantum Computation
• A Prehistory of n-Categorical Physics
• Lecture notes on the lambda calculus
• POVMs and Naimark's theorem without sums
• On classification of modular tensor categories
• De-linearizing Linearity: Projective Quantum Axiomatics from Strong Compact Closure

Cited by in corpus (80)

• A mathematical theory of resources
• Division Algebras and Quantum Theory
• Phase groups and the origin of non-locality for qubits
• Interacting Hopf Algebras
• Lambek vs. Lambek: Functorial Vector Space Semantics and String Diagrams for Lambek Calculus
• Causal categories: relativistically interacting processes
• A Universal Construction for (Co)Relations
• Deligne Categories in Lattice Models and Quantum Field Theory, or Making Sense of $O(N)$ Symmetry with Non-integer $N$
• Equality Saturation: A New Approach to Optimization
• On unitary 2-representations of finite groups and topological quantum field theory
• Categories for the practising physicist
• The Topology of Quantum Algorithms
• Reconstructing quantum theory from diagrammatic postulates
• Grammar-aware sentence classification on quantum computers
• Axioms for retrodiction: achieving time-reversal symmetry with a prior
• Towards 3-Dimensional Rewriting Theory
• Categorical Quantum Circuits
• Category-Theoretic Quantitative Compositional Distributional Models of Natural Language Semantics
• Algebras of Open Dynamical Systems on the Operad of Wiring Diagrams
• The Expectation Monad in Quantum Foundations
• Interacting Hopf Algebras: the theory of linear systems
• Non-Commutative Geometry, Categories and Quantum Physics
• A correspondence between rooted planar maps and normal planar lambda terms
• Quantum Gauge Field Theory in Cohesive Homotopy Type Theory
• Quantization via Linear homotopy types
• Epistemic Horizons and the Foundations of Quantum Mechanics
• Dilations and information flow axioms in categorical probability
• Division Algebras, Supersymmetry and Higher Gauge Theory
• Parallel Self-Testing of the GHZ State with a Proof by Diagrams
• ZX-Calculus and Extended Wolfram Model Systems II: Fast Diagrammatic Reasoning with an Application to Quantum Circuit Simplification
• Itsy bitsy topological field theory
• On Constructive Axiomatic Method
• Tangle Machines
• ZX-Calculus and Extended Hypergraph Rewriting Systems I: A Multiway Approach to Categorical Quantum Information Theory
• Infinite-Dimensionality in Quantum Foundations: W*-algebras as Presheaves over Matrix Algebras
• Renormalization and Computation II: Time Cut-off and the Halting Problem
• A Type Theory for Strictly Unital $\infty$-Categories
• Network Models from Petri Nets with Catalysts
• Teaching machines to understand data science code by semantic enrichment of dataflow graphs
• A diagrammatic view of differential equations in physics
• Categories in control: applied PROPs
• Logic and linear algebra: an introduction
• The algebra and machine representation of statistical models
• Compositional Deep Learning
• Compositionality and String Diagrams for Game Theory
• Towards a unified framework for decomposability of processes
• Substructural fixed-point theorems and the diagonal argument: theme and variations
• Variations on the Choi-Jamiolkowski isomorphism
• Categorical Quantum Dynamics
• Categorical Vector Space Semantics for Lambek Calculus with a Relevant Modality (Extended Abstract)
• On Strict Higher C*-categories
• Computing with Coloured Tangles
• Structured and Decorated Cospans from the Viewpoint of Double Category Theory
• Hidden Markov Models and the Bayes Filter in Categorical Probability
• An electrical engineering perspective on naturality in computational physics
• Language-independence of DisCoCirc's Text Circuits: English and Urdu
• The Abstract Structure of Quantum Algorithms
• Graphical Calculus for products and convolutions
• Duality for Convexity
• Symmetry and composition in probabilistic theories
• Using Z3 to Verify Inferences in Fragments of Linear Logic
• A Graphical Interface for Category Theory Proofs in Coq
• A Category Theory Approach to Interoperability
• Applied Category Theory for Genomics -- An Initiative
• The Resurgence of the G(2) Group for the Strong Sector and the Emergence of Dark Matter
• The dagger lambda calculus
• String diagrams for game theory
• Computational Complexity of Deciding Provability in Linear Logic and its Fragments
• Cobordisms and commutative categorial grammars
• Bicategorical Semantics for Nondeterministic Computation
• Enriched Lawvere Theories for Operational Semantics
• Combinatorial Decision Dags: A Natural Computational Model for General Intelligence
• Information Theoretic Resources in Quantum Theory
• Semantics of HTS AC loss modelling: Theories, models and experiments
• Can category-theoretic semantics resolve the problem of the interpretation of the quantum state vector?
• The Grothendieck Construction in Categorical Network Theory
• Combinatorics and algebra of tensor calculus
• Radically Compositional Cognitive Concepts
• Beyond Operator Systems
• Categorical Vector Space Semantics for Lambek Calculus with a Relevant Modality