Two-way nondeterministic finite automata with quantum and classical states and their limits
Jingnan Xie, Ching-Sheng Lin, Harry B. Hunt
Two-way finite automata with quantum and classical states (2QCFA’s), introduced by Ambainis and Watrous, extend deterministic two-way finite automata with a constant-size quantum register and provide a natural hybrid model of computation. In this paper, we introduce two-way nondeterministic finite automata with quantum and classical states (2QCNFA’s), extending this framework to the nondeterministic setting. We show that 2QCNFA’s are closed under union, intersection, and marked concatenation, and that they can recognize certain comparison languages whose status for 2QCFA’s remains open. We further initiate the study of decision problems for this model by proving that 2QCNFA’s can recognize the set of invalid computations of a deterministic Turing machine, which implies that the universality problem is undecidable. In addition, we investigate descriptional complexity, showing that there is no approximation algorithm for minimization between 2QCNFA’s and classical models such as DFA’s and context-free grammars, and that the corresponding trade-offs are non-recursive.
Information and Computation•Jun 25, 2026•0 citations