Oxford Comlab

[This is a joint seminar with OASIS]

A formulation of quantum mechanics in terms of symmetric monoidal categories

provides a logical foundation as well as a purely diagrammatic calculus for

it. This approach was initiated in 2004 in a joint paper with Samson

Abramsky (Ox). An important role is played by certain Frobenius comonoids,

abstract bases in short, which provide an abstract account both on classical

data and on quantum superposition. Dusko Pavlovic (Ox), Jamie Vicary (Ox)

and I showed that these abstract bases are indeed in 1-1 correspondence with

bases in the category of Hilbert spaces, linear maps, and the tensor

product. There is a close relation between these abstract bases and linear

logic. Joint work with Ross Duncan (Ox) shows how incompatible abstract

basis interact; the resulting structures provide a both logical and

diagrammatic account which is sufficiently expressive to describe any state

and operation of "standard" quantum theory, and solve standard problems in a

non-standard manner, either by diagrammatic rewrite or by automation.

But are there interesting non-standard models too, and what do these teach

us? In this talk we will survey the above discussed approach, present some

non-standard models, and discuss in how they provide new insights in quantum

non-locality, which arguably caused the most striking paradigm shift of any

discovery in physics during the previous century. The latter is joint work

with Bill Edwards (Ox) and Rob Spekkens (Perimeter Institute).

Fixed-point logics are a class of logics designed for formalising

recursive or inductive definitions. Being initially studied in

generalised recursion theory by Moschovakis and others, they have later

found numerous applications in computer science, in areas

such as database theory, finite model theory, and verification.

A common feature of most fixed-point logics is that they extend a basic

logical formalism such as first-order or modal logic by explicit

constructs to form fixed points of definable operators. The type of

fixed points that can be formed as well as the underlying logic

determine the expressive power and complexity of the resulting logics.

In this talk we will give a brief introduction to the various extensions

of first-order logic by fixed-point constructs and give some examples

for properties definable in the different logics. In the main part of

the talk we will concentrate on extensions of first-order

logic by least and inflationary fixed points. In particular, we

compare the expressive power and complexity of the resulting logics.

The main result will be to show that while the two logics have rather

different properties, they are equivalent in expressive power on the

class of all structures.