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:1102.3093 · NCMA

Superiority of one-way and realtime quantum machines and new directions

Abuzer Yakaryılmaz

Published Feb 15, 2011• 2 citations
arXivHTMLPDF

Abstract

In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.

DOI
10.48550/arxiv.1102.3093

Related papers

Superiority of one-way and realtime quantum machines

Abuzer Yakaryılmaz

In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.

RAIRO - Theoretical Informatics and Applications•Oct 1, 2012•20 citations

Empowering measures for quantum finite automata (QFA)

Soumya Debabrata Pani, Chandan Kumar Behera

The 1-way quantum finite automata and 2-way quantum finite automata are the first ever developed quantum automatons. But they suffer from many disadvantages which make them less powerful and impracticable. To remove these drawbacks there are many ways to modify and aggrandize the quantum finite automatons. Including 1-counter with 1-way QFA significantly improve its power. Likely quantum finite automata with quantum and classical states (QCFA) and 2-way quantum finite 1-counter automata (2-QF1-CA) are the quintessence of these modifications. In our paper we first discuss about 1-QFA and 2-QFA and their drawbacks. In the section IV we introduce an algorithm by implementing 1-way quantum finite k-counter automata (1-QFk-CA). Then we discuss another algorithm by implementing quantum finite 1-counter automata (QF1-CA) with multiple scanning of the input string. These algorithms improve the power of QFAs.

International Conference on Computer Research and Development•Mar 1, 2011•1 citation

New results on classical and quantum counter automata

Masaki Nakanishi, Abuzer Yakaryılmaz, Aida Gainutdinova

We show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation result between Las Vegas one-way probabilistic one-counter automaton and one-way deterministic one-counter automaton. We also obtain new results on classical counter automata regarding language recognition. It was conjectured that one-way probabilistic one blind-counter automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz: Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. and Applic. 46(4): 615-641 (2012)]. We show that this conjecture is false, and also show several separation results for blind/non-blind counter automata.

Discrete Mathematics & Theoretical Computer Science•Jul 13, 2016•1 citation

1-way quantum finite automata: strengths, weaknesses and generalizations

Andris Ambainis, Rūsiņš Freivalds

We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (greater than 7/9), then any 1-way QFAs can be simulated by a 1-way reversible automaton. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. We construct a 1-way QFA that is exponentially smaller than any equivalent classical (even randomized) finite automaton. We think that this construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.

arXiv:quant-ph/9802062•Annual Symposium on Foundations of Computer Science•Nov 27, 2002•220 citations

QUANTUM COUNTER AUTOMATA

A. C. Cem Say, Abuzer Yakaryılmaz

The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.

arXiv:1105.0165•International Journal of Foundations of Computer Science•Aug 1, 2012•11 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
In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.
The 1-way quantum finite automata and 2-way quantum finite automata are the first ever developed quantum automatons. But they suffer from many disadvantages which make them less powerful and impracticable. To remove these drawbacks there are many ways to modify and aggrandize the quantum finite automatons. Including 1-counter with 1-way QFA significantly improve its power. Likely quantum finite automata with quantum and classical states (QCFA) and 2-way quantum finite 1-counter automata (2-QF1-CA) are the quintessence of these modifications. In our paper we first discuss about 1-QFA and 2-QFA and their drawbacks. In the section IV we introduce an algorithm by implementing 1-way quantum finite k-counter automata (1-QFk-CA). Then we discuss another algorithm by implementing quantum finite 1-counter automata (QF1-CA) with multiple scanning of the input string. These algorithms improve the power of QFAs.
We show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation result between Las Vegas one-way probabilistic one-counter automaton and one-way deterministic one-counter automaton. We also obtain new results on classical counter automata regarding language recognition. It was conjectured that one-way probabilistic one blind-counter automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz: Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. and Applic. 46(4): 615-641 (2012)]. We show that this conjecture is false, and also show several separation results for blind/non-blind counter automata.
We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (greater than 7/9), then any 1-way QFAs can be simulated by a 1-way reversible automaton. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. We construct a 1-way QFA that is exponentially smaller than any equivalent classical (even randomized) finite automaton. We think that this construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.
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.