On the Simulation Cost of Quantum Finite Automata

This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simulation laws for two representative models. A one-way finite automaton with $c$ classical states and a $q$-dimensional quantum register has exact probabilistic simulation cost $\mathrm{\Theta }(c{q}^2)$, while an $n$-dimensional measure-once one-way quantum finite automaton has worst-case cost $\mathrm{\Theta }(n^2)$. The proofs develop a prepare–test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests. The same obstruction is recast through finite sign-rank matrices, clarifying the role of Forster’s spectral method. Placed beside the surrounding two-way separations, these results give a clean hierarchy of finite-automata quantum advantage.