We investigate what it means to apply the solution, proposed to the firewall paradox by Harlow and Hayden, to the famous quantum paradoxes of Schödinger's Cat and Wigner's Friend if ones views these as posing a thermodynamic decoding problem (as does Hawking radiation in the firewall paradox). The implications might point to a relevance of the firewall paradox for the axiomatic and set theoretic foundations underlying mathematics. We reconsider in this context the results of Benioff on the foundational challenges posed by the randomness postulate of quantum theory. A central point in our discussion is that one can mathematically not naturally distinguish between computational complexity (as central to the approach of Harlow and Hayden and further developed by Susskind) and proof theoretic complexity (since they represent the same concept on a Turing machine), with the latter being related to a finite bound on Kolmogorov entropy (due to Chaitin incompleteness).
We investigate what it means to apply the solution, proposed to the firewall paradox by Harlow and Hayden, to the famous quantum paradoxes of Schödinger's Cat and Wigner's Friend if ones views these as posing a thermodynamic decoding problem (as does Hawking radiation in the firewall paradox). The implications might point to a relevance of the firewall paradox for the axiomatic and set theoretic foundations underlying mathematics. We reconsider in this context the results of Benioff on the foundational challenges posed by the randomness postulate of quantum theory. A central point in our discussion is that one can mathematically not naturally distinguish between computational complexity (as central to the approach of Harlow and Hayden and further developed by Susskind) and proof theoretic complexity (since they represent the same concept on a Turing machine), with the latter being related to a finite bound on Kolmogorov entropy (due to Chaitin incompleteness).
This article analyses the firewall paradox (wall‑of‑fire paradox, AMPS) — one of the most discussed challenges to modern quantum gravity. The paradox arises from an apparent contradiction between three postulates: the unitarity of quantum mechanics, the semiclassical description of Hawking radiation, and Einstein’s equivalence principle. Proponents of “informational language” argue that to save information, one must abandon the equivalence principle and accept the existence of a high‑energy “firewall” at the event horizon of a collapsar. It is shown that the firewall paradox is a problem of “informational language” , not a physical contradiction. The paradox is rooted in the conflation of the three senses of “information” (configuration, observer’s knowledge, pseudosubstance) introduced in Article 1. When reformulated in physical language (configuration, quantum correlations, unitary evolution), the need for a “firewall” disappears. Monogamy of entanglement is a property of quantum correlations, not an “informational principle”. The change in correlation structure after Page time is a technical problem, not a fundamental contradiction. Alternative approaches (Susskind’s complementarity) that do not require a firewall are considered. Responses to possible objections are given. The reformulation preserves the equivalence principle, eliminates the pseudo‑paradox, and turns the problem into a technical description of quantum correlations. The article is the seventh in the series “Reformulating Key Concepts of Physics Without Informational Language”. Keywords: firewall paradox, wall of fire, AMPS, collapsar, information, quantum correlations, monogamy of entanglement.
Despite its remarkable empirical success and predictive power, quantum theory is riddled with mysteries. One such conceptual puzzle is the measurement problem: why do quantum systems in superposition collapse to a single-valued outcome upon being measured? The scenario of Wigner's friend illustrates this tension, with recent extensions deriving strong no-go results for the nature of reality. Another fundamental puzzle arises at the interface of quantum theory and general relativity---the black hole information paradox. This thesis further explores these two foundational paradoxes. Part I of this thesis focuses on extensions of the Wigner's friend scenario. We introduce several novel extended Wigner's friend arguments, and establish connections with notions of nonclassicality, i.e. the study of quantum phenomena that evade classical explanation. Key results are a refined version of the Frauchiger--Renner paradox, new extended Wigner's friend scenarios based on contextuality, and an argument against the absoluteness of free choices based on the Pusey--Barrett--Rudolph theorem. The latter result complements the Local Friendliness no-go theorem, which challenged the absoluteness of experimentally obtained measurement outcomes. In Part II of this thesis, we turn to black hole puzzles and the interplay of quantum theory and gravity. We present a paradox that unifies extended Wigner's friend arguments with black hole puzzles, strengthening the cloning and firewall paradoxes. After discussing subtleties in these paradoxes, we next present an analysis combining elements of quantum theory with gravity, analyzing the detector response near a superposed black hole using elements of quantum reference frames.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
A bstract We reconsider the black hole firewall puzzle, emphasizing that quantum error- correction, computational complexity, and pseudorandomness are crucial concepts for understanding the black hole interior. We assume that the Hawking radiation emitted by an old black hole is pseudorandom, meaning that it cannot be distinguished from a perfectly thermal state by any efficient quantum computation acting on the radiation alone. We then infer the existence of a subspace of the radiation system which we interpret as an encoding of the black hole interior. This encoded interior is entangled with the late outgoing Hawking quanta emitted by the old black hole, and is inaccessible to computationally bounded observers who are outside the black hole. Specifically, efficient operations acting on the radiation, those with quantum computational complexity polynomial in the entropy of the remaining black hole, commute with a complete set of logical operators acting on the encoded interior, up to corrections which are exponentially small in the entropy. Thus, under our pseudorandomness assumption, the black hole interior is well protected from exterior observers as long as the remaining black hole is macroscopic. On the other hand, if the radiation is not pseudorandom, an exterior observer may be able to create a firewall by applying a polynomial-time quantum computation to the radiation.
Abstract We argue that there is a simple, unique, reason for all quantum paradoxes, and that such a reason is not uniquely related to quantum theory. It is rather a mathematical question that arises at the intersection of logic, probability, and computation. We give our ‘weirdness theorem’ that characterises the conditions under which the weirdness will show up. It shows that whenever logic has bounds due to the algorithmic nature of its tasks, then weirdness arises in the special form of negative probabilities or non-classical evaluation functionals. Weirdness is not logical inconsistency, however. It is only the expression of the clash between an unbounded and a bounded view of computation in logic. We discuss the implication of these results for quantum mechanics, arguing in particular that its interpretation should ultimately be computational rather than exclusively physical. We develop in addition a probabilistic theory in the real numbers that exhibits the phenomenon of entanglement, thus concretely showing that the latter is not specific to quantum mechanics.