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:2512.11006

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

Katsufumi Matsuura

quant-phSubmitted Dec 11, 2025• Announced Dec 12, 2025• 0 citations• Revised Aug 12, 2026 (v4)
v1 · Dec 11, 2025v2 · Apr 10, 2026v3 · Jun 2, 2026v4 · Aug 12, 2026
arXivHTMLPDF

Abstract

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.

Comments
12 pages, no figures

Related papers

Undecidability of the Unitary Hitting Time Problem: No Universal Time-Step Selector and an Operational No-Go for Finite-Time Decisions

Katsufumi Matsuura

•Jan 1, 2025•0 citations

Sigma-Time Quantum Dynamics I: Unitary BV-Clock Evolutions with Gates and Pulses

Ben F.T. Tibola

Quantum dynamics is usually written relative to a smooth external time parameter, while actual control schedules often contain waits, pulses, gates, resets, and event-like interventions. This paper develops the first unitary part of a sigma-time quantum dynamics framework. We define a bounded-Hamiltonian quantum evolution over a finite-horizon bounded-variation sigma clock with a continuous clock component, flat clock intervals, and a locally finite set of atom times carrying unitary gates. Under these hypotheses the sigma-chronological product exists, is unitary, composes as an evolution family, conserves wave-function norm, is strongly continuous away from atom times, and obeys a sharp atom/gate insertion law. We also prove a fixed-clock perturbation estimate and a bounded isolated-pulse corridor in which shrinking finite-width pulses converge in operator norm to declared atomic gates. The result is deliberately scoped: it does not claim an unbounded Schroedinger-operator theorem, a measurement theorem, an open-system theorem, or a Zeno limit theorem. A finite qubit benchmark with two bounded waits and one atomic gate is included as a reproducibility appendix and verifies unitary defect, trace preservation, Choi positivity, and output-state validity to machine precision

•May 28, 2026•0 citations

Undecidability in quantum thermalization

Naoto Shiraishi, Keiji Matsumoto

The investigation of thermalization in isolated quantum many-body systems has a long history, dating back to the time of developing statistical mechanics. Most quantum many-body systems in nature are considered to thermalize, while some never achieve thermal equilibrium. The central problem is to clarify whether a given system thermalizes, which has been addressed previously, but not resolved. Here, we show that this problem is undecidable. The resulting undecidability even applies when the system is restricted to one-dimensional shift-invariant systems with nearest-neighbour interaction, and the initial state is a fixed product state. We construct a family of Hamiltonians encoding dynamics of a reversible universal Turing machine, where the fate of a relaxation process changes considerably depending on whether the Turing machine halts. Our result indicates that there is no general theorem, algorithm, or systematic procedure determining the presence or absence of thermalization in any given Hamiltonian.

arXiv:2012.13889•Nature Communications•Aug 24, 2021•26 citations

Universality in quantum computation

Jennifer L. Dodd

A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers.        The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected.       This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate.       Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.

•Jan 1, 2004•7 citations

Hitting Statistics from Quantum Jumps

A. Chia, Tomasz Paterek, L. C. Kwek

We propose a definition of the hitting time for a model of continuous-time quantum walks based on quantum jumps and derive explicit expressions for its hitting statistics. This method works naturally for open quantum walks where incoherent transitions occur but can also be modified to cover the unitary case when incoherent transitions are absent.

Quantum Information and Measurement (QIM)•Jan 1, 2017•1 citation

A Projection-First Reframing of Information and Computation: Distinguishability, Channels, and Conditional Undecidability

Peter Nero

A projection can identify source states that an effective description no longer distinguishes. This observation is useful, but it is not by itself a theory of information, computation, complexity, or undecidability. Information quantities require a state or probability law and a specified channel; computation requires an encoding, evolution rule, readout, and resource model; undecidability requires an unbounded problem family and an explicit reduction from a known undecidable problem. This paper gives a projection-first account of these layers. Classical and quantum data-processing inequalities formalize loss of distinguishability under channels, while recovery maps state when the loss can be reversed on a selected family of states. Noninvertibility alone does not imply entropy production, an arrow of time, computational hardness, or undecidability. For Modal Triplet Theory, finite selected operators supply concrete descriptive channels, but a physical undecidability theorem remains open until a uniform computational embedding is constructed.

•Jan 15, 2026•0 citations
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.
Quantum dynamics is usually written relative to a smooth external time parameter, while actual control schedules often contain waits, pulses, gates, resets, and event-like interventions. This paper develops the first unitary part of a sigma-time quantum dynamics framework. We define a bounded-Hamiltonian quantum evolution over a finite-horizon bounded-variation sigma clock with a continuous clock component, flat clock intervals, and a locally finite set of atom times carrying unitary gates. Under these hypotheses the sigma-chronological product exists, is unitary, composes as an evolution family, conserves wave-function norm, is strongly continuous away from atom times, and obeys a sharp atom/gate insertion law. We also prove a fixed-clock perturbation estimate and a bounded isolated-pulse corridor in which shrinking finite-width pulses converge in operator norm to declared atomic gates. The result is deliberately scoped: it does not claim an unbounded Schroedinger-operator theorem, a measurement theorem, an open-system theorem, or a Zeno limit theorem. A finite qubit benchmark with two bounded waits and one atomic gate is included as a reproducibility appendix and verifies unitary defect, trace preservation, Choi positivity, and output-state validity to machine precision
The investigation of thermalization in isolated quantum many-body systems has a long history, dating back to the time of developing statistical mechanics. Most quantum many-body systems in nature are considered to thermalize, while some never achieve thermal equilibrium. The central problem is to clarify whether a given system thermalizes, which has been addressed previously, but not resolved. Here, we show that this problem is undecidable. The resulting undecidability even applies when the system is restricted to one-dimensional shift-invariant systems with nearest-neighbour interaction, and the initial state is a fixed product state. We construct a family of Hamiltonians encoding dynamics of a reversible universal Turing machine, where the fate of a relaxation process changes considerably depending on whether the Turing machine halts. Our result indicates that there is no general theorem, algorithm, or systematic procedure determining the presence or absence of thermalization in any given Hamiltonian.
A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers.        The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected.       This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate.       Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.
A projection can identify source states that an effective description no longer distinguishes. This observation is useful, but it is not by itself a theory of information, computation, complexity, or undecidability. Information quantities require a state or probability law and a specified channel; computation requires an encoding, evolution rule, readout, and resource model; undecidability requires an unbounded problem family and an explicit reduction from a known undecidable problem. This paper gives a projection-first account of these layers. Classical and quantum data-processing inequalities formalize loss of distinguishability under channels, while recovery maps state when the loss can be reversed on a selected family of states. Noninvertibility alone does not imply entropy production, an arrow of time, computational hardness, or undecidability. For Modal Triplet Theory, finite selected operators supply concrete descriptive channels, but a physical undecidability theorem remains open until a uniform computational embedding is constructed.