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:2003.09877 · Leibniz international proceedings in informatics

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

Zachary Remscrim

Published Mar 22, 2020• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.itcs.2021.39

Related papers

The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem

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 a single qubit, can recognize, with bounded error, the language $L_{eq}=\{a^m b^m :m \in \mathbb{N}\}$ in expected polynomial time and the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ in expected exponential time. We further demonstrate the power of 2QCFA by showing that they can recognize the word problems of many groups. In particular 2QCFA, with a single qubit and algebraic number transition amplitudes, can recognize, with bounded error, the word problem of any finitely generated virtually abelian group in expected polynomial time, as well as the word problems of a large class of linear groups in expected exponential time. This latter class (properly) includes all groups with context-free word problem. We also exhibit results for 2QCFA with any constant number of qubits. As a corollary, we obtain a direct improvement on the original Ambainis and Watrous result by showing that $L_{eq}$ can be recognized by a 2QCFA with better parameters. As a further corollary, we show that 2QCFA can recognize certain non-context-free languages in expected polynomial time. In a companion paper, we prove matching lower bounds, thereby showing that the class of languages recognizable with bounded error by a 2QCFA in expected $\mathit{subexponential}$ time is properly contained in the class of languages recognizable with bounded error by a 2QCFA in expected $\mathit{exponential}$ time.

arXiv:2003.09879•Leibniz international proceedings in informatics•Jan 1, 2020•2 citations

Classical and quantum computation with small space bounds (PhD thesis)

Abuzer Yakaryılmaz

In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many different cases. The main contributions are summarized below. Firstly, we consider QTMs in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by QTMs is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted QTMs; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic QTMs is given. Secondly, we consider constant space-bounded QTMs in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata (QFAs and PFAs, respectively,) with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way PFAs and two-way classical-head QFAs are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce PFAs and QFAs with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime QFAs augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight.

arXiv:1102.0378•Feb 2, 2011•5 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•1 citation

SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES

Shenggen Zheng, Daowen Qiu, Lvzhou Li

Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over two-way probabilistic finite automata (2PFA) for recognizing some non-regular languages such as the language Leq = {anbn ∣ n ∈ N} and the palindrome language Lpal = {w ∈ {a,b}* ∣ w=wR}, where xR is x in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language Lm = {xcy ∣ ∑ = {a,b,c},x,y ∈ {a,b}*, ∣x∣ = ∣y∣} that is similar to the middle language Lmiddle = {xay ∣ x,y ∈ {a,b}*, ∣x∣ = ∣y∣}. We prove that the language Lm show that Lm can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus Lm is another witness of the fact that 2QCFA are more powerful than their classical counterparts.

arXiv:1112.2844•International Journal of Foundations of Computer Science•Aug 1, 2012•13 citations

State succinctness of two-way finite automata with quantum and classical states

Shenggen Zheng, Daowen Qiu, Jozef Gruska +2 more

