It is often assumed that the complete physics theory of the universe is computable - in sense that it can provide meaningful theoretical predictions for every phenomenon of the universe. Against this view, it is argued that once quantum mechanics is understood as encompassing a novel concept of probability, thereby resolving the measurement problem in straightforward ways, the interpretation speaks for uncomputability of the complete physics theory. The reasons why a new theory of probability is needed are explored, along the lines of the principle of indifference and the sleeping beauty problem.
When statistical models are used in social sciences, there is no presumption that actual reality is stochastic. Even if actual reality is deterministic, hidden and unobservable variables require a use of effective (in ordinary language, approximate) models, with number of variables potentially unrestricted. From the quantum reconstruction point of view, quantum mechanics can be interpreted as a statistical information-processing framework - therefore, the aforementioned view in social sciences can naturally be transported to quantum physics - this especially so given prevalent uses of effective theories. This naturally gives us the common framework behind hidden variables interpretations unconstrained by particular laws of deterministic motion. The measurement problem is cleanly identified as arising from missing hidden variables. However, hidden variables interpretations do not imply that a final UV-complete theory of physics has to be usable - the theory may be uncomputable, with inability to generate predictions. In such a case, an infinite sequence of effective quantum theories would have to be used. Therefore, even if hidden variables interpretations are correct, supremacy of the orthodox quantum mechanics framework may be upheld, which is supported by a combination of quantum reconstruction and computational complexity arguments. This allows us to bypass considerable difficulties of hidden variables interpretations in satisfying Lorentz invariance. Connections to entropic gravity are then explored.
Quantum programs that use temporary values, known as \emph{ancilla} qubits, must explicitly \emph{uncompute} each ancilla back to zero to ensure that the program produces correct outputs. Conventional uncomputation uses unitary quantum gates, whereas leading quantum algorithms now leverage \emph{measurement-based uncomputation} (MBU), which replaces costly unitary
T gates with cheaper measurements and phase corrections.
Current quantum programming frameworks can use measurement to uncompute specific gates such as Toffoli. No automatic transformation, however, accepts an arbitrary circuit whose ancillas are computed and uncomputed via the standard approach and converts the circuit to use MBU\@. Researchers instead apply MBU to individual circuit designs by hand, which limits algorithm development and compiler optimization.
Such a transformation has not existed due to two fundamental unknowns: where MBU applies and which gates realize MBU for an arbitrary computation. To solve these, we first present a static analysis that identifies, for each ancilla qubit, each circuit position where measurement is sound --- subsuming basic assumptions that MBU only applies at the end of a circuit. Next, we present circuit transformations that soundly turn unitary uncomputation gates into efficient phase corrections after measurement --- generalizing rewrite rules from prior literature that are either limited to a single gate or not applicable to a general circuit.
We present \textsf{MBUndo}, an integrated compiler pass that automatically converts circuits to measurement-based uncomputation. It requires no user annotations other than which qubits are ancillas, the same as needed by existing uncomputation synthesizers, and can enhance their output circuits. We evaluate \textsf{MBUndo} on 22 benchmarks to reveal \emph{T} gate reductions of
>36.5% over uncomputation synthesizers.