Abstracts

Samson Abramsky, Information Flow in Physics, Geometry, Logic and Computation

In my lectures, I will describe a broad program that has been initiated to model information flow in these and related areas. This includes a high-level reformulation of quantum information and quantum computing using category theory that have been shown to capture all of the fundamental components of the theory. The approach supports reasoning about classical and quantum communication in the same model. The approach also has provided what are arguably the first completely formal descriptions and proofs of correctness of several key quantum informatic protocols, e.g. (logic-gate) teleportation, superdense coding, and one-way computational schemes. It also provides a description of the quantum state, as well as the flow of information from the quantum state to the classical world (measurements), and from the classical world to the quantum state (control), all of which are important for reasoning about security in a quantum setting.

Howard Barnum and Alexander Wilce, Broadcasting, Teleportation, Bit Commitment and All That: A Survey from Altitude

In a well-known generalization of classical probability theory, arbitrary compact convex sets serve as abstract "state spaces" for physical systems; classical systems correspond to simplices and quantum systems, to state spaces of C*-algebras. One can define natural tensor products for abstract state spaces, modeling composite systems subject to a no-signaling condition. Many familiar quantum-theoretic phenomena, including the possibility of entanglement, disturbance of states by measurement, and no-cloning and no-broadcasting theorems, already appear as consequences of non-classicality at this level of generality. However, the existence of a teleportation protocol is a strong constraint, moving us closer to quantum theory. In this talk, after briefly summarizing the framework of abstract state spaces, we outline what we currently understand about teleportation, bit commitment, remote steering of

ensembles and other information-theoretic tasks in this setting.Time permitting, we will also explore connections with the category-theoretic semantics for quantum protocols developed by Abramsky, Coecke and collaborators, and the similar category-theoretic formalism of Selinger.

Various parts of this talk represent recent and ongoing joint work with Jon Barrett, Matt Leifer, Oscar Dahlsten, Ben Toner, and others.

Rick Blute, Dagger Categories and Algebraic QFT

Adam Brandenburger, Epistemic Game Theory.

Game theory as a field began with the publication of the book Theory of Games and Economic Behavior by John von Neumann and Oskar Morgenstern (1944). A fundamental goal of the field, they explained, was “to find the mathematically complete principles which define ‘rational behavior’ for the participants” in a game (op. cit., p.31). The search for these principles has continued ever since. Recently, it has become clear that to make progress on this question, new tools are needed. The classical definition of a game—as game matrix or tree—needs to be augmented to include a description of what the players think about the game, including what they think about what other players think, and so on. We will describe this “epistemic” approach to game analysis—and present an impossibility result on rationality in games to which it has led.

Bob Coecke, Classical Versus Quantum, ... in pictures

We report on some recent results on the formulation of quantum mechanics in terms of symmetric monoidal categories. This approach aims to provide an operational foundation, a logical axiomatics as well as a purely diagrammatic calculus for it. This approach was initiated in 2004 in a joint paper with Samson Abramsky. A first new concept is that of a classical object, which provides a an account both on classical data and the notion of spectra, while still staying within the category-theoretic realm. It does this in an operational manner by relying on the distinct abilities to copy and delete classical data. Recently, in collaboration with Dusko Pavlovic and Jamie Vicary we showed that these classical objects are indeed in 1-1 correspondence with bases in Hilbert spaces. Also, in collaboration with Pavlovic and Eric Paquette we showed how classical stochastic theory, informatic ordering, as well as abstract convex structure can be extracted from abstract quantum processes through the notion of classical object. Based on the joint work with Ross Duncan on complementary quantum observables, on which we will report here, in collaboration with Bill Edwards we abstractly generated arbitrary multi-partite entangled states; hence equipping multi-partite entanglement with a formal interpretation in terms of information-flow. Finally, we present Rob Spekkens' toy model in purely category-theoretic terms; its quantum-like behaviors are now consequences merely of abstract category-theoretic structure, including all of those discussed above.

Ross Duncan, The Logic of Complementary Quantum Observables

In quantum mechanics not every measurable quantity can possess a well defined value at the same time: the most famous examples are position and momentum, but this phenomenon is ubiquitous in quantum systems . The existence of such incompatible observables is a fundamental feature of the theory, and has been used as a starting point for logical approaches to quantum mechanics back as far as von Neumann. In this talk I will address the question: what is the constructive content of the incompatibility between two observables? Using the categorical approach to quantum mechanics initiated by Abramsky and Coecke, I will describe how a space of classical values can be coded as a quantum observable, and consider the information flow within processes making use of two complementary -- that is to say maximally incompatible -- observables. The resulting structure is closely related to a bialgebra, and yields a beautiful graphical language. This language can be used to perform many calculations concerning quantum circuits, entangled states and quantum algorithms.

Radha Jagadeesan, Games for Authorization

