From Algorithms and Information to Physics -- and Back

Ferdinand Gonseth has been quoted “La logique est tout d’abord une science naturelle - Logic is, first of all, a natural science.” This is in remarkable contrast with John Wheeler’s famous slogan “It from Bit.” The tension inherent in this pair of ideas and styles of thought originates from whether information or logic should be considered as more or less fundamental than physical laws. The difference can sometimes be used to obtain new insight: Landauer’s reading, in his Gonseth-like spirit “Information is Physical,” of the second law of thermodynamics is that erasure of information or, more generally, any logical irreversibility of a transformation, must be compensated in the environment in the form of heat dissipation (of the free energy required for carrying out the process). If, in turn, one regards the environment as a computation - this now in the spirit of the Church-Turing thesis, a popular computer-science reading of the “it-from-bit” theme -, then the compensation in this environment must be such that the global computation is logically reversible. In this view, the second law becomes a property of a computation: No information ever gets lost; nature computes with Toffoli-, not AND gates. In the described spirit, the proposed project lies at the intersection between physics - mostly quantum theory, but also thermodynamics and relativity - and computation as well as information theory. We have subdivided it into four subprojects (SP) investigating different aspects of the relationship.

SP 1: Quantum Non-Locality, Contextuality, and their Applications. This part of the project is devoted to phenomena of quantum theory that are fascinating specifically when viewed through the glasses of information theory: non-locality and contextuality. Both have demonstrated the insufficiency of classical paradigms in the face of quantum theory. The focus of this rich field of research has in recent years been broadened by the applicant through replacing probability distributions by Kolmogorov complexity; this has inspired a number of researchers. We plan to deepen this study and extend it from Bell’s also to Kochen and Specker’s theorem. Particularly interesting is the phenomenas’ applicability for a randomness and cryptographic confidentiality calculus we aim at further developing.

SP 2: Computational and Communication Prospects from Relaxed Causality. The mysterious origin of non-local correlations in a causal structure has served as a motivation for questioning and relaxing that very structure while maintaining logical consistency. Such an approach has been initiated by researchers in Vienna and pursued by the applicant together with one of his former collaborators in the frame of the predecessor of the proposed project. For instance, we have investigated the possibility of increased computational power of circuits allowed to contain loops as long as logical consistency is maintained: Then, the cryptographically important problem of integer factoring becomes efficiently solvable - just like for a quantum computer. The exact computational power of such circuits remains unclear, and we plan to investigate it in this subproject.

SP 3: Thermodynamics from an Algorithmic Viewpoint. There are close connections between information theory and thermodynamics. We aim at investigating them in depth with the goal of understanding thermodynamic concepts such as macrostates, work value, or entropy in a non-contextual, objective way through the above-mentioned Kolmogorov-complexity measures and the Kolmogorov structure function. Through a physical understanding of classicality of information in terms of macroscopicity and work value (redundancy), we aim at shedding more light on the quantum measurement problem, i.e., the transition from quantum to classical information: What Gedankenexperimente could decide between different “interpretations of quantum theory”?

SP 4: Device-Independent and Post-Quantum Cryptography. The connection between quantum theory on the one hand and cryptography on the other is intimate and (at least) two-fold: Whereas traditional schemes get broken by a quantum computer, quantum physics offers new possibilities such as quantum cryptography. The goal of this subproject is to deepen the knowledge on these connections, e.g., on practical efficient device-independent key agreement from non-local correlations. We also aim at studying traditional information-theoretic cryptography in the Kolmogorov-complexity framework, as well as “post-quantum cryptography,” i.e., schemes resisting an adversary having access to a quantum computer. We have a vivid collaboration on this topic with IBM Research that we plan to intensify.