{\it Two-way quantum automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any $m\in {\mathbb{Z}}^+$ and any $ε<1/2$, we show that: {enumerate} there is a promise problem $A^{eq}(m)$ which can be solved by a 2QCFA with one-sided error $ε$ in a polynomial expected running time with a constant number (that depends neither on $m$ nor on $\varepsilon$) of quantum states and $\mathbf{O}(\log{\frac{1}ε)}$ classical states, whereas the sizes of the corresponding {\it deterministic finite automata} (DFA), {\it two-way nondeterministic finite automata} (2NFA) and polynomial expected running time {\it two-way probabilistic finite automata} (2PFA) are at least $2m+2$, $\sqrt{\log{m}}$, and $\sqrt[3]{(\log m)/b}$, respectively; there exists a language $L^{twin}(m)=\{wcw| w\in\{a,b\}^*\}$ over the alphabet $Σ=\{a,b,c\}$ which can be recognized by a 2QCFA with one-sided error $ε$ in an exponential expected running time with a constant number of quantum states and $\mathbf{O}(\log{\frac{1}ε)}$ classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least $2^m$, $\sqrt{m}$, and $\sqrt[3]{m/b}$, respectively; {enumerate} where $b$ is a constant.

arXiv:1202.2651•Feb 13, 2012•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•348 citations
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.
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 a single qubit, can recognize, with bounded error, the language Leq={ambm:m∈N}L_{eq}=\{a^m b^m :m \in \mathbb{N}\}Leq​={ambm:m∈N} in expected polynomial time and 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} in expected exponential time. We further demonstrate the power of 2QCFA by showing that they can recognize the word problems of many groups. In particular 2QCFA, with a single qubit and algebraic number transition amplitudes, can recognize, with bounded error, the word problem of any finitely generated virtually abelian group in expected polynomial time, as well as the word problems of a large class of linear groups in expected exponential time. This latter class (properly) includes all groups with context-free word problem. We also exhibit results for 2QCFA with any constant number of qubits. As a corollary, we obtain a direct improvement on the original Ambainis and Watrous result by showing that LeqL_{eq}Leq​ can be recognized by a 2QCFA with better parameters. As a further corollary, we show that 2QCFA can recognize certain non-context-free languages in expected polynomial time. In a companion paper, we prove matching lower bounds, thereby showing that the class of languages recognizable with bounded error by a 2QCFA in expected subexponential\mathit{subexponential}subexponential time is properly contained in the class of languages recognizable with bounded error by a 2QCFA in expected exponential\mathit{exponential}exponential time.
In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many different cases. The main contributions are summarized below. Firstly, we consider QTMs in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by QTMs is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted QTMs; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic QTMs is given. Secondly, we consider constant space-bounded QTMs in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata (QFAs and PFAs, respectively,) with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way PFAs and two-way classical-head QFAs are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce PFAs and QFAs with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime QFAs augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight.
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.
Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over two-way probabilistic finite automata (2PFA) for recognizing some non-regular languages such as the language Leq = {anbn ∣ n ∈ N} and the palindrome language Lpal = {w ∈ {a,b}* ∣ w=wR}, where xR is x in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language Lm = {xcy ∣ ∑ = {a,b,c},x,y ∈ {a,b}*, ∣x∣ = ∣y∣} that is similar to the middle language Lmiddle = {xay ∣ x,y ∈ {a,b}*, ∣x∣ = ∣y∣}. We prove that the language Lm show that Lm can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus Lm is another witness of the fact that 2QCFA are more powerful than their classical counterparts.
{\it Two-way quantum automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any m∈Z+m\in {\mathbb{Z}}^+m∈Z+ and any ε<1/2ε<1/2ε<1/2, we show that: {enumerate} there is a promise problem Aeq(m)A^{eq}(m)Aeq(m) which can be solved by a 2QCFA with one-sided error εεε in a polynomial expected running time with a constant number (that depends neither on mmm nor on ε\varepsilonε) of quantum states and O(log⁡1ε)\mathbf{O}(\log{\frac{1}ε)}O(logε1​) classical states, whereas the sizes of the corresponding {\it deterministic finite automata} (DFA), {\it two-way nondeterministic finite automata} (2NFA) and polynomial expected running time {\it two-way probabilistic finite automata} (2PFA) are at least 2m+22m+22m+2, log⁡m\sqrt{\log{m}}logm​, and (log⁡m)/b3\sqrt[3]{(\log m)/b}3(logm)/b​, respectively; there exists a language Ltwin(m)={wcw∣w∈{a,b}∗}L^{twin}(m)=\{wcw| w\in\{a,b\}^*\}Ltwin(m)={wcw∣w∈{a,b}∗} over the alphabet Σ={a,b,c}Σ=\{a,b,c\}Σ={a,b,c} which can be recognized by a 2QCFA with one-sided error εεε in an exponential expected running time with a constant number of quantum states and O(log⁡1ε)\mathbf{O}(\log{\frac{1}ε)}O(logε1​) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m2^m2m, m\sqrt{m}m​, and m/b3\sqrt[3]{m/b}3m/b​, respectively; {enumerate} where bbb is a constant.
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.