Embedding measure-once quantum finite automata in the Feynman quantum computer model
C. Mereghetti, B. Palano, Dario Tamascelli · Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano) · 2026
We present an explicit embedding of measure-once quantum finite automata (MO-QFAs) into the Feynman quantum computer model.Given an MO-QFA, we construct the corresponding Feynman machine whose register encodes both the input word and the automaton state, while a cursor evolving under a Hamiltonian implements the sequential application of the automaton transition operators.The construction relies on nested SWITCH mechanisms that select transitions according to the input symbols.We prove that, for every MO-QFA and every input word, measuring the cursor in its final position yields exactly the quantum state reached by the automaton after processing the same input.Consequently, acceptance probabilities are preserved exactly, and every language recognized by an MO-QFA with cutpoint can be recognized within the Feynman framework with the same acceptance behavior.This establishes an explicit connection between discrete-time quantum computation and continuous-time, physically motivated Hamiltonian models.