Search Talks

Algorithmic information theory (AIT) delivers an objective quantification of simplicity-qua-compressibility,that was employed by Solomonoff (1964) to specify a gold standard of inductive inference. Or so runs the conventional account,that I will challenge in my talk.

In this talk we describe a general procedure for associating a minimal informationally-complete quantum measurement (or MIC) with a probabilistic representation of quantum theory. Towards this, we make use of the idea that the Born Rule is a consistency criterion among subjectively assigned probabilities rather than a tool to set purely physically mandated probabilities. In our setting, the difference between quantum theory and classical statistical physics is the way their physical assumptions augment bare probability theory: Classical statistical physics corresponds to a trivial augmentation, while quantum theory makes crucial use of the Born Rule. We prove that the representation of the Born Rule obtained from a symmetric informationally-complete measurement (or SIC) minimizes the distinction between the two theories in at least two senses, one functional, the other geometric. Our results suggest that this representation supplies a natural vantage point from which to identify their essential differences, and, perhaps thereby, a set of physical postulates reflecting the quantum nature of the world.

In his famous thought experiment, Wigner assigns an entangled state to the composite quantum system made up of Wigner's friend and her observed system. While the two of them have different accounts of the process, each Wigner and his friend can in principle verify his/her respective state assignments by performing an appropriate measurement. As manifested through a click in a detector or a specific position of the pointer, the outcomes of these measurements can be regarded as reflecting directly observable "facts". Reviewing arXiv:1507.05255, I will derive a no-go theorem for observer-independent facts, which would be common both for Wigner and the friend. I will then analyze this result in the context of a newly derived theorem in arXiv:1604.07422, where Frauchiger and Renner prove that "single-world interpretations of quantum theory cannot be self-consistent". It is argued that "self-consistency" has the same implications as the assumption that observational statements of different observers can be compared in a single (and hence an observer-independent) theoretical framework. The latter, however, may not be possible, if the statements are to be understood as relational in the sense that their determinacy is relative to an observer.

A central fact in computer science is that there are universal machines, that is machines that can run any other program. Recently, a somewhat similar notion of universality has been discovered in physics, by which some spin models can simulate all other models. In this work we shed light on the relation between the two concepts of universality

Following Stefan Wolf’s talk, we address the doubts expressed on fundamental space-time causality. Usually it is assumed that causal structures represent a definite partial ordering of events. By relaxing that notion one risks problems of logical nature. Yet, as we show, there exists a logically consistent world beyond the causal, even in the classical realm where quantum theory is not invoked. We explore the classical correlations within and the computational limits of that world. It turns out that relaxing causality in that fashion does not allow for efficient computation of NP-hard problems. These results are related to closed time-like curves: Contrary to previous models of time travel, which necessitate quantum theory and violate the NP-hardness assumption, we obtain a computationally tame model for classical and reversible time travel where freedom of choice is unrestricted.

Landauer's principle claims that "Information is Physical." Its conceptual antipode, Wheeler's "It from Bit," has since long been popular among computer scientists in the form of the Church-Turing hypothesis: All natural processes can be simulated by a universal Turing machine. Switching back and forth between the two paradigms, motivated by quantum-physical Bell correlations and the doubts they raise about fundamental space-time causality, we look for an intrinsic, physical randomness notion and find one, namely complexity, around the second law of thermodynamics. Bell correlations combined with Kolmogorov complexity in the role of randomness imply an all-or-nothing nature of the Church-Turing hypothesis: Either beyond-Turing computations are physically impossible, or they can be carried out by "devices" as simple as individual photons. This latter result demonstrates in an exemplary way the fruitful interplay between physical and informational-computational principles.

An important ingredient of the scientific method is the ability to test alternative hypotheses on the causal relations relating a given set of variables. In the classical world, this task can be achieved with a variety of statistical, information-theoretic, and computational techniques. In this talk I will address the extension from the classical scenario to the quantum scenario, and, more generally, to general probabilistic theories. After introducing the basic hypothesis testing framework, I will focus on a concrete example, where the task is to identify the causal intermediary of a given variable, under the promise that the causal intermediary belongs to a given set of candidate variables. In this problem, I will show that quantum physics offers an exponential advantage over the best classical strategies, with a doubling of the exponential decay of the error probability. The source of the advantage can be found in the combination of two quantum features: the complementarity between the information on the causal structure and other properties of the cause effect relation, and the ability to perform multiple tests in a quantum superposition. An interesting possibility is that one of the "hidden principles" of quantum theory could be on our ability to test alternative causal hypotheses.