There are links from the titles of most talks to the slides for the talk.


Big Toy Models: Embedding Physical Theories in Chu Spaces

Samson Abramsky

Oxford University

We show how several types of physical system can be fully embedded in Chu spaces. Separability in Chu spaces picks out the appropriate notions of  ‘fully abstract' representations of physical states. Chu space morphisms correspond to the physically meaningful symmetries. The passage from pure to mixed states is given by a functor on Chu spaces. We consider universal Chu spaces for various classes of systems, and linear types and their physical interpretations.


Probabilistic Interference and Coherence as a General Informatic Phenomenon

Howard Barnum

Perimeter Institute

The kind of interference that is manifested in the two-slit experiment has played a central role in the development and interpretation of quantum theory.  Sorkin defined a hierarchy of levels of interference, with the Nth level manifested in interference experiments using at least N slits; quantum theory has only level two interference in this hierarchy, the lowest that counts as proper interference.  We adapt Sorkin's hierarchy to the convex sets framework for formulating physical theories, abstracting properties appropriate to "slits" and "multiple-slit experiments".  We consider spectral convex sets, for which every face is the image of a compression, a type of projection map with properties appropriate to describe passage through a set of slits.  We obtain two main results. The first characterizes multiple-slit experiments that exhibit kth order interference as ones in which the states that pass the slits when all slits are open, have components that are not in the linear span of the states that pass when one or more of the slits that is closed.  These components are higher-order analogues of the "off-diagonal" density matrix components responsible for second-order interference in quantum theory.  The second technical result is a demonstration that the state spaces of finite-dimensional atomic Jordan-Banach algebras, a very restricted class of convex sets that includes the finite-dimensional quantum mechanical state spaces, and one that has often been the object of axiomatic characterization as an intermediate step toward characterizing quantum mechanics

itself---exhibit at most level two interference.


Origins of Epistemic Game Theory

Adam Brandenburger


In 1935, Oskar Morgenstern wrote:

    “[T]here is exhibited an endless chain of reciprocally conjectural reactions and counter-

    reactions….  The remedy would lie in analogous employment of the so-called Russell

    theory of types in logistics.  This would mean that on the basis of the assumed

    knowledge by the economic subjects of theoretical tenets of Type I, there can be

    formulated higher propositions of the theory; thus, at least, of Type II.  On the basis of

    information about tenets of Type II, propositions of Type III, at least, may be set up,


We will attempt to trace, from this promising start, the steps forward and backward on the path to the development of epistemic game theory.  This will take us through von Neumann and Morgenstern, Nash, and Harsanyi, to an emerging field of epistemics as of the mid-1980s.  We will continue with some comments on the field of epistemic game theory today.


Depicting Non-locality

Bob Coecke


The punch-line of this talk is to "depict non-locality", that is, to provide a pictorial presentation of the flow of information which, due to Bell/GHZ-type arguments, cannot be given a stochastic spatio-temporal causal explanation.  We will show that in the case of qubits the performed computation is that of an AND-gate on the choices of measurements made by distant observers.  This work points at a research project that classifies the computations which nature performs "outside of space-time".  It builds further on results on so-called "phase-groups of observables" in:

[1] with Ross Duncan: "Interacting quantum observables".  ICALP'08. arXiv:0906.4725

[2] with Bill Edwards and Rob Spekkens: "The group-theoretic origin of quantum non-locality".

Within an abstract category-theoretic setting we in particular reproduce the result of:

[3] Janet Anders and Dan Browne: "Computational power of correlations" Phys Rev Lett 102, 050502 (2009). arXiv:0805.1002

where it was shown that GHZ-correlations enable to boost parity computations into universal classical computation.  Informal introductions to the abstract category-theoretic/diagrammatic framework that constitutes the backbone of our developments are:

[4] "Kindergarten quantum mechanics". arXiv:quant-ph/0510032

[5] "Introducing categories to the practicing physicist". arXiv:0808.1032

Recent extensive tutorial introductions are:

[6] "Quantum picturalism".  Contemporary Physics '09.  arXiv:0908.1787

[7] "Categories for the practicing physicist".  arXiv:0905.3010


Classical Representations of Qubit Channels

Tanner Crowder


A set of qubit channels has a classical representation when it is isomorphic to the convex closure of a group of classical channels.  We prove that there are five such groups, each being either a subgroup of the alternating group on four letters, or a subgroup of the symmetric group on three letters.  Surprisingly, these isomorphisms open up the possibility of doing quantum information theory with classical channels. For instance, every unital qubit channel systematically determines a classical channel whose eigenvalues yield the Holevo capacity of the former. In addition, because the convex closures of any two finite isomorphic groups in SO(3) are themselves isomorphic, qubit channels with classical representations constitute a legitimate form of mathematical structure. As time permits, we shall delve into this interesting structure, characterizing the idempotent, skew-symmetric and even the *stochastic* qubit channels. This is joint work with Keye Martin.


A Pyramid in Quantum Information Theory

Johnny Feng

NRL and Tulane

