pith. sign in

arxiv: 2606.20927 · v1 · pith:4YO5CVCRnew · submitted 2026-06-18 · 🪐 quant-ph · cs.CC

Unobservables and Decoherence from Complexity

Michael Epping , Jochen Szangolies This is my paper

Pith reviewed 2026-06-26 16:39 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords quantum measurementscomputational complexityNP-complete problemsdecoherencesuperselection sectorsunobservablesquantum-classical transition
0
0 comments X

The pith

The assumption that quantum systems cannot efficiently solve NP-complete problems implies some formally valid measurements are unperformable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that if quantum systems cannot solve NP-complete problems efficiently, then certain quantum measurements allowed by the formalism on finite-dimensional systems cannot actually be performed. This restriction produces unobservables such as Pauli matrices in inconvenient bases, pairs of states with no connecting physical evolution, and superpositions whose coherence is undetectable and thus indistinguishable from mixtures. The authors link the effect to superselection sectors and propose that computational complexity limits help account for why macroscopic systems behave classically. A sympathetic reader would see this as tying the quantum-to-classical transition to information-processing constraints instead of environment alone.

Core claim

Under the assumption that quantum systems cannot solve NP-complete problems efficiently, certain formally valid quantum measurements on finite-dimensional systems are unperformable. Examples include Pauli matrices in inconveniently transformed bases, quantum states not connected by any physically realizable time evolution, and superpositions of pure states whose coherence cannot be observed, making them indistinguishable from mixtures. These phenomena connect to the presence of superselection sectors, suggesting that limitations on measurements and time evolutions imposed by computational complexity may contribute to the apparent classicality of macroscopic systems.

What carries the argument

The implication from the assumption that quantum systems cannot solve NP-complete problems efficiently to the unperformability of certain formally allowed measurements and evolutions on finite-dimensional systems.

If this is right

  • Pauli matrices in certain transformed bases cannot be measured.
  • Some quantum states cannot be reached from others by any physically realizable time evolution.
  • Coherence in some superpositions cannot be observed and the states are indistinguishable from mixtures.
  • The effect relates directly to the presence of superselection sectors.
  • Limitations on measurements and evolutions from computational complexity may partly explain the classical appearance of macroscopic systems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result suggests effective superselection rules arising from complexity rather than fundamental postulates.
  • Small-scale quantum devices might be used to test whether measurements encoding hard problems remain inaccessible.
  • The approach could be extended to other no-go theorems that rest on computational bounds.
  • Decoherence-like effects might appear even in isolated finite systems when observables are computationally hard to access.

Load-bearing premise

Quantum systems cannot solve NP-complete problems efficiently.

What would settle it

An explicit physical procedure that performs a measurement corresponding to one of the unobservables identified under the complexity assumption, such as a Pauli operator whose basis transformation encodes an NP-complete problem.

Figures

Figures reproduced from arXiv: 2606.20927 by Jochen Szangolies, Michael Epping.

