Search Talks

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.

I discuss how we might go about about performing a Bell experiment in which humans are used to decide the settings at each end. To get a sufficiently high rate of switching at both ends, I suggest an experiment over a distance of about 100km with 100 people at each end wearing EEG headsets, with the signals from these headsets being used to switch the settings. The radical possibility we wish to investigate is that, when humans are used to decide the settings (rather than various types of random number generators), we might then expect to see a violation of Quantum Theory in agreement with the relevant Bell inequality. Such a result, while very unlikely, would be tremendously significant for our understanding of the world (and I will discuss some interpretations). Possible radical implications aside, performing an experiment like this would push the development of new technologies. The biggest problem would be to get sufficiently high rates wherein there has been a human induced switch at each end before a signal as to the new value of the setting could be communicated to the other end and, at the same time, a photon pair is detected. It looks like an experiment like this, while challenging, is just about feasible with current technologies.

Microcanonical thermodynamics studies the operations that can be performed on systems with well-defined energy. So far, this approach has been applied to classical and quantum systems. Here we extend it to arbitrary physical theories, proposing two requirements for the development of a general microcanonical framework. We then formulate three resource theories, corresponding to three different choices of basic operations. We focus on a class of physical theories, called sharp theories with purification, where these three sets of operations exhibit remarkable properties. In these theories, a necessary condition for thermodynamic transitions is given by a suitable majorisation criterion. This becomes a sufficient condition in all three resource theories if and only if the dynamics allowed by the theory satisfy a condition that we call "unrestricted reversibility". Under this condition, we derive a duality between the resource theory of microcanonical thermodynamics and the resource theory of pure bipartite entanglement.

Dividing the world into subsystems is an important component of the scientific method. The choice of subsystems, however, is not defined a priori. Typically, it is dictated by our experimental capabilities, and, in general, different agents may have different capabilities. Here we propose a construction that associates every agent with a subsystem, equipped with its set of states and its set of transformations. In quantum theory, this construction accommodates the traditional notion of subsystems as factors of a tensor product, as well as the notion of classical subsystems of quantum systems. We then restrict our attention to systems where all physical transformations act invertibly. For such systems, the future states are a faithful encoding of the past states, in agreement with a requirement known as the Conservation of Information. For systems satisfying the Conservation of Information, we propose a dynamical definition of pure states, and show that all the states of all subsystems admit a canonical purification. This result extends the purification principle to a broader setting, in which coherent superpositions can be interpreted as purifications of incoherent mixtures. As an example, we illustrate the general construction for subsystems associated with group representations.