This paper argues that the requirement of applicableness of quantum linearity to any physical level from molecules and atoms to the level of macroscopic extensional world, which leads to a main foundational problem in quantum theory referred to as the "measurement problem", actually has a computational character: It implies that there is a generic algorithm, which guarantees exact solutions to the Schr ödinger equation for every physical system in a reasonable amount of time regardless of how many constituent microscopic particles it comprises.From the point of view of computational complexity theory, this requirement is equivalent to the assumption that the computational complexity classes P and NP are equal, which is widely believed to be very unlikely.As demonstrated in the paper, accepting the different computational assumption called the Exponential Time Hypothesis (that involves P =NP) would justify the separation between a microscopic quantum system and a macroscopic apparatus (usually called the Heisenberg cut) since this hypothesis, if true, would imply that deterministic quantum and classical descriptions are impossible to overlap in order to obtain a rigorous derivation of complete properties of macroscopic objects from their microstates.
This paper argues that the requirement of applicableness of quantum linearity to any physical level from molecules and atoms to the level of macroscopic extensional world, which leads to a main foundational problem in quantum theory referred to as the "measurement problem", actually has a computational character: It implies that there is a generic algorithm, which guarantees exact solutions to the Schr ödinger equation for every physical system in a reasonable amount of time regardless of how many constituent microscopic particles it comprises.From the point of view of computational complexity theory, this requirement is equivalent to the assumption that the computational complexity classes P and NP are equal, which is widely believed to be very unlikely.As demonstrated in the paper, accepting the different computational assumption called the Exponential Time Hypothesis (that involves P =NP) would justify the separation between a microscopic quantum system and a macroscopic apparatus (usually called the Heisenberg cut) since this hypothesis, if true, would imply that deterministic quantum and classical descriptions are impossible to overlap in order to obtain a rigorous derivation of complete properties of macroscopic objects from their microstates.
It is argued that any possible definition of a realistic physics theory – i.e., a mathematical model representing the real world – cannot be considered comprehensive unless it is supplemented with requirement of being computationally realistic. That is, the mathematical structure of a realistic model of a physical system must allow the collection of all the system's physical quantities to compute all possible measurement outcomes on some computational device not only in an unambiguous way but also in a reasonable amount of time. In the paper, it is shown that a deterministic quantum model of a microscopic system evolving in isolation should be regarded as realistic since the NP-hard problem of finding the exact solution to the Schrödinger equation for an arbitrary physical system can be surely solved in a reasonable amount of time in the case, in which the system has just a small number of degrees of freedom. In contrast to this, the deterministic quantum model of a truly macroscopic object ought to be considered as non-realistic since in a world of limited computational resources the intractable problem possessing that enormous amount of degrees of freedom would be the same as mere unsolvable.
Abstract. Is the universe computable? If yes, is it computationally a polynomial place? In standard quantum mechanics, which permits infinite parallelism and the infinitely precise specification of states, a negative answer to both questions is not ruled out. On the other hand, empirical evidence suggests that NP-complete problems are intractable in the physical world. Likewise, computational problems known to be algorithmically uncomputable do not seem to be computable by any physical algorithms on the one hand, and physical computers on the other, finds a natural explanation if the universe is assumed to be algorithmic; that is, that physical reality is the product of discrete subphysical information processing equivalent to the actions of a probabilistic Turing machine. This assumption can be reconciled with the observed exponentiality of quantum systems at microscopic scales, and the consequent possibility of implementing Shor's quantum polynomial time algorithm at that scale, provided the degree of superposition is intrinsically, finitely upper-bounded. If this bound is associated with the quantum-classical divide (the Heisenberg cut), a natural resolution to the quantum measurement problem arises. From this viewpoint, macroscopic classicality is an evidence that the universe is in BPP, and both questions raised above receive affirmative answers. A recently proposed computational model of quantum measurement, which relates the Heisenberg cut to the discreteness of Hilbert space, is briefly discussed. A connection to quantum gravity is noted. Our results are compatible with the philosophy that mathematical truths are independent of the laws of physics.
Is the universe computable? If yes, is it computationally a polynomial place? In standard quantum mechanics, which permits infinite parallelism and the infinitely precise specification of states, a negative answer to both questions is not ruled out. On the other hand, empirical evidence suggests that NP‐complete problems are intractable in the physical world. Likewise, computational problems known to be algorithmically uncomputable do not seem to be computable by any physical means. We suggest that this close correspondence between the efficiency and power of abstract algorithms on the one hand, and physical computers on the other, finds a natural explanation if the universe is assumed to be algorithmic; that is, that physical reality is the product of discrete sub‐physical information processing equivalent to the actions of a probabilistic Turing machine. This assumption can be reconciled with the observed exponentiality of quantum systems at microscopic scales, and the consequent possibility of implementing Shor’s quantum polynomial time algorithm at that scale, provided the degree of superposition is intrinsically, finitely upper‐bounded. If this bound is associated with the quantum‐classical divide (the Heisenberg cut), a natural resolution to the quantum measurement problem arises. From this viewpoint, macroscopic classicality is an evidence that the universe is in BPP, and both questions raised above receive affirmative answers. A recently proposed computational model of quantum measurement, which relates the Heisenberg cut to the discreteness of Hilbert space, is briefly discussed. A connection to quantum gravity is noted. Our results are compatible with the philosophy that mathematical truths are independent of the laws of physics.
In the well known Copenhagen interpretation of Quantum mechanics, advocated by N. Bohr, the physical objects and the experimental results can be described only in a macroscopic language, leaving any possible microscopic description as unspeakable. This point of view has been deepened by C. Rovelli in the relational interpretation of Quantum mechanics. Most of the alternative interpretations, which try a detailed microscopic description of physical phenomena and of their evolution, have in common the explicit introduction of the wave function as the basic element of the theory. These interpretations require the notion of quantum state as the fundamental concept of the theory, which is the typical unspeakable physical element according to the Copenhagen interpretation. The two basic physical entities are intimately bound together by the integrity of the wave function. These interpretations are usually indicated as realistic. It is well known that the use of the wave function and its time evolution in the description of the physical processes leads unavoidably to some difficulties or so-called paradoxes. The measurement problem is at the center of these difficulties, mainly because it requires the introduction of the reduction process of the wave function, which is not included explicitly within the mathematical formalism of Quantum Mechanics. In this paper we build up and propose a model which goes beyond the standard formalism and which is able to solve the measurement problem and all the other difficulties which, in a way or in another, are related to it.
The macro-objectivation problem derives from the fact that the Schrodinger equation is linear and thus requires that a macroscopic system interacting with an entangled state must be entangled as well. However, such a requirement entails that the Schrodinger equation must also be solvable in the macroscopic world in the same way as it is solvable in the microscopic world, which itself is an assumption. In this work, the alternative assumption that the Schrodinger equation is in general an intractable problem is considered.
Quantum computing promises computational performance that is exponentially faster than any conceivable classical computer. This is due to the theoretically expected scaling of N entangled qubits, with parallel evolution of 2^N quantum states. This is in sharp contrast to classical computing, where N bits may have 2^N classical states, but only one at a time. It is widely believed that quantum superposition and entanglement have been demonstrated in several experimental systems, and that practical quantum computing can be achieved once sufficiently long quantum relaxation times are obtained. On the contrary, we suggest that there may be serious problems with quantum computing on both the macroscopic and microscopic levels, and that the experiments thus far have not proven the existence of non-classical superposition states, which are necessary for the proper functioning of qubits. In order to investigate this further, we propose new experiments in three physical systems: electron spins, single photons, and superconducting loops. We further suggest that certain more limited classes of quantum computing, such as quantum annealing, do not require quantum entanglement, and can achieve significant performance enhancements even if universal quantum computing proves to be impossible.