Because domain theory was introduced to provide a formal mathematical model of programming languages, it was surprising when Martin and Coecke discovered the spectral order on quantum mixed states.  For two dimensional state spaces, the mixed states Ω2 form a Scott domain, and since qubit channels are selfmaps on Ω2, it is natural to ask if they also possess domain theoretic structure.

In this talk, we will characterize the Scott-continuous qubit channels, show that they form a Scott domain in the pointwise order, and show that Holevo capacity is a measurement on the domain of unital channels, in the sense of domain theory.  We will also consider some important operators on the domain of qubit channels itself, including its natural measurement, which turns out to be very different from the Holevo capacity.

The technique used in establishing the order theoretic structure of qubit channels reveals the importance of channels with a diagonal Bloch representation.  The diagonal channels, which form a tetrahedron in R3, have a surprising number of properties which make them special.  We will see how they arise as the convex closure of spin channels, as the classical (4,4) channels which diagonalize in the Hadamard basis, as the free affine monoid over the Klein four group, and even as the qubit channels which arise from quantum teleportation through arbitrary entangled states.  To demonstrate their practical utility, we will use the diagonal channels to calculate the Holevo capacity of an arbitrary unital channel, and provide a simple protocol which can be used to achieve that capacity.


Quantum-Bayesian Coherence

(or, My Favorite Convex Set)

Chris Fuchs

Perimeter Institute

In a quantum-Bayesian delineation of quantum mechanics, the Born Rule cannot be interpreted as a rule for setting measurement-outcome probabilities from an objective quantum state.  (A quantum system has potentially as many quantum states as there are agents considering it.) But what then is the role of the rule?  In this talk, I will argue that it should be seen as an empirical addition to Bayesian reasoning itself.  Particularly, I show how to view the Born Rule as a normative rule in addition to usual Dutch-book coherence.  It is a rule that takes into account how one should assign probabilities to the outcomes of various intended measurements on a physical system, but explicitly in terms of prior probabilities for and conditional probabilities consequent upon the imagined outcomes of a special counterfactual reference measurement. This interpretation is seen particularly clearly by representing quantum states in terms of probabilities for the outcomes of a fixed, fiducial symmetric informationally complete (SIC) measurement. I further explore the extent to which the general form of the new normative rule implies the full state-space structure of quantum mechanics.  It seems to go some way.


Using Information Theory to Find Hidden Structure in Datasets

Peter Hines

York University, UK

Abstract: This talk describes how Shannon information theory allows us to search for hidden structure within sets of data. The same methods allow us to quantify the extent to which structure found is useful in understanding, and making predictions about, data sets.

The methods presented are non-parametric, and are applicable to datasets without a well-defined metric space structure. The original motivation and applications came from the fields of cognitive science and psychology, but as demonstrated within this talk, the methods are much more generally applicable.

The work described is a collaborative project between mathematicians, computer scientists, and cognitive scientists in the UK.


Directed Cohomology

Sanjeevi Krishnan


I will present a cohomology theory for "directed spaces," spaces equipped with temporal structure.  Examples include spacetime manifolds and classifying spaces.  On such spaces, ordinary cohomology groups reveal properties invariant under continuous deformations, while directed cohomology monoids detect finer properties invariant under deformations respecting the temporal structure and thus tease out the "qualitative" structure of time.  Directed cohomology extends several well-known properties of its classical analogue: our new invariants admit chain-theoretic constructions, equivalent homotopical descriptions, axiomatic characterizations, and multiplicative structure.  After presenting the basic theory of directed homotopy and cohomology, I will sketch real and potential applications to concurrent engineering, string rewriting, and informatics.  This talk, aimed at a general audience, assumes no prior experience with directed spaces or cohomology theories.


Implicit State CTMC or How to Count Without Enumerating

Jean Krivine


Joint work with Eric Deeds (Harvard Medical School), Vincent Danos (Edinburgh), Jérôme Feret (INRIA) and Walter Fontana (HMS).

Protein-protein interactions play a crucial role in most cellular functions. Over the past decade, high-throughput techniques combined with statistical analyses have produced a global picture of protein-protein interactions (PPI’s) as scale-free networks with small-world properties. But PPI networks, unlike familiar networks such as the Internet backbone, do not function via the direct transmission of information across persistent physical links. Rather, the edges in such a network represent the potential for local actions that must be implemented through protein-protein binding and other chemical events. The combination of many such events in a cell generates a distribution of protein complexes, ultimately determining the behaviour of cellular processes. To characterize this distribution, and describe how it emerges from a set of local binding rules, we need to construct a dynamic model of the network. This is a serious challenge in view of the enormous numbers of unique molecular species that large networks can generate.

In this talk I will describe such a line of research, based on the model of Yeast PPI collated by Eric Deeds at the Harvard Medical School. On the technical side, we will address the issue of:

    1) the use of an implicit representation of the states of the CTMC in order to fight the explosion in the number of molecular species that one has to track (implicit state CTMC).

    2) the use of an implicit representation of intra-molecular reactions in order to fight the explosion in the number of rules that allows one to generate the CTMC (Bologna algorithm).