Figure 1
Figure 1. Figure 1: FIG. 1. Circuit implementations for [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. The main idea of the hypothetical algorithm: Sequential measurements and reversing unwanted outcomes using a [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. A unitary quantum circuit that implements the same operation as the reversible measurement, where only the [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper claims that the assumption that quantum systems cannot solve NP-complete problems efficiently (BQP does not contain NP) implies that certain formally valid quantum measurements on finite-dimensional systems are physically unperformable. Consequences include Pauli matrices in inconveniently transformed bases as unobservables, quantum states not connected by any physically realizable time evolution, and superpositions whose coherence is unobservable (indistinguishable from mixtures), with a suggested link to superselection sectors. The authors argue this may partly explain the apparent classicality of macroscopic systems via computational complexity limits on measurements and evolutions.

Significance. If explicit reductions were provided establishing that implementing the claimed unobservables would yield a polynomial-time quantum algorithm for an NP-complete problem (with system dimension scaling appropriately with instance size), the work would offer a novel complexity-theoretic account of unobservability and the quantum-to-classical transition, independent of standard decoherence mechanisms. The conditional nature of the argument limits its immediate impact absent such reductions and independent motivation for the core assumption.

major comments (3)
  1. [Abstract and §1] Abstract and §1: The central implication—that the complexity assumption forces certain finite-dimensional measurements to be unperformable—requires an explicit reduction showing that a quantum circuit or protocol realizing the measurement solves an NP-complete problem in polynomial time. No such reduction (mapping the measurement outcome to an NP witness or decision) is visible, rendering the premise-to-conclusion step unsecured.
  2. [Discussion of finite-dimensional systems (likely §3 or §4)] Discussion of finite-dimensional systems (likely §3 or §4): The finite-dimensional qualifier is load-bearing, yet the argument does not demonstrate that the Hilbert-space dimension scales with the size of the NP instance; without this, the BQP⊈NP premise cannot apply to rule out the measurement.
  3. [Example of transformed Pauli matrices (likely §2)] Example of transformed Pauli matrices (likely §2): The claim that these are unobservables is not supported by showing that their measurement protocol would place an NP-complete problem in BQP; the formal validity of the observable is acknowledged but the complexity obstruction is asserted without the required circuit reduction.
minor comments (2)
  1. [Introduction] Notation for the complexity assumption (e.g., BQP vs. NP) should be standardized and referenced to standard definitions in the introduction.
  2. [Final section] The connection to superselection sectors in the final section would benefit from a brief comparison to existing literature on superselection and complexity.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for the thoughtful and detailed report. The comments correctly identify that the manuscript's central claims rest on a conceptual link between the BQP ⊈ NP assumption and unperformable measurements, without supplying explicit circuit reductions or dimension-scaling arguments. We address each point below, indicating revisions where we can strengthen clarity without overstating what the current work contains.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and §1: The central implication—that the complexity assumption forces certain finite-dimensional measurements to be unperformable—requires an explicit reduction showing that a quantum circuit or protocol realizing the measurement solves an NP-complete problem in polynomial time. No such reduction (mapping the measurement outcome to an NP witness or decision) is visible, rendering the premise-to-conclusion step unsecured.

    Authors: We agree that an explicit reduction would make the implication rigorous and directly connect a measurement protocol to placing an NP-complete problem in BQP. The manuscript advances a general conceptual argument: under the standing assumption that BQP does not contain NP, any measurement whose efficient implementation would require solving an NP-complete problem must be physically unperformable. No concrete reduction is provided because the work focuses on the logical consequence rather than constructive complexity theory. We will revise the abstract and §1 to explicitly flag this gap and state that the argument remains conditional on future reductions. revision: partial

  2. Referee: [Discussion of finite-dimensional systems (likely §3 or §4)] Discussion of finite-dimensional systems (likely §3 or §4): The finite-dimensional qualifier is load-bearing, yet the argument does not demonstrate that the Hilbert-space dimension scales with the size of the NP instance; without this, the BQP⊈NP premise cannot apply to rule out the measurement.

    Authors: The referee is correct that the BQP ⊈ NP premise applies only when the relevant problem size (and thus Hilbert-space dimension) grows with the instance. The manuscript treats finite-dimensional systems in which the dimension is variable and part of the input description; however, it does not explicitly map dimension to NP-instance size for each example. We will revise the relevant sections to include a clear statement of how dimension scales with problem size, thereby making the applicability of the complexity assumption explicit. revision: yes

  3. Referee: [Example of transformed Pauli matrices (likely §2)] Example of transformed Pauli matrices (likely §2): The claim that these are unobservables is not supported by showing that their measurement protocol would place an NP-complete problem in BQP; the formal validity of the observable is acknowledged but the complexity obstruction is asserted without the required circuit reduction.

    Authors: We acknowledge that the transformed-Pauli example illustrates the idea but does not contain an explicit reduction showing that measuring the observable solves an NP-complete problem. The manuscript presents it as a minimal illustration of the general principle rather than a fully worked complexity reduction. We will revise §2 to clarify the illustrative nature of the example and to note that a concrete reduction remains an open technical task. revision: partial

standing simulated objections not resolved
  • Explicit reductions establishing that realizing the claimed unobservables (including transformed Pauli measurements) would yield a polynomial-time quantum algorithm for an NP-complete problem.

Circularity Check

0 steps flagged

No circularity; central claim is conditional implication from external complexity assumption

full rationale

The paper states its strongest claim as a conditional: the assumption that quantum systems cannot solve NP-complete problems efficiently implies certain finite-dimensional measurements are unperformable. This premise is introduced externally rather than derived from any internal definition, fit, or self-citation chain. No equations or steps in the abstract reduce a 'prediction' to a fitted parameter by construction, nor does any load-bearing step invoke a uniqueness theorem or ansatz from the authors' prior work. The derivation therefore remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on one domain assumption about quantum computational limits; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Quantum systems cannot solve NP-complete problems efficiently
    This is explicitly identified in the abstract as the assumption from which all consequences for unobservables and decoherence follow.

pith-pipeline@v0.9.1-grok · 5715 in / 1163 out tokens · 26340 ms · 2026-06-26T16:39:40.287539+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references

  1. [1]

    InitializeN+Mqubits in|+⟩ ⊗(N+M)

  2. [2]

    From now onewill track the clauses satisfied by the current state and protected byN(e)

    Initialize the established formulaewithtrue(empty formula). From now onewill track the clauses satisfied by the current state and protected byN(e)

  3. [3]

    unsatisfiable

    For every clauseC ′ i inD(F): (a) MeasureM(C ′ i). (b) If the outcome is Π(C ′ i), then sete=e∧C ′ i. (c) If the outcome is Π(¬C′ i), then undo the unwanted projection by measuringN(e). (d) Try a fixed number of timesRto obtain the out- come Π(C ′ i). RedrawC ′ i if it is a random XOR clause. (e) Return “unsatisfiable” if allRattempts failed. This is corr...

  4. [4]

    The firstNqubits yield the solutionv ∗ that satisfiesF

    Measure in the computational basis. The firstNqubits yield the solutionv ∗ that satisfiesF. out with the finite resources of any observer. Thus, for this problem size,N(F) is a simple example of a POVM that has no counter-part in any physical system, even for comparatively modest system sizes. Consequently, there are mathematically valid quantum measureme...

    1952

  5. [5]

    C. A. Fuchs, Mind and Matter15, 245 (2017)

    2017

  6. [6]

    E. P. Wigner, inPhilosophical reflections and syntheses (Springer, 1995) pp. 247–260

    1995

  7. [7]

    Ueda, Frontiers in Quantum Physics , 136 (1998)

    M. Ueda, Frontiers in Quantum Physics , 136 (1998)

    1998

  8. [8]

    A. N. Jordan and A. N. Korotkov, Contemporary Physics 51, 125 (2010)

    2010

  9. [9]

    Schindler, T

    P. Schindler, T. Monz, D. Nigg, J. T. Barreiro, E. A. Martinez, M. F. Brandl, M. Chwalla, M. Hennrich, and R. Blatt, Physical review letters110, 070403 (2013)

    2013

  10. [10]

    W. H. Zurek, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sci- ences376, 20170315 (2018)

    2018

  11. [11]

    Joos and H

    E. Joos and H. D. Zeh, Zeitschrift f¨ ur Physik B Con- densed Matter59, 223 (1985)

    1985

  12. [12]

    E. Joos, H. D. Zeh, C. Kiefer, D. J. Giulini, J. Kupsch, and I.-O. Stamatescu,Decoherence and the appearance of a classical world in quantum theory(Springer Science & Business Media, 2013)

    2013

  13. [13]

    Aaronson, Y

    S. Aaronson, Y. Atia, and L. Susskind, arXiv preprint arXiv:2009.07450 (2020)

    arXiv 2009

  14. [14]

    Fine, inStudies in Logic and the Foundations of Math- ematics, Vol

    A. Fine, inStudies in Logic and the Foundations of Math- ematics, Vol. 74 (Elsevier, 1973) pp. 567–581

    1973

  15. [15]

    Maudlin, topoi14, 7 (1995)

    T. Maudlin, topoi14, 7 (1995)

    1995

  16. [16]

    A. R. Calderbank and P. W. Shor, Phys. Rev. A54, 1098 (1996)

    1996

  17. [17]

    Steane, Proceedings of the Royal Society of London

    A. Steane, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sci- ences452, 2551–2577 (1996)

    1996

  18. [18]

    Van Gelder and I

    A. Van Gelder and I. Spence, inTheory and Applications of Satisfiability Testing – SAT 2010, edited by O. Strich- man and S. Szeider (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010) pp. 388–397

    2010

  19. [19]

    Aaronson, ACM Sigact News36, 30 (2005)

    S. Aaronson, ACM Sigact News36, 30 (2005)

    2005

  20. [20]

    C. P. Gomes, A. Sabharwal, and B. Selman, inPro- ceedings of the 20th International Conference on Neural Information Processing Systems, NIPS’06 (MIT Press, Cambridge, MA, USA, 2006) p. 481–488

    2006

  21. [21]

    Peres,Quantum theory concepts and methods, reprint

    A. Peres,Quantum theory concepts and methods, reprint. with corr. ed., Fundamental theories of physics 57 (Kluwer, Dordrecht [u.a, 1993)

    1993

  22. [22]

    Von Neumann,Mathematische Grundlagen der Quan- tenmechanik, Grundlehren der mathematischen Wis- senschaften 38 (Springer, Berlin, 1932)

    J. Von Neumann,Mathematische Grundlagen der Quan- tenmechanik, Grundlehren der mathematischen Wis- senschaften 38 (Springer, Berlin, 1932)

    1932

  23. [23]

    G. C. Wick, A. S. Wightman, and E. P. Wigner, Physical Review88, 101 (1952)

    1952

  24. [24]

    Hepp, Helv

    K. Hepp, Helv. Phys. Acta45, 237 (1972)

    1972

  25. [25]

    Bub, inPSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, Vol

    J. Bub, inPSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, Vol. 2 (Cambridge University Press, 1988) pp. 134–144

    1988

  26. [26]

    Bub, Foundations of physics18, 701 (1988)

    J. Bub, Foundations of physics18, 701 (1988)

    1988

  27. [27]

    Araki, inFundamental Aspects of Quantum Theory (Springer, 1986) pp

    H. Araki, inFundamental Aspects of Quantum Theory (Springer, 1986) pp. 23–33

    1986

  28. [28]

    N. P. Landsman, Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics26, 45 (1995)

    1995

  29. [29]

    Svozil, Foundations of Physics56, 4 (2026)

    K. Svozil, Foundations of Physics56, 4 (2026)

    2026

  30. [30]

    W. H. Zurek, Reviews of modern physics75, 715 (2003)

    2003

  31. [31]

    Peres, Physical Review D22, 879 (1980)

    A. Peres, Physical Review D22, 879 (1980). 6 Appendix A: Undoing a Measurement with a F our-Qubit Code In the following we describe a code that can undo a measurement with the smallest number of qubits possible. The codeq 4 is a CSS code [12, 13] that encodes two logical qubits into four physical ones, with a code distance of two. Hence, in the usual nota...

    1980

  32. [32]

    The state is 1 2(1+g 1)|ψ ′⟩ ∝ ψ

    The syndrome is 00, so we apply no correction. The state is 1 2(1+g 1)|ψ ′⟩ ∝ ψ

  33. [33]

    collapse

    The syndrome is 10, so we applyZ 1 and the state isZ 1 1 2(1−g 1)|ψ ′⟩ ∝ ψ . Either way, we restored the original state that described the system prior to the collapse. A similar analysis can be done for other measurement bases. It is noteworthy that the entanglement is restored by the measurement, not by the correction, which only affects a single qubit....

  34. [34]

    normal or

    It is defined analogously toM(C m) in Eq. (B6) as M  _ i∈S vi   (B7) for someS⊂ {1,2, .., N}, except that we use the XOR in contrast to the “normal or” that appears in the clauses of F. Also this measurement can be implemented efficiently, see Fig. 1b for an example. The sequential measurement ofMfor all clauses inFwith outcomesx= (x 1, x2, ..., xm) i...

  35. [35]

    together they exclude half of the solutions, namely wherev N+m ̸=C m

    Note that the product of these probabilities is 1 2, i.e. together they exclude half of the solutions, namely wherev N+m ̸=C m. In terms of the original variablesv qm1,v qm2, andv qm3, all assignments still appear with the same relative weight, such that the next set of four clauses (m→m+ 1) have the same probabilities. lm1 lm1 lm1 vN+m Excluded by clause...

  36. [36]

    Considering both cases we have thatP(|S i \T|is even) is equal to or larger than 1 2 and strictly larger than 1 2 when averaged overT, i.e

    Thus|S i \T|is even and odd with equal probability. Considering both cases we have thatP(|S i \T|is even) is equal to or larger than 1 2 and strictly larger than 1 2 when averaged overT, i.e. when averaged overσ. TheMXOR clauses gradually excludev N+m = false for allm(Mvariables andMindependent constraints). Suppose that the set of solutions before adding...