{"id":"arxiv/2605.10682","url":"https://arxiv.org/abs/2605.10682","tags":["quant-ph","cs.FL"],"score":0,"title":"On the Simulation Cost of Quantum Finite Automata","domain":"quant-ph","source":"arxiv","authors":["Zeyu Chen","Junde Wu"],"reviews":0,"subject":"quant-ph","summary":"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 $Θ(cq^2)$, while an $n$-dimensional measure-once one-way quantum finite automaton has worst-case cost $Θ(n^2)$. The proofs develop a prepare--test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-11","reactions":{}}