Scientific Series

There are two notions that play a central role in the mathematical theory of computation. One is that of a computable problem, i.e., of a problem that can, in principle, be solved by an (idealized) computer. It is known that there exist problems that \'have answers\', but for which those answers are not computable. The other is that of the difficulty of a computation, i.e. of the number of (idealized) steps required actually to carry out that computation. It is known that, given any appropriate \'degree of difficulty\', there exists a problem that, while computable, is at least that difficult. These two notions, while purely mathematical, are designed to reflect, in some broad sense, the physics of the computation process. But there are indications that physics may have something further to say about them. Indeed, it has been suggested that, by using general relativity, some problems that are (mathematically) non-computable may become computable; and that, by using quantum mechanics, some problems that are (mathematically) difficult may become less so. Are there, in principle, any limitations on what physics can do for us in this area?

Coin flipping by telephone (Blum \'81) is one of the most basic cryptographic tasks of two-party secure computation. In a quantum setting, it is possible to realize (weak) coin flipping with information theoretic security. Quantum coin flipping has been a longstanding open problem, and its solution uses an innovative formalism developed by Alexei Kitaev for mapping quantum games into convex optimization problems. The optimizations are carried out over duals to the cone of operator monotone functions, though the mapped problem can also be described in a very simple language that involves moving points in the plane. Time permitting, I will discuss both Kitaev\'s formalism, and the solution that leads to quantum weak coin flipping with arbitrarily small bias.

At a very basic level, physics is about what we can say about propositions like \'A has a value in S\' (or \'A is in S\' for short), where A is some physical quantity like energy, position, momentum etc. of a physical system, and S is some subset of the real line. In classical physics, given a state of the system, every proposition of the form \'A is in S\' is either true or false, and thus classical physics is realist in the sense that there is a \'way things are\'. In contrast to that, quantum theory only delivers a probability of \'A is in S\' being true. The usual instrumentalist interpretation of the formalism leading to these probabilities involves an external observer, measurements etc.In a future theory of quantum gravity/cosmology, we will have to treat the whole universe as a quantum system, which renders instrumentalism meaningless, since there is no external observer. Moreover, space-time presumably does not have a smooth continuum structure at small scales, and possibly physical quantities will take their values in some other mathematical structure than the real numbers, which are the \'mathematical continuum\'. In my talk, I will show how the use of topos theory, which is a branch of category theory, may help to formulate physical theories in a way that (a) is neo-realist in the sense that all propositions \'A is in S\' do have truth values and (b) does not depend fundamentally on the continuum in the form of the real numbers. After introducing topoi and their internal logic, I will identify suitable topoi for classical and quantum physics and show which structures within these topoi are of physical significance. This is still very far from a theory of quantum gravity, but it can already shed some light on ordinary quantum theory, since we avoid the usual instrumentalism. Moreover, the formalism is general enough to allow for major generalisations. I will conclude with some more general remarks on related developments.

Two spinning black holes emit gravitational waves as they orbit, and eventually merge to form a single black hole. How do the properties of the final black hole depend on those of the initial black holes? This is a classic problem in general relativity, with implications for astrophysics, cosmology, and gravitational wave detection. I will describe the rapid numerical and theoretical progress over the past two years, and discuss some open questions and future directions.

The most remarkable recent discovery in fundamental physics is that the Universe is undergoing accelerated expansion. A proper understanding of its physical origin forces us to make a hard choice between dynamical and environmental scenarios. The former approach predicts the existence of a new long distance physics in the gravitational sector, while the second relies on the vast landscape of vacua with different values of the cosmological constant. I will discuss achievements and shortcomings of both approaches, and illustrate them in the concrete examples.

Decoherence attempts to explain the emergent classical behaviour of a quantum system interacting with its quantum environment. In order to formalize this mechanism we introduce the idea that the information preserved in an open quantum evolution (or channel) can be characterized in terms of observables of the initial system. We use this approach to show that information which is broadcast into many parts of the environment can be encoded in a single observable. This supports a model of decoherence where the pointer observable can be an arbitrary positive operator-valued measure (POVM). This generalization makes it possible to characterize the emergence of a realistic classical phase-space. In addition, this model clarifies the relations among the information preserved in the system, the information flowing from the system to the environment (measurement), and the establishment of correlations between the system and the environment.

It is common to assert that the discovery of quantum theory overthrew our classical conception of nature. But what, precisely, was overthrown? Providing a rigorous answer to this question is of practical concern, as it helps to identify quantum technologies that outperform their classical counterparts, and of significance for modern physics, where progress may be slowed by poor physical intuitions and where the ability to apply quantum theory in a new realm or to move beyond quantum theory necessitates a deep understanding of the principles upon which it is based. In this talk, I demonstrate that a large part of quantum theory can be obtained from a single innovation relative to classical theories, namely, that there is a fundamental restriction on the sorts of statistical distributions over classical states that can be prepared. This restriction implies a fundamental limit on the amount of knowledge that any observer can have about the classical state. I will also discuss the quantum phenomena that are not captured by this principle, and I will end with a few speculations on what conceptual innovations might underlie the latter set and what might be the origin of the statistical restriction.

We prove that all non-conspiratorial/retro-causal hidden variable theories has to be measurement ordering contextual, i.e. there exists *commuting* operator pair (A,B) and a hidden state \\\\lambda such that the outcome of A depends on whether we measure B before or after. Interestingly this rules out a recent proposal for a psi-epistemic due to Barrett, Hardy, and Spekkens. We also show that the model was in fact partly discovered already by vanFraassen 1973; the only thing missing was giving a probability distribution on the space of ontic states (the hidden variables).

Cosmological observations will soon distinguish between the standard slow roll inflationary paradigm and some of its recently developed alternatives. Driven by developments in string theory, many new models include features such as non-minimal kinetic terms, leading to large non-gaussianities, making them observationally testable in the CMB. Models of slow roll inflation can also give rise to large non- gaussianities if the initial inflationary state was sufficiently excited, with a shape dependence that will be clearly distinguishable. I will review these different possibilities and discuss how they provide new theoretical challenges in understanding the initial conditions problem and the global structure of the inflationary universe.