Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.20927

Unobservables and Decoherence from Complexity

Michael Epping, Jochen Szangolies

quant-phcs.CCSubmitted Jun 18, 2026• Announced Jun 22, 2026• 0 citations
arXivHTMLPDF

Abstract

The interface between the quantum and the classical is an intriguing and, at times, hotly contested subject of ongoing research. The quantum regime is characterized by interference, made possible by the superposition principle, while such phenomena are absent in macroscopic, everyday experience. Here, we investigate the link of this absence (or, as we will argue, unobservability) to computational complexity. We show how the assumption that quantum systems cannot solve NP-complete problems efficiently implies that certain formally valid quantum measurements on finite-dimensional systems are unperformable. We study several consequences of this restriction. First, Pauli matrices in an inconveniently transformed basis are a simple example of unobservables. Furthermore, some quantum states are not connected by any physically realizable time evolution. Finally there are quantum states whose coherence cannot be observed, i.e. superpositions of pure quantum states which are indistinguishable from mixtures. We discuss the connection of this phenomenon to the presence of superselection sectors. Our results suggest that the apparent classicality of macroscopic systems may be partly due to limitations on measurements and time evolutions imposed by computational complexity.

Comments
15 pages, 3 figures

Related papers

Quantum violation of macroscopic realism and the transition to classical physics

Johannes Kofler

The descriptions of the quantum realm and the macroscopic classical world differ significantly not only in their mathematical formulations but also in their foundational concepts and philosophical consequences. When and how physical systems stop to behave quantum mechanically and begin to behave classically is still heavily debated in the physics community and subject to theoretical and experimental research. This dissertation puts forward an approach to the quantum-to-classical transition fully within quantum theory and conceptually different from already existing models: It neither needs to refer to the uncontrollable environment of a system (decoherence) nor to change the quantum laws itself (collapse models), but puts the stress on the limits of observability of quantum phenomena due to the imprecision of our measurement apparatuses. For a certain class of time evolutions it is this mere restriction to coarse-grained measurements which is sufficient to see the natural emergence of macroscopic realism and even the classical Newtonian laws out of the full quantum formalism. But there also exist "non-classical" Hamiltonians for which a classical spatiotemporal description of the system's time evolution remains impossible even under fuzzy measurements or decoherence. It is argued that such Hamiltonians are unlikely to be spontaneously realized in nature because of their high complexity. The last part addresses the question of the origin of quantum randomness and proposes a link with mathematical undecidability.

arXiv:0812.0238•Dec 1, 2008•6 citations

Conditions for Quantum Violation of Macroscopic Realism

Johannes Kofler, Časlav Brukner

Why do we not experience a violation of macroscopic realism in everyday life. Normally, no violation can be seen either because of decoherence or the restriction of coarse-grained measurements, transforming the time evolution of any quantum state into a classical time evolution of a statistical mixture. We find the sufficient condition for these classical evolutions for spin systems under coarse-grained measurements. However, there exist "nonclassical" Hamiltonians whose time evolution cannot be understood classically, although at every instant of time the quantum state appears as a classical mixture. We suggest that such Hamiltonians are unlikely to be realized in nature because of their high computational complexity.

arXiv:0706.0668•Physical Review Letters•Aug 28, 2008•146 citations

Computational Solution to Quantum Foundational Problems

Arkady Bolotin

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.

arXiv:1403.7686•Physical Science International Journal•Jan 10, 2014•4 citations

The Quantum Measurement Problem and Physical reality: A Computation Theoretic Perspective

R. Srikanth

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.

•Feb 14, 2006•8 citations

The Quantum Measurement Problem and Physical reality: A Computation Theoretic Perspective

R. Srikanth

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.

arXiv:quant-ph/0602114•AIP conference proceedings•Jan 1, 2006•7 citations

Classical World Arising out of Quantum Physics under the Restriction of Coarse-Grained Measurements

Johannes Kofler, Časlav Brukner

Conceptually different from the decoherence program, we present a novel theoretical approach to macroscopic realism and classical physics within quantum theory. It focuses on the limits of observability of quantum effects of macroscopic objects, i.e., on the required precision of our measurement apparatuses such that quantum phenomena can still be observed. First, we demonstrate that for unrestricted measurement accuracy, no classical description is possible for arbitrarily large systems. Then we show for a certain time evolution that under coarse-grained measurements, not only macrorealism but even classical Newtonian laws emerge out of the Schrödinger equation and the projection postulate.

arXiv:quant-ph/0609079•Physical Review Letters•Nov 2, 2007•237 citations
The interface between the quantum and the classical is an intriguing and, at times, hotly contested subject of ongoing research. The quantum regime is characterized by interference, made possible by the superposition principle, while such phenomena are absent in macroscopic, everyday experience. Here, we investigate the link of this absence (or, as we will argue, unobservability) to computational complexity. We show how the assumption that quantum systems cannot solve NP-complete problems efficiently implies that certain formally valid quantum measurements on finite-dimensional systems are unperformable. We study several consequences of this restriction. First, Pauli matrices in an inconveniently transformed basis are a simple example of unobservables. Furthermore, some quantum states are not connected by any physically realizable time evolution. Finally there are quantum states whose coherence cannot be observed, i.e. superpositions of pure quantum states which are indistinguishable from mixtures. We discuss the connection of this phenomenon to the presence of superselection sectors. Our results suggest that the apparent classicality of macroscopic systems may be partly due to limitations on measurements and time evolutions imposed by computational complexity.
The descriptions of the quantum realm and the macroscopic classical world differ significantly not only in their mathematical formulations but also in their foundational concepts and philosophical consequences. When and how physical systems stop to behave quantum mechanically and begin to behave classically is still heavily debated in the physics community and subject to theoretical and experimental research. This dissertation puts forward an approach to the quantum-to-classical transition fully within quantum theory and conceptually different from already existing models: It neither needs to refer to the uncontrollable environment of a system (decoherence) nor to change the quantum laws itself (collapse models), but puts the stress on the limits of observability of quantum phenomena due to the imprecision of our measurement apparatuses. For a certain class of time evolutions it is this mere restriction to coarse-grained measurements which is sufficient to see the natural emergence of macroscopic realism and even the classical Newtonian laws out of the full quantum formalism. But there also exist "non-classical" Hamiltonians for which a classical spatiotemporal description of the system's time evolution remains impossible even under fuzzy measurements or decoherence. It is argued that such Hamiltonians are unlikely to be spontaneously realized in nature because of their high complexity. The last part addresses the question of the origin of quantum randomness and proposes a link with mathematical undecidability.
Why do we not experience a violation of macroscopic realism in everyday life. Normally, no violation can be seen either because of decoherence or the restriction of coarse-grained measurements, transforming the time evolution of any quantum state into a classical time evolution of a statistical mixture. We find the sufficient condition for these classical evolutions for spin systems under coarse-grained measurements. However, there exist "nonclassical" Hamiltonians whose time evolution cannot be understood classically, although at every instant of time the quantum state appears as a classical mixture. We suggest that such Hamiltonians are unlikely to be realized in nature because of their high computational complexity.
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.
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.
Conceptually different from the decoherence program, we present a novel theoretical approach to macroscopic realism and classical physics within quantum theory. It focuses on the limits of observability of quantum effects of macroscopic objects, i.e., on the required precision of our measurement apparatuses such that quantum phenomena can still be observed. First, we demonstrate that for unrestricted measurement accuracy, no classical description is possible for arbitrarily large systems. Then we show for a certain time evolution that under coarse-grained measurements, not only macrorealism but even classical Newtonian laws emerge out of the Schrödinger equation and the projection postulate.