pith. sign in

arxiv: 2512.11006 · v3 · pith:NWLQ7QO6new · submitted 2025-12-11 · 🪐 quant-ph

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

Katsufumi Matsuura This is my paper

Pith reviewed 2026-05-16 23:36 UTC · model grok-4.3

classification 🪐 quant-ph
keywords undecidabilityunitary dynamicshitting timequantum evolutionhalting problemno-go theoremfinite resourcestime-dependent unitary
0
0 comments X

The pith

No algorithm exists that can output the hitting time for every computable quantum state and unitary evolution.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the Unitary Hitting Time Problem is undecidable. For any computably described initial state, target state, and time-dependent unitary, there is no general procedure that always returns the first time the evolved state reaches a given fidelity threshold. This follows from a direct reduction of the halting problem for Turing machines into unitary dynamics. The result also yields an operational no-go: no single finite-resource protocol can correctly decide these times across all inputs while respecting uniform bounds on observation time and on energy dissipation. The argument separates logical time inside the evolution equations from the physical time required to prepare, run, and measure the system.

Core claim

The total UHTP is undecidable: there is no algorithm that, given any computable pure states |a> and |b> together with a computable time-dependent unitary U(t), returns the infimum t > 0 at which the fidelity between U(t)|a> and |b> meets a fixed threshold (or infinity if the threshold is never met). The proof reduces the halting problem to this decision task by embedding reversible computation into unitary dynamics via a fixed-target beacon construction and lifting discrete steps to continuous time with piecewise-constant Hamiltonians. A companion no-go theorem shows that, for any fixed accuracy parameters, no universal protocol exists that outputs the hitting time for all inputs while using

What carries the argument

The Unitary Hitting Time Problem (UHTP) itself, defined as the infimum t where fidelity reaches a threshold, together with the reduction that embeds the halting problem into unitary evolution through reversible computation and a fixed-target beacon.

If this is right

  • No total algorithm can compute hitting times for all computably described inputs.
  • Universal time-step selection is impossible both logically and operationally.
  • For any fixed accuracy, no finite-resource protocol can decide hitting times while keeping observation time and dissipation uniformly bounded.
  • The distinction between logical time inside the equations and physical time of preparation and measurement blocks universal finite-time decisions.
  • The result complements existing undecidability proofs for spectral gaps and quantum-control reachability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Quantum simulators or control algorithms that presuppose a universal timing oracle will encounter inputs for which no finite procedure suffices.
  • Practical devices may need to switch to adaptive, input-dependent strategies rather than relying on a single bounded protocol.
  • Similar undecidability patterns could appear in approximate or noisy versions of the hitting-time task once the embedding of computation is preserved.
  • Designers of quantum algorithms should treat exact hitting times as non-computable in the worst case and plan for potentially unbounded verification resources.

Load-bearing premise

Unitary dynamics must be able to embed arbitrary reversible computations so that Turing-machine behavior can be simulated inside the quantum evolution.

What would settle it

An explicit algorithm that, for every computable triple of states |a>, |b> and unitary U(t), correctly returns the exact hitting time would falsify the undecidability claim.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines the Unitary Hitting Time Problem (UHTP) for computably described states |a>, |b> and time-dependent unitary U(t), where the hitting time is the infimum t > 0 at which fidelity reaches a fixed threshold (or infinity). It proves undecidability of the total UHTP by reduction from the halting problem, using embeddings of reversible computation into unitary evolution via a fixed-target beacon construction and piecewise-constant Hamiltonian lifting. It further establishes an operational no-go: no universal finite-resource protocol exists that outputs the hitting time for all such inputs while respecting uniform finite bounds on observation time and on dissipation/work. The work distinguishes logical time from physical/operational time and positions the results as complementing prior undecidability theorems for spectral gaps and quantum control reachability.

Significance. If the reduction and no-go hold, the result is significant: it demonstrates that no total algorithm or uniform finite-time protocol can compute hitting times across all computably describable unitary dynamics capable of embedding universal computation. This strengthens the landscape of undecidability results in quantum dynamics and control, with the explicit separation of logical versus physical time providing a useful operational framing. The construction appears to yield falsifiable predictions about the non-existence of bounded-time selectors.

