Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.07058

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

Zeyu Chen, Junde Wu

Published Apr 8, 2026• 3 citations
arXivHTMLPDF

Abstract

Under strict cutpoints, probabilistic finite automata (PFAs) and one-way general quantum finite automata (1gQFAs) recognize the same stochastic languages, shifting the theoretical focus to the state cost required for a classical PFA to simulate a 1gQFA. For an $n$-state ($n\geq 2$) 1gQFA, the state cost upper bound of classical simulation was previously known to be $n^2+3$, while the lower bound remained an open problem widely conjectured to be quadratic. After establishing a well-defined notion of classical simulation, we improve the existing state cost upper bound from $n^2+3$ to $n^2+1$. Subsequently, we introduce the concepts of shattering and dynamic shattering, which are used to determine the memory required for a PFA to recognize a language. Using these techniques, we prove that the state cost lower bound of the simulation reaches $n^2+1$ over a four-letter alphabet. With the upper and lower bounds thus matching, the problem is fully resolved.

DOI
10.48550/arxiv.2604.07058

Related papers

On the Simulation Cost of Quantum Finite Automata

Zeyu Chen, Junde Wu

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.

quant-pharXiv:2605.10682•May 12, 2026•2 citations

Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines

Zachary Remscrim

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ with bounded error in expected time $2^{O(n)}$, on inputs of length $n$. We prove that their result essentially cannot be improved upon: a 2QCFA (of any size) cannot recognize $L_{pal}$ with bounded error in expected time $2^{o(n)}$. To our knowledge, this is the first example of a language that can be recognized with bounded error by a 2QCFA in exponential time but not in subexponential time. Moreover, we prove that a quantum Turing machine (QTM) running in space $o(\log n)$ and expected time $2^{n^{1-Ω(1)}}$ cannot recognize $L_{pal}$ with bounded error; again, this is the first lower bound of its kind. Far more generally, we establish a lower bound on the running time of any 2QCFA or $o(\log n)$-space QTM that recognizes any language $L$ in terms of a natural "hardness measure" of $L$. This allows us to exhibit a large family of languages for which we have asymptotically matching lower and upper bounds on the running time of any such 2QCFA or QTM recognizer.

arXiv:2003.09877•Leibniz international proceedings in informatics•Mar 22, 2020•7 citations

Quantum Finite Automata with One-Sided Unbounded Error

Abuzer Yakaryılmaz, A. C. Cem Say

Abstract. We prove that several variants of the quantum finite automaton (QFA) model are strictly superior to their probabilistic counterparts, in terms of both language recognition power and succinctness, in the onesided unbounded error setting. This is the first case where one-way QFA models have been shown to outperform the corresponding probabilistic automata in both these respects. We give a characterization of the class of languages recognized by these QFA’s with cutpoint 0, demonstrating that it is equal to the class of exclusive stochastic languages. We prove several closure properties of the related classes. 1

•Feb 12, 2009•2 citations

Implications of quantum automata for contextuality

Jibran Rashid, Abuzer Yakaryılmaz

We construct zero-error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded-error probabilistic finite automata (PFAs). Here is a summary of our results: - There is a promise problem solvable by an exact two-way QFA in exponential expected time, but not by any bounded-error sublogarithmic space probabilistic Turing machine (PTM). - There is a promise problem solvable by an exact two-way QFA in quadratic expected time, but not by any bounded-error $ o(\log \log n) $-space PTMs in polynomial expected time. The same problem can be solvable by a one-way Las Vegas (or exact two-way) QFA with quantum head in linear (expected) time. - There is a promise problem solvable by a Las Vegas realtime QFA, but not by any bounded-error realtime PFA. The same problem can be solvable by an exact two-way QFA in linear expected time but not by any exact two-way PFA. - There is a family of promise problems such that each promise problem can be solvable by a two-state exact realtime QFAs, but, there is no such bound on the number of states of realtime bounded-error PFAs solving the members this family. Our results imply that there exist zero-error quantum computational devices with a \emph{single qubit} of memory that cannot be simulated by any finite memory classical computational model. This provides a computational perspective on results regarding ontological theories of quantum mechanics \cite{Hardy04}, \cite{Montina08}. As a consequence we find that classical automata based simulation models \cite{Kleinmann11}, \cite{Blasiak13} are not sufficiently powerful to simulate quantum contextuality. We conclude by highlighting the interplay between results from automata models and their application to developing a general framework for quantum contextuality.

