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 $Θ(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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.10682
curl -X POST /api/v1/records/arxiv/2605.10682/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.10682/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'