major comments (2)
  1. [§3] §3 (Reduction construction): the claim that the fidelity threshold is crossed exactly at the logical halting step (and not earlier) under the piecewise-constant Hamiltonian lifting requires explicit verification that no intermediate fidelity crossings occur for non-halting or partial-computation trajectories; the current sketch leaves open whether the continuous-time embedding could produce spurious early hits for certain reversible embeddings.
  2. [§4] §4 (Operational no-go): the uniform finite upper bound on observation time is shown to fail for arbitrarily late halting instances, but the argument assumes the protocol must work for every computably described input; it is unclear whether the no-go still holds if the protocol is allowed to depend on a computable description of the input size or halting-time bound, which would weaken the operational interpretation.
minor comments (2)
  1. [§2] Notation for the fidelity threshold and the infimum definition should be stated once in a dedicated preliminary subsection rather than repeated inline.
  2. [Introduction] The abstract and introduction cite prior undecidability results on spectral gaps and reachability; add one or two explicit forward references to the relevant theorems in those works for direct comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below, indicating where we will revise the text for clarity and completeness.

read point-by-point responses

  1. Referee: [§3] §3 (Reduction construction): the claim that the fidelity threshold is crossed exactly at the logical halting step (and not earlier) under the piecewise-constant Hamiltonian lifting requires explicit verification that no intermediate fidelity crossings occur for non-halting or partial-computation trajectories; the current sketch leaves open whether the continuous-time embedding could produce spurious early hits for certain reversible embeddings.

    Authors: We agree that the sketch in §3 leaves the absence of spurious early crossings implicit rather than fully verified. In the revised manuscript we will insert a new lemma (Lemma 3.4) that explicitly proves, for both halting and non-halting instances, that the fidelity between the evolved state and the target beacon remains strictly below the threshold for all t less than the logical halting time. The argument relies on the orthogonality of the beacon states under the reversible embedding and on the fact that the piecewise-constant Hamiltonian only rotates within orthogonal subspaces until the halting step; intermediate partial-computation states therefore cannot produce overlap exceeding the threshold. We will also add a short paragraph discussing why the construction precludes early hits for the specific class of reversible embeddings used. revision: yes

  2. Referee: [§4] §4 (Operational no-go): the uniform finite upper bound on observation time is shown to fail for arbitrarily late halting instances, but the argument assumes the protocol must work for every computably described input; it is unclear whether the no-go still holds if the protocol is allowed to depend on a computable description of the input size or halting-time bound, which would weaken the operational interpretation.

    Authors: The no-go theorem is stated for protocols whose finite upper bound on observation time is uniform across all inputs and independent of any computable description of input size or halting-time bound. If a protocol is permitted to receive and use such an input-dependent bound, the uniformity requirement is relaxed and the no-go does not apply; such protocols may exist for restricted families of instances. Our result targets precisely the uniform case, which corresponds to a universal time-step selector that cannot presuppose knowledge of the computation length—an assumption that would itself be undecidable. We will revise the opening paragraph of §4 and the statement of Theorem 4.1 to make this scope explicit, thereby preserving the intended operational distinction between logical and physical time. revision: partial

Circularity Check

0 steps flagged

No significant circularity; reduction from halting problem is self-contained

full rationale

The central result is an explicit reduction from the known undecidable halting problem to UHTP, constructed via embedding reversible computation into unitary dynamics with a fixed-target beacon and piecewise-constant Hamiltonian lifting. This construction is defined directly in the paper without reducing to any fitted parameter, self-referential definition, or load-bearing self-citation. The no-go theorem follows directly from the reduction and uniform bounds, with no renaming of known results or ansatz smuggling. The derivation chain is independent and self-contained against external benchmarks like the halting problem.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard computability theory (halting problem) and the ability to embed reversible classical computation into unitary quantum dynamics; no free parameters or invented physical entities are introduced.

axioms (2)
  • standard math The halting problem for Turing machines is undecidable.
    Used as the source problem for the reduction to UHTP.
  • domain assumption Reversible computation can be embedded into unitary dynamics.
    Stated as the mechanism that lifts the halting problem into the quantum setting.

pith-pipeline@v0.9.0 · 5534 in / 1326 out tokens · 22087 ms · 2026-05-16T23:36:34.934396+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.