arXiv:1404.2761•Apr 10, 2014•14 citations

Time-space tradeoffs for two-way finite automata

Shenggen Zheng, Daowen Qiu, Jozef Gruska

We explore bounds of {\em time-space tradeoffs} in language recognition on {\em two-way finite automata} for some special languages. We prove: (1) a time-space tradeoff upper bound for recognition of the languages $L_{EQ}(n)$ on {\em two-way probabilistic finite automata} (2PFA): $TS={\bf O}(n\log n)$, whereas a time-space tradeoff lower bound on {\em two-way deterministic finite automata} is ${\bf Ω}(n^2)$, (2) a time-space tradeoff upper bound for recognition of the languages $L_{INT}(n)$ on {\em two-way finite automata with quantum and classical states} (2QCFA): $TS={\bf O}(n^{3/2}\log n)$, whereas a lower bound on 2PFA is $TS={\bf Ω}(n^2)$, (3) a time-space tradeoff upper bound for recognition of the languages $L_{NE}(n)$ on exact 2QCFA: $TS={\bf O}(n^{1.87} \log n)$, whereas a lower bound on 2PFA is $TS={\bf Ω}(n^2)$. It has been proved (Klauck, STOC'00) that the exact one-way quantum finite automata have no advantage comparing to classical finite automata in recognizing languages. However, the result (3) shows that the exact 2QCFA do have an advantage in comparison with their classical counterparts, which has been the first example showing that the exact quantum computing have advantage in time-space tradeoff comparing to classical computing. Usually, two communicating parties, Alice and Bob, are supposed to have an access to arbitrary computational power in {\em communication complexity} model that is used. Instead of that we will consider communication complexity in such a setting that two parties are using only finite automata and we prove in this setting that quantum automata are better than classical automata and also probabilistic automata are better than deterministic automata for some well known tasks.

arXiv:1507.01346•Jul 6, 2015•2 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•371 citations
Under strict cutpoints, probabilistic finite automata (PFAs) and one-way general quantum finite automata (1gQFAs) recognize the same stochastic languages, shifting the theoretical focus to the state cost required for a classical PFA to simulate a 1gQFA. For an nnn-state (n≥2n\geq 2n≥2) 1gQFA, the state cost upper bound of classical simulation was previously known to be n2+3n^2+3n2+3, while the lower bound remained an open problem widely conjectured to be quadratic. After establishing a well-defined notion of classical simulation, we improve the existing state cost upper bound from n2+3n^2+3n2+3 to n2+1n^2+1n2+1. Subsequently, we introduce the concepts of shattering and dynamic shattering, which are used to determine the memory required for a PFA to recognize a language. Using these techniques, we prove that the state cost lower bound of the simulation reaches n2+1n^2+1n2+1 over a four-letter alphabet. With the upper and lower bounds thus matching, the problem is fully resolved.
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 ccc classical states and a qqq-dimensional quantum register has exact probabilistic simulation cost Θ(cq2)Θ(cq^2)Θ(cq2), while an nnn-dimensional measure-once one-way quantum finite automaton has worst-case cost Θ(n2)Θ(n^2)Θ(n2). 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.
The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language Lpal={w∈{a,b}∗:w is a palindrome}L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}Lpal​={w∈{a,b}∗:w is a palindrome} with bounded error in expected time 2O(n)2^{O(n)}2O(n), on inputs of length nnn. We prove that their result essentially cannot be improved upon: a 2QCFA (of any size) cannot recognize LpalL_{pal}Lpal​ with bounded error in expected time 2o(n)2^{o(n)}2o(n). To our knowledge, this is the first example of a language that can be recognized with bounded error by a 2QCFA in exponential time but not in subexponential time. Moreover, we prove that a quantum Turing machine (QTM) running in space o(log⁡n)o(\log n)o(logn) and expected time 2n1−Ω(1)2^{n^{1-Ω(1)}}2n1−Ω(1) cannot recognize LpalL_{pal}Lpal​ with bounded error; again, this is the first lower bound of its kind. Far more generally, we establish a lower bound on the running time of any 2QCFA or o(log⁡n)o(\log n)o(logn)-space QTM that recognizes any language LLL in terms of a natural "hardness measure" of LLL. This allows us to exhibit a large family of languages for which we have asymptotically matching lower and upper bounds on the running time of any such 2QCFA or QTM recognizer.
Abstract. We prove that several variants of the quantum finite automaton (QFA) model are strictly superior to their probabilistic counterparts, in terms of both language recognition power and succinctness, in the onesided unbounded error setting. This is the first case where one-way QFA models have been shown to outperform the corresponding probabilistic automata in both these respects. We give a characterization of the class of languages recognized by these QFA’s with cutpoint 0, demonstrating that it is equal to the class of exclusive stochastic languages. We prove several closure properties of the related classes. 1
We construct zero-error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded-error probabilistic finite automata (PFAs). Here is a summary of our results: - There is a promise problem solvable by an exact two-way QFA in exponential expected time, but not by any bounded-error sublogarithmic space probabilistic Turing machine (PTM). - There is a promise problem solvable by an exact two-way QFA in quadratic expected time, but not by any bounded-error $ o(\log \log n) $-space PTMs in polynomial expected time. The same problem can be solvable by a one-way Las Vegas (or exact two-way) QFA with quantum head in linear (expected) time. - There is a promise problem solvable by a Las Vegas realtime QFA, but not by any bounded-error realtime PFA. The same problem can be solvable by an exact two-way QFA in linear expected time but not by any exact two-way PFA. - There is a family of promise problems such that each promise problem can be solvable by a two-state exact realtime QFAs, but, there is no such bound on the number of states of realtime bounded-error PFAs solving the members this family. Our results imply that there exist zero-error quantum computational devices with a \emph{single qubit} of memory that cannot be simulated by any finite memory classical computational model. This provides a computational perspective on results regarding ontological theories of quantum mechanics \cite{Hardy04}, \cite{Montina08}. As a consequence we find that classical automata based simulation models \cite{Kleinmann11}, \cite{Blasiak13} are not sufficiently powerful to simulate quantum contextuality. We conclude by highlighting the interplay between results from automata models and their application to developing a general framework for quantum contextuality.
We explore bounds of {\em time-space tradeoffs} in language recognition on {\em two-way finite automata} for some special languages. We prove: (1) a time-space tradeoff upper bound for recognition of the languages LEQ(n)L_{EQ}(n)LEQ​(n) on {\em two-way probabilistic finite automata} (2PFA): TS=O(nlog⁡n)TS={\bf O}(n\log n)TS=O(nlogn), whereas a time-space tradeoff lower bound on {\em two-way deterministic finite automata} is Ω(n2){\bf Ω}(n^2)Ω(n2), (2) a time-space tradeoff upper bound for recognition of the languages LINT(n)L_{INT}(n)LINT​(n) on {\em two-way finite automata with quantum and classical states} (2QCFA): TS=O(n3/2log⁡n)TS={\bf O}(n^{3/2}\log n)TS=O(n3/2logn), whereas a lower bound on 2PFA is TS=Ω(n2)TS={\bf Ω}(n^2)TS=Ω(n2), (3) a time-space tradeoff upper bound for recognition of the languages LNE(n)L_{NE}(n)LNE​(n) on exact 2QCFA: TS=O(n1.87log⁡n)TS={\bf O}(n^{1.87} \log n)TS=O(n1.87logn), whereas a lower bound on 2PFA is TS=Ω(n2)TS={\bf Ω}(n^2)TS=Ω(n2). It has been proved (Klauck, STOC'00) that the exact one-way quantum finite automata have no advantage comparing to classical finite automata in recognizing languages. However, the result (3) shows that the exact 2QCFA do have an advantage in comparison with their classical counterparts, which has been the first example showing that the exact quantum computing have advantage in time-space tradeoff comparing to classical computing. Usually, two communicating parties, Alice and Bob, are supposed to have an access to arbitrary computational power in {\em communication complexity} model that is used. Instead of that we will consider communication complexity in such a setting that two parties are using only finite automata and we prove in this setting that quantum automata are better than classical automata and also probabilistic automata are better than deterministic automata for some well known tasks.
In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.