Source-linked AI summary
Physics, Topology, Logic and Computation: A Rosetta Stone
John C. Baez, Mike Stay
TL;DR
The paper addresses the need to translate concepts across physics, topology, logic, and computation. It makes selected analogies precise using closed symmetric monoidal categories, concluding that shared object-and-process structures organize correspondences across the fields. The treatment also points to further connections, including universal quantum computation by moving anyons.
Problem
Researchers across physics, topology, logic, and computation use differing terminology and notation, while their related systems and processes lack a shared Rosetta Stone.
Method
The paper compares the four fields through objects, morphisms, string diagrams, closed symmetric monoidal categories, propositional logic, and a simple computation model.
Results
The paper presents an expanded Rosetta Stone showing analogies among the four fields, including shared object-and-process structures organized by closed symmetric monoidal categories.
Takeaways & Limitations
The analogies support viewing the overlap among physics, topology, logic, and computation as a possible general science of systems and processes.
Takeaways & Limitations
The treatment is sketchy, narrowly focused, and idiosyncratic, and the broader theory with additional categorical structure remains substantially unexplored.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper presents category theory as a Rosetta Stone for translating analogies among physics, topology, logic, and computation. It motivates this program through diagrammatic representations of processes, proofs, and programs, then focuses on closed symmetric monoidal categories.
- A category organizes objects and morphisms, which can represent systems and processes in physics, including Hilbert spaces and linear operators.
- Linear operators can be represented diagrammatically, with their behavior determined by topology rather than geometric deformation; they closely resemble cobordisms.A cobordism is an n-dimensional manifold connecting manifolds of one dimension less.
- Logic treats propositions as objects and proofs as morphisms, while computer science treats data types as objects and programs as morphisms.Flow charts for programs are abstractly similar to Feynman diagrams.
- Quantum cryptography and quantum computation helped connect physicists and topologists with logicians and computer scientists by framing quantum processes as information processing.Category theory makes the analogy between flow charts and Feynman diagrams more precise and powerful.
- The paper addresses differing terminology and notation by comparing the four fields through a proposed Rosetta Stone of interlocking analogies.The authors describe this shared overlap as a possible general science of systems and processes.
- The exposition develops closed symmetric monoidal categories through background, string diagrams, propositional and linear logic, a computation model, and a concluding expanded Rosetta Stone.It assumes no prior knowledge of category theory, proof theory, or computer science.
2 The Analogy Between Physics and Topology
This section develops the analogy between quantum processes and topological cobordisms through category theory, using string diagrams and examples from Hilb and nCob. It introduces categorical structures that also connect to logic and computation.
- Physics and topology: Hilb uses Hilbert spaces as objects and linear operators as morphisms, while nCob uses manifolds as objects and cobordisms as morphisms.These categories provide the central physics–topology analogy.
- Categorical structures: Hilb and nCob are compact symmetric monoidal categories, whereas Set is cartesian closed and structurally different from them.The paper uses this contrast to organize its comparison of categorical examples.
- String diagrams: String diagrams represent categorical processes pictorially, with wires for objects and black boxes for morphisms connected by composition.They make composition, identities, and associativity visually explicit.
- Monoidal structure and quantum information: Because Hilb has a noncartesian tensor product, quantum states need not be assembled from separate subsystem states, and information cannot be freely duplicated or deleted.The section connects these features to Bell’s theorem and the no-cloning and no-deletion theorems.
- Symmetry and dimension: Tang_k gains composition, parallel composition, and braiding as dimension increases, then stabilizes at k = 3, with Tang_k equivalent to 1Cob for k ≥3.The stabilization is attributed to the ability to untie all knots in 4-dimensional space.
- Closed and dagger categories: Closed categories unify encoding a morphism as a state, recovering it by evaluation, and treating processes as function-like objects across physics, topology, logic, and computation.Dagger categories add morphism reversal, while the discussion notes that the inner product has not yet entered the Hilbert-space analysis.
3 Logic
The paper connects logic with category theory by representing propositions as objects and proofs or implications as morphisms, then identifies categorical structures corresponding to logical systems. It develops intuitionistic and linear fragments while emphasizing the duality and omissions that distinguish them from classical logic.
- 3.1 Background: Logic can be modeled categorically by taking propositions as objects and implications as morphisms, producing a category with at most one morphism between objects.A morphism exists exactly when one proposition implies another.
- 3.1 Background: Intuitionistic propositional logic yields a cartesian closed poset, with conjunction as product, truth as terminal object, and implication as internal hom.The defining relation is X ∧Y implies Z iff Y implies X ⇒Z.
- 3.1 Background: Adding disjunction and falsity makes the opposite category cartesian, so the resulting structure is precisely a Heyting algebra.Negation is definable as X ⇒⊥, so it adds no further structure.
- 3.2 Proofs as Morphisms: The paper restricts its later logic to the fragment using ∧, ⊤ and ⇒, omitting disjunction, falsity, contraction, and weakening.This narrower fragment is chosen to study closed symmetric monoidal categories.
- 3.3 Logical Theories from Categories: Categorical duality explains logical mirror symmetry, while cut elimination makes composition redundant in proofs and yields finite homsets with decidable morphism equality in free categories.These consequences are stated for the free symmetric monoidal closed category on any set of objects.
- 3.2 Proofs as Morphisms: Closed symmetric monoidal categories correspond to multiplicative intuitionistic linear logic, where proofs become morphisms modulo equations defining categorical structure.The construction takes propositions as objects and equivalence classes of proofs as morphisms.
4 Computation
The paper presents lambda calculus as a simple model of software and uses it to connect computation with category theory. It develops correspondences between typed or linear lambda theories and cartesian closed or closed symmetric monoidal categories.
- 4.1 Background: The lambda calculus models software, contrasting with Turing machines as idealized models of computer hardware.
- 4.1 Background: Lambda terms are built from variables, application, and lambda-abstraction, with terms functioning both as programs and data.Lambda-abstraction represents a program that takes x as input and returns t as output.
- 4.1 Background: Beta, eta, and alpha rules rewrite lambda terms, making program execution a sequence of computational transformations.Beta reduction substitutes an argument for free occurrences of a variable; repeated rewriting runs the program.
- 4.1 Background: Church and Kleene built Boolean logic, natural numbers, arithmetic operations, and more complicated functions from the simple lambda-calculus formalism.Church numerals represent programs that apply an input program repeatedly, and arithmetic can be defined through such numerals.
- 4.1 Background: Computation in the lambda calculus can be carried out through repeated rewrites, including arithmetic such as multiplying Church numerals.The paper illustrates multiplication by reducing a program that raises a program to the sixth power.
- 4.2–4.3 Categorical Correspondences: Every typed lambda-theory gives a cartesian closed category and conversely, while every linear type theory gives a closed symmetric monoidal category and conversely.The constructions in both directions form functors that are inverses up to natural isomorphism, so the corresponding categories are equivalent.
5 Conclusions
The paper sketches category theory as a Rosetta Stone linking physics, topology, logic, and computation through shared structures and processes. It closes by illustrating both the practical reach and the substantial scope of these connections.
- Common framework: Category theory clarifies analogies among physics, topology, logic, and computation by organizing each field’s things and processes into categories with shared features.The paper focuses on features present in every closed symmetric monoidal category and presents them in an expanded Rosetta Stone.
- Scope: The paper’s framework remains partial, leaving extra categorical structure and higher n-categorical connections for further development.The authors explicitly characterize their treatment as only scratching the surface.
- Physical applications: Modular tensor categories connect string theory, topological quantum field theory, knot theory, and models of the fractional quantum Hall effect.These categories describe possible behaviors of anyonic excitations in superconducting thin films under conditions such as magnetic-field strength.
- Quantum computation: Certain anyon systems can function as universal quantum computers, making arbitrary computations possible in principle by moving anyons around.The paper notes that practical implementation would be difficult.
- Unified interpretation: A single diagram can represent a quantum process, a tangle, a computation, or an abstract morphism in a braided monoidal category.This convergence exemplifies the proposed general science of systems and processes.