×

One-way probabilistic reversible and quantum one-counter automata. (English) Zbl 1061.68099

Summary: Kravtsev introduced 1-way quantum 1-counter automata (1Q1CAs), and showed that several non-context-free languages can be recognized by bounded error 1Q1CAs. In this paper, we first show that all of these non-context-free languages can be also recognized by bounded error 1PR1CAs (and so 1Q1CAs). Moreover, the accepting probability of each of these 1PR1CAs is strictly greater than, or at least equal to, that of corresponding Kravtsev’s original 1Q1CA. Second, we show that there exists a bounded error 1PR1CA (and so 1Q1CA) which recognizes \(\{a_{1}^{n}a_{2}^{n}\cdots a_{k}^{n}\}\), for each \(k\geqslant2\). We also show that, in a quantum case, we can improve the accepting probability in a strict sense by using quantum interference. Third, we state the relation between 1-way deterministic 1-counter automata (1D1CAs) and 1Q1CAs. On one hand, all of above mentioned languages cannot be recognized by 1D1CAs because they are non-context-free. On the other hand, we show that a regular language \(\{\{a,b\}^{*}a\}\) cannot be recognized by bounded error 1Q1CAs.

MSC:

68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ambainis, A.; Bonner, R.; Freivalds, R.; Kikusts, A., Probabilities to accept languages by quantum finite automata, (Proc. 5th Annu. Internat. Conf. on Computing and Combinatorics (COCOON’99), Lecture Notes in Computer Science, Vol. 1627 (1999), Springer: Springer Berlin), 174-183 · Zbl 0944.68118
[2] A. Ambainis, R. Freivalds, 1-way quantum finite automata: strengths, weakness and generalizations, in: Proc. 39th Annu. Symp. on Foundations of Computer Science, 1998, pp. 332-341.; A. Ambainis, R. Freivalds, 1-way quantum finite automata: strengths, weakness and generalizations, in: Proc. 39th Annu. Symp. on Foundations of Computer Science, 1998, pp. 332-341.
[3] A. Kondacs, J. Watrous, On the power of quantum finite state automata, in: Proc. 38th Annu. Symp. on Foundations of Computer Science, 1997, pp. 66-75.; A. Kondacs, J. Watrous, On the power of quantum finite state automata, in: Proc. 38th Annu. Symp. on Foundations of Computer Science, 1997, pp. 66-75.
[4] Kravtsev, M., Quantum finite one-counter automata, (Proc. 26th Conf. on Current Trends in Theory and Practice of Informatics (SOFSEM’99), Lecture Notes in Computer Science, Vol. 1725 (1999), Springer: Springer Berlin), 431-440 · Zbl 0970.81008
[5] Minsky, M. L., Recursive unsolvability of post’s problem of ‘tag’ and other topics in the theory of Turing machines, Ann. Math., 74, 3, 437-455 (1961) · Zbl 0105.00802
[6] C. Moore, J. Crutchfield, Quantum automata and quantum grammars, Technical Report, 97-07-02, Santa-Fe Institute Working Paper, also available at \tt http://xxx.lanl.gov/archive/quant-ph/9707031; C. Moore, J. Crutchfield, Quantum automata and quantum grammars, Technical Report, 97-07-02, Santa-Fe Institute Working Paper, also available at \tt http://xxx.lanl.gov/archive/quant-ph/9707031
[7] A. Nayak, Optimal lower bounds for quantum automata and random access codes, in: Proc. 40th Annu. Symp. on Foundations of Computer Science, 1999, pp. 369-376.; A. Nayak, Optimal lower bounds for quantum automata and random access codes, in: Proc. 40th Annu. Symp. on Foundations of Computer Science, 1999, pp. 369-376.
[8] P. Shor, Algorithms for quantum computation: discrete log and factoring, in: Proc. 35th Annu. Symp. on Foundations of Computer Science, 1994, pp. 56-65.; P. Shor, Algorithms for quantum computation: discrete log and factoring, in: Proc. 35th Annu. Symp. on Foundations of Computer Science, 1994, pp. 56-65.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.