Measure-Once Quantum Timed Automata
Abhisek Midya · HAL (Le Centre pour la Communication Scientifique Directe) · 2026
We introduce measure-once quantum timed automata (MO-QTA), extending measure-once quantum finite automata to timed words by incorporating Alur--Dill clocks, clock constraints, and reset operations. We show that this extension is nontrivial: the homomorphism property underlying the algebraic characterization of measure-once quantum finite automata generally fails once transitions depend on history-dependent clock valuations. We identify \emph{reset-completeness}, in which every transition resets every clock, as a condition restoring this property. For reset-complete MO-QTA, we prove, with no assumption on the transition group, that a timed language is recognized with bounded error if and only if it is a \emph{timed group language}, and that this is equivalent to recognition with zero error. We further establish closure under complement, union, intersection, and inverse symbol-relabeling timed homomorphisms; assuming a finite transition group, we additionally prove decidability of membership, emptiness, universality, and equivalence. We show that this decidability does not require reset-completeness: for \emph{general} MO-QTA with finite transition group, a product of the classical Alur--Dill region construction with the transition group establishes decidability of the same four problems. We further show that the most natural weakening of reset-completeness --- resetting at least one clock, rather than every clock, on each transition --- already fails to restore the algebraic characterization, indicating that reset-completeness cannot be relaxed casually.