This paper is a commentary on the foundational significance of the Clifton-Bub-Halvorson theorem characterizing quantum theory in terms of three information-theoretic constraints (Foundations of Physics 33, 1561-1591 (2003); quant-ph/0211089). I argue that: (1) a quantum theory is best understood as a theory about the possibilities and impossibilities of information transfer, as opposed to a theory about the mechanics of nonclassical waves or particles, (2) given the information-theoretic constraints, any mechanical theory of quantum phenomena that includes an account of the measuring instruments that reveal these phenomena must be empirically equivalent to a quantum theory, and (3) assuming the information-theoretic constraints are in fact satisfied in our world, no mechanical theory of quantum phenomena that includes an account of measurement interactions can be acceptable, and the appropriate aim of physics at the fundamental level then becomes the representation and manipulation of information.
Does information play a significant role in the foundations of physics? We investigate whether information-theoretic constraints characterize quantum theory. In a C*-algebraic framework, this is known to hold via three equivalences: no broadcasting and noncommutativity; no bit commitment and nonlocality; no signalling and kinematic independence. But this complex linear framework could be said to build in quantum theory from the start. We show that the first two equivalences break, and the third holds, in a framework of generalized, possibly nonlinear, C*-algebras. This uncovers a hierarchy of notions of when (quantum) information is classical.
Deriving formulations to estimate worst-case size bounds for conjunctive queries under various constraints has been at the core of theoretical database research. If the problem has no constraints or has a single functional dependency, tight worst-case size bounds are computable. If the problem has more than one functional dependency, computing tight bounds can be difficult in practice and may even require an infinite number of linear inequalities in its optimization formulation. While these challenges have been addressed with varying methods, no prior research has employed quantum information theory to address this problem. In this work, we establish a connection between earlier classical information theory-based works and quantum information theory. We propose replacing the classical Shannon entropy formulation with the quantum Rényi entropy of order
α∈(0,1) whose entropy cone is characterized simply by non-negativity. The first key result is to express the bound in terms of optimizing over quantum states and Rényi entropy. Optimizing with respect to quantum states rather than classical distributions transfers the hardness into the problem of characterizing classical states, yielding a sound but generally not tight upper bound. We further quantify this hardness explicitly by proposing a dichotomy theorem: if the query satisfies a head absorption rule, then the Rényi program value is at most one and
∣Q(D)∣≤rmax(D). Otherwise, the program is unbounded.