Another Way of Organizing Qubits: The Qubit Loop

Jimmie Lawson


The qubits admit a natural loop (non-associative) group structure that is a special kind of Bruck loop. It shares many properties with the loop of Einstein velocity addition and the Mobius loop of the complex unit ball.  The lecture will be an effort to give an expository treatment of this loop, its interesting properties, and its analogy to a real vector



Information in Biology: Metaphor or Model?

Anti-entropy and a Model of Phenotypic Complexity Along Evolution

Giuseppe Longo

ENS, Paris

The major observables in Physics are largely, if not exclusively, based on or derived from energy (conservation properties as symmetries, geodetic principles as least action principles...). Biology forced us to think in the novel terms of “organization” and, even, of inherited organization; an organization whose “complexity”  grows along Evolution and embryogenesis, against energy degradation in Physics (entropy production, also in non-isolated systems).

Then, with World War II, the age of coding, decoding and information started. Information Theory and Cryptography became well defined scientific disciplines, with their own principles and remarkable applications. Can we borrow for the analysis of life phenomena any relevant principle or precise result from these scientific areas? A critique of the abuse of ‘’Information’’ in Biology will be hinted.

Some recent work will be introduced on an quantification of “biological (phenotypic) organization”  by a proper observable to Biology, Anti-entropy. The idea will be derived by conceptual dualities w. r. to Quantum Physics, where the operatorial approach by Schrödinger to his famous equation will (“dually”) guide us towards an equational modelling of Gould’s analysis of “phenotypic complexity” along Darwin’s Evolution and, if time allows, to some applications to embryogenesis.

Longo G. “From exact sciences to life phenomena: following Schrödinger and Turing on Programs, Life and Causality”, in "From Type Theory to Morphological Complexity: A Colloquium in Honor of Giuseppe Longo’s 60th birthday", special issue of  Information and Computation, 207, 5: pp. 545-558, 2009.

Bailly F., Longo G. “Biological Organization and Anti-Entropy”, J. Biological Systems, Vol. 17, No. 1, pp. 63-96, 2009.


Black Holes and Information

Prakash Panangaden

McGill University

One of the central tenets of relativity is that information cannot be propagated beyond the light cone.  In some spacetimes the causal structure is so distorted that there are trapped regions from which no information can escape; the black hole spacetimes are the most well-known examples of these.  Intuitively such a region should possess entropy and thus information.  Arguing from a close formal relationship between black hole mechanics

and thermodynamics, Bekenstein predicted that black holes should radiate like black bodies.  This formal connection was dramatically vindicated by Hawking's discovery - based on quantum field theory in curved spaectimes - that black holes radiate at the temperature predicted by Bekenstein.  A later calculation of Wald and mine showed that this continued to be the case with respect to stimulated emission.  These results have

led to decades of speculation about the fate of the information that falls into a black hole.  I will review some of this discussion including some recent work by Hayden and Preskill.

This is a purely expository talk and will not get into the technical details of the calculations involved.  It should be readily accessible to everyone at IP 2009.


A New Description of Maximally-entangled Measurements

Jamie Vicary

Oxford University

Many quantum protocols make crucial use of the ability to measure qubits in a maximally-entangled basis. We present an abstract description of this process, which allows these protocols to be presented much more elegantly and compactly, and allows for succinct correctness proofs.


Events, Causality and Symmetry

Glynn Winskel

University of Cambridge Computer Laboratory, UK.

How are we to extend the methodology of denotational semantics to  the much broader forms of computational processes we need to design, understand and analyze today? How are we to maintain clean algebraic structure and abstraction alongside the operational nature of computation?  This talk will describe a way forward.  It proposes a computational interpretation of  the mathematics needed via causal models such as event structures and Petri nets, but with a vital new ingredient, a formal treatment of symmetry.  The surprise is not  that symmetry is important but that it is the key to so much.  Results will be presented showing that the introduction of symmetry in event structures leads to greater expressivity w.r.t.

I. Objects/types and processes: through a representation of all presheaves over a category of finite partial orders by event structures with symmetry; constructions that previously only existed on the presheaves now carry an operational representation via event structures.

II. Maps/simulations: through Kleisli maps of monads, which only exist as monads up to symmetry; the monads adjust the notion of event, including atomicity, providing a systematic way to vary maps between event structures.

III. Relations/interacting processes: through the denotation of processes as general spans, with examples ranging through nondeterministic dataflow, higher-order synchronizing processes and sequential algorithms.

Causal models are being used across a range of areas:  distributed algorithms, e.g. in fault diagnosis, analysis of trust, and security; systems biology, in the analysis of biochemical pathways; physics, as causal sets;  hardware, in self-timed circuits; types and proofs; nondeterministic dataflow; partial-order model checking; program logic, in models of concurrent separation logic.  They have often been discovered and developed independently in separate fields.  The talk will conclude with an indication of how results point to a comprehensive theory of event-based computation and begin to impinge on applications.