Computability in Quantum Mechanics

Dorit Aharonov, Umesh V. Vazirani

Quantum computation teaches us that quantum mechanics exhibits exponential complexity. We argue that the standard scientific paradigm of "predict and verify" cannot be applied to testing quantum mechanics in this limit of high complexity. We describe how QM can be tested in this regime by extending the usual scientific paradigm to include {\it interactive experiments}.

Tien D. Kieu

Lorenzo Catani, Dan E. Browne, Nadish de Silva

Spekkens’ toy model (SM) is a non-contextual hidden-variable model made to support the epistemic view of quantum theory, where quantum states are states of partial knowledge about a deeper underlying reality. Despite being a classical model, it has reproduced many features of quantum theory (entanglement, teleportation, . . .): (almost) everything but contextuality, which therefore seems to be the inherent quantum feature. In addition to the importance in foundation of quantum theory, the notion of contextuality seems to be a crucial resource for quantum computation. In particular it has been proven that, in the case of odd prime discrete dimensional systems, contextuality is necessary for universal quantum computation in state-injection schemes of computation based on stabilizer quantum mechanics (SQM). The latter is a subtheory of quantum mechanics which is very popular in the field of quantum computation and quantum error correction. State-injection schemes consist of a classically-simulable part (like SQM) and a resource state that boosts the computation to a quantum improvement. In the odd-dimensional case, SM is operationally equivalent to SQM. In the even-dimensional case, the equivalence only holds in terms of structure, not in terms of statistical predictions. This because qubit-SQM shows contextuality, while qudit(odd dimensions)-SQM does not. We believe that SM can be a valid tool to study contextuality as a resource in the field of quantum computation. Restricted versions of SM compatible with quantum mechanics (QM) can be used as the non-contextual classically-simulable part of state-injection schemes thus opening other scenarios where studying if contextuality is necessary for quantum computational speed-up.

Stefano Olivares

Ed Gerck

We present a proposal addressing the foundational question of whether quantum mechanics can be reformulated in a computable way. Using a rational, and deterministic framework based on arbitrary-length integers and algebra. Departing from traditional models that rely on real numbers, complex amplitudes, and probabilistic interpretations, we propose a rational-number-based formulation of quantum mechanics. We demonstrate this approach through the exact eigenvalue formulation of the Schrödinger equation, a harmonization of general relativity with QM, and a reworking of Shor's algorithm using only finite, rational arithmetic (ISA). Our results suggest that quantum theory can be grounded in exact, computable logic that aligns with physical measurement, quantum computing, and existing digital hardware.

Bart D’Hooghe, Jarosław Pykacz