The Quadratic State Cost of Classical Simulation of One-Way Quantum Finite Automata

Generalized finite automata (GFAs), probabilistic finite automata (PFAs), and one-way general quantum finite automata (1gQFA) recognize the same strict-cutpoint languages, but the state complexity of exact probabilistic simulation has remained unclear. This paper determines that worst-case cost exactly: every $n$-state 1gQFA admits exact strict-cutpoint simulation by a one-way PFA with $O(n^2)$ states, via the standard $n^2$-dimensional mixed-state linearization together with an explicit alphabet-preserving construction that converts each $k$-state GFA into a one-way PFA with at most $2k+6$ states; conversely, for every $n\ge 2$, there exists an $n$-state 1gQFA for which every equivalent one-way PFA requires at least $n^2-1$ states, obtained from a prepare–test construction and a Vapnik–Chervonenkis dimension argument. Hence the worst-case probabilistic state cost of exact strict-cutpoint simulation is $\mathrm{\Theta }(n^2)$.