Authorization logics arise naturally in specifications of access control of distributed systems. These logics use lax modalities to formally describe the context switch - such as the one from sender to receiver - in distributed systems. For example, when a participant A affirms proposition PHI, a recipient B gets the effect A says PHI, rather than the more absolute truth PHI . Recent results of Abadi, Garg/Pfenning demonstrate that these logics satisfy non-interference properties. In its simplest form,

non-interference ensures that there is no purely logical way for a principal B to deduce PHI from an A says PHI (an utterance of PHI by A).

In this talk, we describe a games model of authorization logics. Strategies in this model directly encode the absence of information flow amongst different principals. Our results provide the the rudiments of a uniform semantic treatment of non-interference that encompasses different logics (eg. linear and intuitionist) and rich features (eg. recursion).

This is joint work with Samson Abramsky.

Sam Lomonaco, Quantum Knots
In this talk, we create a mathematical model, called a quantum knot (or link), which naturally represents knotted dynamical quantum vortices that arise in physical systems. In this way, we will show how to create physical quantum systems whose states are knots (or links). In this model, the Reidemeister moves become unitary transformations of the quantum systems. We then investigate the dynamic behavior of quantum knots determined by a number of chosen Hamiltonians.

A surprising spinoff of this work is that we have inadvertently created a formal axiomatic system that fully captures and represents tame knot theory as a context-free formal language, called knot mosaics. This formal will also be discussed in detail.This is a preliminary report of ongoing research. This research is in collaboration with Louis Kauffman. The PowerPoint slides for this talk will be posted at: http://www.csee.umbc.edu/~lomonaco/Lectures.html

Keye Martin and Prakash Panangaden, Domain Theory and Spacetime Structure I and II

Domains are special types of posets that have played an important role in theoretical computer science since the late 1960s when they were discovered by Dana Scott for the purpose of providing a semantics for the lambda calculus. They are partially ordered sets that carry intrinsic (order theoretic) notions of completeness and approximation. The basic intuition is that the order relation captures the idea of approximation qualitatively. There is an abstract notion of ﬁnite piece of information – or of ﬁnite approximation – which plays a key role in the analysis of computation.

General relativity is Einstein’s theory of gravity in which gravity is understood not in terms of mysterious “universal” forces but rather as part of the geometry of spacetime. The study of spacetime structure from an abstract viewpoint was initiated by Penrose in a dramatic paper in which he showed a fundamental inconsistency of general relativity: the inevitable appearance of singularities. Since the ﬁrst singularity theorems causality has played a key role in understanding spacetime structure. For the past decade Sorkin and others have pursued a program for quantization of gravity based on causal structure. In this approach the causal relation is regarded as the fundamental ingredient and the topology and geometry are secondary.

In a paper that appeared in 2006, we proved that the causality relation is much more than a relation – it turns a globally hyperbolic spacetime into what is known as a bicontinuous poset. The order on a bicontinuous poset allows one to deﬁne an intrinsic topology called the interval topology. On a globally hyperbolic spacetime, the interval topology is the manifold topology. The fact that a globally hyperbolic spacetime is bicontinuous implies that it can be reconstructed in a purely order theoretic manner, beginning from only a countable dense set of events and the causality relation.

Measurements were introduced by Martin in his doctoral thesis when reformulating computation as “a process that evolves in a space of informatic objects. ” A domain provides a mathematical model of such a space and a measurement provides a quantitative measure of the amount of information each object in the domain carries. Examples include capacity on the domain of communication channels in information theory and entropy on both the domains of classical and quantum states. By asking the simple question “are there any natural measurements in general relativity?”, we have learned not only how to reconstruct the geometry of spacetime order theoretically, we have also uncovered a surprising topological distinction between the Newtonian and relativistic notions of time. This work also oﬀers a ﬁrst step toward a purely causal deﬁnition of Lorentz invariance.

Dusko Pavlovic, Geometry of Function Abstraction in Quantum and Classical Computation

Function abstraction is a building block of computation. Indeed, in functional programming and lambda calculus, it is the building block. Using the framework of categorical quantum mechanics, I examine the role of function abstraction in quantum computation. It induces the structure of Frobenius algebra structure of classical objects, and allows distinguishing classical data from quantum data. The obtained distinctions point to the sources of quantum phenomena beyond the standard physical interpretations.

Phil Scott, Feedback, Traces, and Dynamics in Categorical Logic

We survey some recent results that apply monoidal categories with partial feedback to the algebra and dynamics of computation. These range from mathematical frameworks for information flow in proof networks for various logics (for example, for finding algebraic invariants for the dynamics of cut-elimination) to models arising from the semantics of quantum computation (for example, modelling quantum while-loops). The general frameworks and theory are based on various recent notions of partially traced *-categories; we give numerous concrete examples arising from several disciplines.

Phil Scott, Feedback, Traces, and Dynamics in Categorical Logic

2007 - 2008 Clifford Lectures