This paper introduces an observation-respecting computational principle that forbids the existence of pre-solution “cheat sheets” for canonical SAT instances. Classical complexity theory implicitly allows auxiliary information that encodes solution-relevant structure prior to solving, erasing any notion of causal or observational order. In contrast, physically grounded models of computation—motivated by quantum mechanics—permit classical information only as the irreversible outcome of explicit measurement. We formalize this distinction by introducing non-resolving preprocessing procedures, defined as polynomial-time processes that avoid satisfiability-correlated measurement. For a canonical non-uniform family of satisfiable SAT instances, we define a hierarchy of solution structures and show that no such preprocessing can significantly compress these structures prior to observation. The obstruction arises from a fundamental mismatch between distribution-level information available before measurement and realization-dependent information that emerges only after satisfiability is resolved. Rather than claiming a resolution of P versus NP in the classical Turing model, this work isolates a precise conceptual barrier: realization-dependent solution information cannot be generated in advance without violating observation-respecting constraints. The result provides a physically motivated explanation for persistent pre-solution information asymmetry in NP-complete problems and suggests new directions for examining computational hardness through the lens of information generation.
This paper introduces an observation-respecting computational principle that forbids the existence of pre-solution “cheat sheets” for canonical SAT instances. Classical complexity theory implicitly allows auxiliary information that encodes solution-relevant structure prior to solving, erasing any notion of causal or observational order. In contrast, physically grounded models of computation—motivated by quantum mechanics—permit classical information only as the irreversible outcome of explicit measurement. We formalize this distinction by introducing non-resolving preprocessing procedures, defined as polynomial-time processes that avoid satisfiability-correlated measurement. For a canonical non-uniform family of satisfiable SAT instances, we define a hierarchy of solution structures and show that no such preprocessing can significantly compress these structures prior to observation. The obstruction arises from a fundamental mismatch between distribution-level information available before measurement and realization-dependent information that emerges only after satisfiability is resolved. Rather than claiming a resolution of P versus NP in the classical Turing model, this work isolates a precise conceptual barrier: realization-dependent solution information cannot be generated in advance without violating observation-respecting constraints. The result provides a physically motivated explanation for persistent pre-solution information asymmetry in NP-complete problems and suggests new directions for examining computational hardness through the lens of information generation.
We approach the 3-SAT satisfiability problem with the quantum-inspired method of imaginary time propagation (ITP) applied to matrix product states (MPS) on a classical computer. This ansatz is fundamentally limited by a quantum entanglement barrier that emerges in imaginary time, reflecting the exponential hardness expected for this NP-complete problem. Strikingly, we argue based on careful analysis of the structure imprinted onto the MPS by the 3-SAT instances that this barrier arises from classical computational complexity. To reveal this connection, we elucidate with stochastic models the specific relationship between the classical hardness of the ♯P ⊇ NP-complete counting problem $\sharp$3-SAT and the entanglement properties of the quantum state. Our findings illuminate the limitations of this quantum-inspired approach and demonstrate how purely classical computational complexity can manifest in quantum entanglement. Furthermore, we present estimates of the non-stabilizerness required by the protocol, finding a similar resource barrier. Specifically, the necessary amount of non-Clifford operations scales superlinearly in system size, thus implying extensive resource requirements of ITP on different architectures such as Clifford circuits or gate-based quantum computers.
A conceptual difficulty in the foundations of quantum mechanics is the quantum measurement problem (QMP), essentially concerned with the apparent non-unitarity of the measurement process and the classicality of macroscopic systems. In an information theoretic approach proposed by us earlier (Quantum Information Processing 2, 153, 2003), which we clarify and elaborate here, QMP is understood to signal a fundamental finite resolution of quantum states, or, equivalently, a discreteness of Hilbert space. This was motivated by the notion that physical reality is a manifestation of information stored and discrete computations performed at a deeper, sub-physical layer. This model entails that states of sufficiently complex, entangled systems will be unresolvable, or, {\em computationally unstable}. Wavefunction collapse is postulated as an error preventive response to such computational instability. In effect, sufficiently complex systems turn classical because of the finiteness of the computational resources available to the physical universe. We show that this model forms a reasonable complement to decoherence for resolving QMP, both in respect of the problem of definite outcomes and of the preferred basis problem. The model suggests that QMP, as a window on the sub-physical universe, serves as a witness to Wheeler's koan ``it from bit''. Some implications for quantum computation and quantum gravity are examined.
This note presents a structural resolution of the quantum measurement problem by decomposing it into three distinct physical layers: the persistence of quantum coherence, the emergence of a single definite classical outcome, and the origin of quantum probability. It provides physical explanations for coherence loss and outcome definiteness based on coordination limits, thermodynamic irreversibility, and information stability, without introducing new dynamics or observer postulates. The analysis further clarifies that the Born rule does not arise from measurement or macroscopic processing, but is an irreducible structural constraint governing microscopic quantum interactions. By correctly delimiting the scope of measurement theory, the note resolves longstanding conceptual confusion while remaining fully consistent with standard quantum mechanics.
We present an algorithm, along with a correctness proof, for solving the 3 Satisfiability problem that is inspired by quantum mechanical principles and that runs in polynomial time with respect to the size of the input problem. Even though we term both our algorithm and its associated proof as quantum (for reasons which we will demonstrate), it is intended to be run on standard classical architecture. In the article, we posit that the 3 Satisfiability problem has an intrinsic complex quantum form that can be programmed in order to build a model of the solution space for satisfiable instances or show that such a model cannot be constructed. This yields surprising results on the ability for classical systems to abstractly simulate general quantum systems.
We present an operational account of quantum measurement in which outcome definiteness and irreversibility arise from causal structure, decoherence, and computational constraints rather than from fundamental collapse. We show that in any globally unitary quantum system with environmental coupling and nontrivial causal partitioning, no physically realizable observer can access all information pathways simultaneously. As a result, observer-dependent descriptions—definite outcomes for embedded observers and coherent superpositions for external observers—are mutually consistent and cannot lead to operational contradiction. This framework resolves Wigner-type measurement paradoxes and clarifies the origin of irreversibility without modifying quantum mechanics.
The central problem in computer science is the conjecture that two complexity classes, P (polynomial time) and NP (nondeterministic polynomial time-roughly those decision problems for which a proposed solution can be checked in polynomial time), are distinct in the standard Turing model of computation: P not equal NP. As a generality, we propose that each physical theory supports computational models whose power is limited by the physical theory. It is well known that classical physics supports a multitude of implementation of the Turing machine. Non-Abelian topological quantum field theories exhibit the mathematical features necessary to support a model capable of solving all #P problems, a computationally intractable class, in polynomial time. Specifically, Witten [Witten, E. (1989) Commun. Math. Phys. 121, 351-391] has identified expectation values in a certain SU(2)-field theory with values of the Jones polynomial [Jones, V. (1985) Bull. Am. Math. Soc. 12, 103-111] that are #P-hard [Jaeger, F., Vertigen, D. & Welsh, D. (1990) Math. Proc. Comb. Philos. Soc. 108, 35-53]. This suggests that some physical system whose effective Lagrangian contains a non-Abelian topological term might be manipulated to serve as an analog computer capable of solving NP or even #P-hard problems in polynomial time. Defining such a system and addressing the accuracy issues inherent in preparation and measurement is a major unsolved problem.