On the Simulation Cost of Quantum Finite Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917480894562304 |
|---|---|
| author | Chen, Zeyu Wu, Junde |
| author_facet | Chen, Zeyu Wu, Junde |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10682 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Simulation Cost of Quantum Finite Automata Chen, Zeyu Wu, Junde Quantum Physics Formal Languages and Automata Theory 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 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. |
| title | On the Simulation Cost of Quantum Finite Automata |
| topic | Quantum Physics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2605.10682 |