The work sits at the intersection of quantum measurement theory, complexity theory, and the foundations of quantum mechanics. Nearby in the archive are studies on decoherence, entanglement, quantum states, and quantum teleportation. The common thread in these works is how quantum properties appear or disappear in macroscopic systems. This paper stands out because it is the first to tie the observability of coherence directly to a computationally hard problem, rather than to interaction with the environment or to instrument imprecision.
The authors construct a specific measurement, called a sandwich POVM, which is formally valid in quantum mechanics, but whose implementation would allow efficient solution of the 3SAT problem. The idea behind the algorithm is to measure sequentially whether the state satisfies each clause of the formula and, on an unwanted outcome, to 'undo' the measurement with a special procedure that returns the state to its previous form. To avoid exponentially small success probabilities, the formula is 'diluted' by adding auxiliary variables and random XOR clauses. If such a measurement could be performed, the algorithm would solve an NP-complete problem in polynomial time, contradicting the widely held assumption that quantum computers are inefficient for NP-complete problems.
It is shown that, under the condition NP ⊄ BQP, there exist measurements that cannot be realized physically in any system. These measurements are called unobservable. A concrete example: in a sufficiently large Hilbert space, one can choose a basis in which the Pauli matrices turn out to be unobservable. It follows that there exist unitary operators that do not correspond to any physical evolution in time, and pairs of states that cannot be transformed into each other by any allowed evolution. Moreover, the superposition of such states is indistinguishable from their mixture in the outcomes of any observable measurements. This means that the coherence between them cannot be detected, which formally coincides with the presence of a superselection rule.
The work introduces a new source of decoherence: not only interaction with the environment, but also computational complexity can render quantum coherence unobservable. Unlike neighboring works, which study decoherence through models of the environment or noise, here the limitation is derived from fundamental assumptions about computational complexity. This opens the possibility of explaining the classicality of macroscopic systems without invoking a specific decoherence mechanism. If complexity really does limit observability, then the classical world may arise not from a physical process, but from the fundamental inaccessibility of certain measurements.
The topic could develop toward a quantitative assessment of the contribution of computational complexity to decoherence. So far, only the existence of unobservable measurements has been shown, not their prevalence. One could investigate how often states with unobservable coherence arise in real systems and how this relates to known decoherence mechanisms. Another direction is the study of approximate implementations of unobservable measurements: the work shows that even an approximate implementation with sufficient accuracy is also impossible, but the boundaries of this impossibility need to be clarified.
The results may influence the interpretation of quantum mechanics, especially the measurement problem and the origin of the classical world. They also matter for quantum computing, pointing to fundamental limits on the operations that can be implemented.
The next step could be the development of a quantitative theory of the unobservable, estimating at what system sizes and problem complexities the limitations become significant. It is also important to explore the connection with existing models of decoherence and superselection.
The work directly addresses the quantum measurement problem and the question of why macroscopic systems look classical. It proposes a new mechanism of effective superselection based on computational complexity, which may complement known approaches such as environment-induced decoherence and spontaneous symmetry breaking. It remains an open question how universal this mechanism is and whether it can explain the observed classicality in all cases.
To undo an unwanted measurement outcome, a quantum code with four qubits is used, which encodes two logical qubits. This is the smallest possible code capable of correcting a single error with a known location.