KGRC Mini-Workshop

On Wednesday, July 12 and 13, 2011, the KGRC hosts an informal workshop.

Program

Tuesday, July 12

Wednesday, July 13

Abstracts

Bob Coecke "The logic of quantum mechanics, Take II"
This is a tale about quantum computing and a bit of natural language processing, ... all in pictures!
It is now exactly 75 years ago that John von Neumann denounced his own Hilbert space formalism: "I would like to make a confession which may seem immoral: I do not believe absolutely in Hilbert space no more." (sic) [1]
His reason was that Hilbert space does not elucidate in any direct manner the key quantum behaviors. Together with Birkhoff he crafted quantum logic, ... a failed research program.
So what are these key quantum behaviors then? [2, 3] For Schrodinger this is the behavior of compound quantum systems, described by the tensor product [4, again 75 years ago]. While the quantum information endeavor is to a great extend the result of exploiting this important insight, the language of the field is still very much that of strings of complex numbers, which is akin to the strings of 0's and 1's in the early days of computer programming. If the manner in which we describe compound quantum systems captures so much of the essence of quantum theory, then it should be at the forefront of the presentation of the theory, and not preceded by continuum structure, field of complex numbers, vector space over the latter, etc, to only then pop up as some secondary construct.
Over the past couple of years we have played the following game: how much quantum phenomena can be derived from `compoundness + epsilon'. It turned out that epsilon can be taken to be `very little', surely not involving anything like continuum, fields, vector spaces, but merely a `two-dimensional space' of temporal composition (cf `and then') and compoundness (cf 'while'), together with some very natural purely operational assertion, including one which in a constructive manner asserts entanglement; among many other things, trace structure (cf von Neumann above) then follow [5, survey]. This `categorical quantum mechanics' research program started with [6].In a very short time, this radically different approach has produced a universal graphical language for quantum theory which helped to resolve some open problems [7,8,9], in quantum foundations, measurement based quantum computing, and on the structure of multi-partite entanglement. It gives a particularly elegant account on complementarity and the quantum classical interaction [10, 11]. It also paved the way to automate quantum reasoning, by means of the Quantomatic software [12].
The approach has even helped to solve problems outside physics, most notably in modeling meaning for natural languages which was the first elegant mathematical solution to this problem [13, 14]. Both the automation and the support of structures in natural language justifies the label of "Logic" (as opposed to Birkhoff and von Neumann's quantum logic).
    [1] M Redei (1997) Why John von Neumann did not like the Hilbert space formalism of quantum
         mechanics (and what he liked instead). Stud Hist Phil Mod Phys 27, 493-510.
    [2] For von Neumann, initially these were the propositions that one could measure with certainty, an
         idea that he later abandoned in favor of the trace structure, which generates probability [1].
    [3] Still, today for most physicists quantum is synonym for Hilbert space, which of course is not
         unrelated to the dominant "shut up and calculates"-interpretation of quantum theory.
    [4] E Schroedinger, (1935) Discussion of probability relations between separated systems. Proc Camb
         Phil Soc 31, 555-563; (1936) 32, 446-451.
    [5] B Coecke (2010) Quantum picturalism. Cont Phys 51, 59-83. arXiv:0908.1787
    [6] S Abramsky & B Coecke (2004) A categorical semantics of quantum protocols. LiCS '04.
         arXiv:0808.1023
    [7] B Coecke, B Edwards and RW Spekkens (2010) Phase groups and the origin of non-locality for qubits.
         ENTCS, to appear. arXiv:1003.5005
    [8] R Duncan and S Perdrix (2010) Rewriting measurement-based quantum computations with
         generalised flow. ICALP'10.
    [9] B Coecke and A Kissinger (2010) The compositional structure of multipartite quantum entanglement.
         ICALP'10. arXiv:1002.2540
    [10] B Coecke and R Duncan (2008) Interacting quantum observables. ICALP'08. arXiv:0906.4725
    [11] B Coecke and S Perdrix (2010) Environment and classical channels in categorical quantum
           mechanics. CSL'10. arXiv:1004.1598
    [12] L Dixon, R Duncan & A Kissinger. dream.inf.ed.ac.uk/projects/quantomatic/
    [13] B Coecke, S Clark & M Sadrzadeh (2010) Ling Anal 36. Mathematical foundations for a compositional
           distributional model of meaning. arXiv:1003.4394
    [14] New Scientist: Quantum links let computers understand language, 8 December 2010.

Cameron Freer "Invariant measures on countable structures"
The Erdős-Rényi random graph construction can be seen as inducing a probability measure concentrated on the Rado graph (sometimes known as the countable "random graph") that is invariant under arbitrary permutations of the underlying set of vertices. A natural question to ask is: For which other countable combinatorial structures does such an invariant measure exist? Until recent work of Petrov and Vershik (2010), the answer was not known even for Henson's countable ultrahomogeneous-universal triangle-free graph. In this talk we will provide a characterization of countable structures that admit invariant measures, in terms of the notion of definable closure. This leads to new examples and non-examples, including a complete list of ultrahomogeneous graphs satisfying our criterion, as well as certain directed graphs and partial orders. Joint work with Nathanael Ackerman and Rehana Patel.

Philip Welch "Operators and Determinacy"
We look at levels of determinacy for Gale-Stewart games provable within second order number theory, and their connections to quasi-inductuve operators - a form of operator extending those of monotone induction.