Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0610040 · Foundations of Physics

Measurement-Based Quantum Computation and Undecidable Logic

Maarten Van den Nest, Hans J. Briegel

Published Mar 13, 2008• 17 citations
arXivHTMLPDF
DOI
10.1007/s10701-008-9212-6

Related papers

Quantum measurement occurrence is undecidable

Jens Eisert, Markus P. Müller, Christian Gogolin

In this work, we show that very natural, apparently simple problems in quantum measurement theory can be undecidable even if their classical analogues are decidable. Undecidability hence appears as a genuine quantum property here. Formally, an undecidable problem is a decision problem for which one cannot construct a single algorithm that will always provide a correct answer in finite time. The problem we consider is to determine whether sequentially used identical Stern-Gerlach-type measurement devices, giving rise to a tree of possible outcomes, have outcomes that never occur. Finally, we point out implications for measurement-based quantum computing and studies of quantum many-body models and suggest that a plethora of problems may indeed be undecidable.

arXiv:1111.3965•Physical Review Letters•Jun 25, 2012•50 citations

Measurement-based quantum computation

Hans J. Briegel, Dan E. Browne, Wolfgang Dür +2 more

arXiv:0910.1116•Nature Physics•Jan 1, 2009•1,087 citations

Mathematical undecidability and quantum randomness

Tomasz Paterek, Časlav Brukner, Robert Prevedel +4 more

We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms and show that quantum measurements are capable of revealing whether a given proposition is decidable or not within the axiomatic system. Whenever a mathematical proposition is undecidable within the axioms encoded in the state, the measurement associated with the proposition gives random outcomes. Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability. Whenever a proposition and a given set of axioms together contain more information than the axioms themselves, the proposition can neither be proved nor disproved from the axioms { it is mathematically undecidable [1, 2]. Here we propose a novel link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms. Quantum mechanics imposes an upper limit on how much information can be encoded in a quantum state [3, 4], thus limiting the information content of the set of axioms. We show that quantum measurements are capable of revealing whether a given proposition is decidable or not. Whenever a mathematical proposition is undecidable within the system of axioms encoded in the state, the measurement associated with the proposition gives random outcomes. This allows for an experimental test of mathematical undecidability by realizing in the laboratory both the actual quantum states and the required quantum measurements. (To illustrate these ideas, we conducted experiments using the polarization of photons.) Our results support the view that quantum randomness is irreducible [5, 6] and a manifestation of mathematical undecidability. Any formal system is based on axioms, which are propositions that are dened to be true. A proposition is logically independent from a given set of axioms if it can neither be proved nor disproved from the axioms. If a proposition is independent from the axioms, neither the proposition itself nor its negation creates an inconsistency together with the axiomatic system. ^

•Dec 1, 2008•1 citation

Undecidability of Hitting Times in Computably Described Quantum Dynamics: A No-Go Theorem for Universal Time Selection

Katsufumi Matsuura

We study the Unitary Hitting Time Problem (UHTP) in quantum dynamics. Given computably described pure states |a>, |b> and a time-dependent unitary U(t), define the hitting time as the infimum of t > 0 such that the fidelity between U(t)|a> and |b> reaches a fixed threshold (with infinity if the threshold is never reached). We prove that there is no total algorithm that outputs this hitting time for all inputs; equivalently, the total UHTP is undecidable via a reduction from the halting problem. Operationally, we show a no-go theorem: for any fixed accuracy parameters, there is no universal finite-resource protocol that, for all computably described inputs, correctly outputs the hitting time while obeying uniform finite upper bounds on observation time and on dissipation/work. The proofs use reversible computation embedded into unitary dynamics, a fixed-target beacon construction, and a continuous-time lifting via piecewise-constant Hamiltonians. Our results target systems capable of embedding universal computation and complement prior undecidability results such as spectral-gap and quantum-control reachability. We distinguish logical time (inside the equations) from physical/operational time (of preparation, evolution, measurement), and show that universal time-step selection is impossible in both senses. Revised version. The main result has been strengthened to undecidability under a single fixed periodically driven unitary dynamics. The discussion of related work and the computability assumptions have also been expanded.

quant-pharXiv:2512.11006•Dec 12, 2025•0 citations

Demonstration of measurement-free universal logical quantum computation

Friederike Butt, Ivan Pogorelov, Freund, Robert +4 more

Nature Communications•Jan 1, 2026•0 citations

Demonstration of measurement-free universal logical quantum computation

Butt, Friederike, Pogorelov, Ivan, Freund, Robert +4 more

•Jan 1, 2026•0 citations
In this work, we show that very natural, apparently simple problems in quantum measurement theory can be undecidable even if their classical analogues are decidable. Undecidability hence appears as a genuine quantum property here. Formally, an undecidable problem is a decision problem for which one cannot construct a single algorithm that will always provide a correct answer in finite time. The problem we consider is to determine whether sequentially used identical Stern-Gerlach-type measurement devices, giving rise to a tree of possible outcomes, have outcomes that never occur. Finally, we point out implications for measurement-based quantum computing and studies of quantum many-body models and suggest that a plethora of problems may indeed be undecidable.
We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms and show that quantum measurements are capable of revealing whether a given proposition is decidable or not within the axiomatic system. Whenever a mathematical proposition is undecidable within the axioms encoded in the state, the measurement associated with the proposition gives random outcomes. Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability. Whenever a proposition and a given set of axioms together contain more information than the axioms themselves, the proposition can neither be proved nor disproved from the axioms { it is mathematically undecidable [1, 2]. Here we propose a novel link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms. Quantum mechanics imposes an upper limit on how much information can be encoded in a quantum state [3, 4], thus limiting the information content of the set of axioms. We show that quantum measurements are capable of revealing whether a given proposition is decidable or not. Whenever a mathematical proposition is undecidable within the system of axioms encoded in the state, the measurement associated with the proposition gives random outcomes. This allows for an experimental test of mathematical undecidability by realizing in the laboratory both the actual quantum states and the required quantum measurements. (To illustrate these ideas, we conducted experiments using the polarization of photons.) Our results support the view that quantum randomness is irreducible [5, 6] and a manifestation of mathematical undecidability. Any formal system is based on axioms, which are propositions that are dened to be true. A proposition is logically independent from a given set of axioms if it can neither be proved nor disproved from the axioms. If a proposition is independent from the axioms, neither the proposition itself nor its negation creates an inconsistency together with the axiomatic system. ^
We study the Unitary Hitting Time Problem (UHTP) in quantum dynamics. Given computably described pure states |a>, |b> and a time-dependent unitary U(t), define the hitting time as the infimum of t > 0 such that the fidelity between U(t)|a> and |b> reaches a fixed threshold (with infinity if the threshold is never reached). We prove that there is no total algorithm that outputs this hitting time for all inputs; equivalently, the total UHTP is undecidable via a reduction from the halting problem. Operationally, we show a no-go theorem: for any fixed accuracy parameters, there is no universal finite-resource protocol that, for all computably described inputs, correctly outputs the hitting time while obeying uniform finite upper bounds on observation time and on dissipation/work. The proofs use reversible computation embedded into unitary dynamics, a fixed-target beacon construction, and a continuous-time lifting via piecewise-constant Hamiltonians. Our results target systems capable of embedding universal computation and complement prior undecidability results such as spectral-gap and quantum-control reachability. We distinguish logical time (inside the equations) from physical/operational time (of preparation, evolution, measurement), and show that universal time-step selection is impossible in both senses. Revised version. The main result has been strengthened to undecidability under a single fixed periodically driven unitary dynamics. The discussion of related work and the computability assumptions have also been expanded.