On the power of two-way multihead quantum finite automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 1-2, pp. 19-35.

This paper introduces a variant of two-way quantum finite automata named two-way multihead quantum finite automata. A two-way quantum finite automaton is more powerful than classical two-way finite automata. However, the generalizations of two-way quantum finite automata have not been defined so far as compared to one-way quantum finite automata model. We have investigated the newly introduced automata from two aspects: the language recognition capability and its comparison with classical and quantum counterparts. It has been proved that a language which cannot be recognized by any one-way and multi-letter quantum finite automata can be recognized by two-way quantum finite automata. Further, it has been shown that a language which cannot be recognized by two-way quantum finite automata can be recognized by two-way multihead quantum finite automata with two heads. Furthermore, it has been investigated that quantum variant of two-way deterministic multihead finite automata takes less number of heads to recognize a language containing of all words whose length is a prime number.

DOI : 10.1051/ita/2018020
Classification : 81P68, 68Q05, 68Q10, 68Q12, 68Q45
Mots-clés : Two-way deterministic finite automata (2DFA), two-way reversible finite automata (2RFA), two-way deterministic multihead finite automata (DMFA), two-way reversible multihead finite automata (RMFA), two-way quantum finite automata (2QFA), two-way multihead quantum finite automata (2MQFA)
Bhatia, Amandeep Singh 1 ; Kumar, Ajay 1

1 
@article{ITA_2019__53_1-2_19_0,
     author = {Bhatia, Amandeep Singh and Kumar, Ajay},
     title = {On the power of two-way multihead quantum finite automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {19--35},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1-2},
     year = {2019},
     doi = {10.1051/ita/2018020},
     mrnumber = {3920825},
     zbl = {1418.81016},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2018020/}
}
TY  - JOUR
AU  - Bhatia, Amandeep Singh
AU  - Kumar, Ajay
TI  - On the power of two-way multihead quantum finite automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2019
SP  - 19
EP  - 35
VL  - 53
IS  - 1-2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2018020/
DO  - 10.1051/ita/2018020
LA  - en
ID  - ITA_2019__53_1-2_19_0
ER  - 
%0 Journal Article
%A Bhatia, Amandeep Singh
%A Kumar, Ajay
%T On the power of two-way multihead quantum finite automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2019
%P 19-35
%V 53
%N 1-2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2018020/
%R 10.1051/ita/2018020
%G en
%F ITA_2019__53_1-2_19_0
Bhatia, Amandeep Singh; Kumar, Ajay. On the power of two-way multihead quantum finite automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 1-2, pp. 19-35. doi : 10.1051/ita/2018020. http://www.numdam.org/articles/10.1051/ita/2018020/

[1] M. Amano and K. Iwama, Undecidability on quantum finite automata, in Proc. of the Thirty-first Annual ACM Symposium on Theory of Computing. ACM (1999) 368–375 | DOI | MR | Zbl

[2] A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical states. Theor. Comput. Sci. 287 (2002) 299–311 | DOI | MR | Zbl

[3] A. Belovs, A. Rosmanis and J. Smotrovs, Multi-letter reversible and quantum finite automata, in International Conference on Developments in Language Theory. Springer (2007) 60–71 | DOI | MR | Zbl

[4] A.S. Bhatia and A. Kumar, Modeling of RNA secondary structures using two-way quantum finite automata. Chaos, Solitons Fract. 116 (2018) 332–339 | DOI | MR | Zbl

[5] A.S. Bhatia and A. Kumar, Quantifying matrix product state. Quant. Inf. Process. 17 (2018) 41 | DOI | MR | Zbl

[6] R.P. Feynman, Simulating physics with computers. Int. J. Theor. Phys. 21 (1982) 467–488 | DOI | MR

[7] D. Ganguly and K.S. Ray, 2-tape 1-way quantum finite state automata. Preprint (2016) | arXiv

[8] D. Ganguly and K. Chatterjee, K.S. Ray, 1-way multihead quantum finite state automata. Appl. Math. 7 (2016) 1005 | DOI

[9] L.K. Grover, A fast quantum mechanical algorithm for database search, in Proc. of the Twenty-eighth Annual ACM Symposium on Theory of Computing. ACM (19960 212–219 | MR | Zbl

[10] S. Gudder, Quantum computers. Int. J. Theor. Phys. 39 (2000) 2151–2177 | DOI | MR | Zbl

[11] I. Hill Iii, Introduction to automata theory, languages, and computation, Addison Wesley, Boston, Ma (1979)

[12] M. Holzer and M. Kutrib, A. Malcher, Multi-head finite automata: Characterizations, concepts and open problems. Preprint (2009) | arXiv | MR | Zbl

[13] M. Holzer, M. Kutrib and A. Malcher, Complexity of multi-head finite automata: origins and directions. Theor. Comput. Sci. 412 (2011) 83–96 | DOI | MR | Zbl

[14] O.H. Ibarra, On two-way multihead automata. J. Comput. Syst. Sci. 7 (1973) 28–36 | DOI | MR | Zbl

[15] A. Kondacs and J. Watrous, On the power of quantum finite state automata, in 38th Annual Symposium on Foundations of Computer Science, 1997. IEEE (1997) 66–75

[16] M. Kunc and A. Okhotin, Reversible two-way finite automata over a unary alphabet. Technical Report 1024, Turku Centre for Computer Science (2011)

[17] M. Kutrib and A. Malcher, One-way reversible multi-head finite automata, in International Workshop on Reversible Computation. Springer (2012) 14–28 | MR | Zbl

[18] K.-J. Lange, P. Mckenzie and A. Tapp, Reversible space equals deterministic space. J. Comput. Syst. Sci. 60 (2000) 354–367 | DOI | MR | Zbl

[19] L. Li and D. Qiu, Determination of equivalence between quantum sequential machines. Theor. Comput. Sci. 358 (2006) 65–74 | DOI | MR | Zbl

[20] L. Li, D. Qiu, Determining the equivalence for one-way quantum finite automata. Theor. Comput. Sci. 403 (2008) 42–51 | DOI | MR | Zbl

[21] L. Li, D. Qiu, X. Zou, L. Li, L. Wu and P. Mateus, Characterizations of one-way general quantum finite automata. Theor. Comput. Sci. 419 (2012) 73–91 | DOI | MR | Zbl

[22] P. Mateus, D. Qiu and L. Li, On the complexity of minimizing probabilistic and quantum automata. Inf. Comput. 218 (2012) 36–53 | DOI | MR | Zbl

[23] B. Monien, Two-way multihead automata over a one-letter alphabet. RAIRO: ITA 14 (1980) 67–82 | Numdam | MR | Zbl

[24] C. Moore and J.P. Crutchfield, Quantum automata and quantum grammars. Theor. Comput. Sci. 237 (2000) 275–306 | DOI | MR | Zbl

[25] K. Morita, Two-way reversible multi-head finite automata. Fund. Inf. 110 (2011) 241–254 | MR | Zbl

[26] K. Morita, A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads, in International Workshop on Reversible Computation. Springer (2012) 29–43 | MR | Zbl

[27] M.A. Nielsen and I.L. Chuang, Quantum computation and quantum information. Cambridge University Press (2010) | Zbl

[28] D. Qiu, Characterization of sequential quantum machines. Int. J. Theor. Phys. 41 (2002) 811–822 | DOI | MR | Zbl

[29] D. Qiu and S. Yu, Hierarchy and equivalence of multi-letter quantum finite automata. Theor. Comput. Sci. 410 (2009) 3006–3017 | DOI | MR | Zbl

[30] D. Qiu and M. Ying, Characterizations of quantum automata. Theor. Comput. Sci. 312 (2004) 479–489 | DOI | MR | Zbl

[31] D. Qiu, L. Li, X. Zou, P. Mateus and J. Gruska, Multi-letter quantum finite automata: decidability of the equivalence and minimization of states. Acta Tnf. 48 (2011) 271 | MR | Zbl

[32] D. Qiu, L. Li, P. Mateus and A. Sernadas, Exponentially more concise quantum recognition of non-RMM regular languages. J. Comput. Syst. Sci. 81 (2015) 359–375 | DOI | MR | Zbl

[33] M.O. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Dev. 3 (1959) 114–125 | DOI | MR | Zbl

[34] A.L. Rosenberg, On multi-head finite automata. IBM J. Res. Dev. 10 (1966) 388–394 | DOI | MR | Zbl

[35] P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in 35th Annual Symposium on Foundations of Computer Science. IEEE (1994) 124–134 | DOI | MR

[36] I.H. Sudborough, Bounded-reversal multihead finite automata languages. Inf. Cont. 25 (1974) 317–328 | DOI | MR | Zbl

[37] Two-Way Deterministic Finite Automata. Available at: https://en.wikipedia.org/wiki/two-way˙deterministic˙finite˙automaton (2017)

[38] J. Wang, Handbook of Finite State Based Models and Applications. CRC Press (2012) | MR | Zbl

[39] S. Zheng, L. Li, D. Qiu and J. Gruska, Promise problems solved by quantum and classical finite automata. Theor. Comput. Sci. 666 (2017) 48–64 | DOI | MR | Zbl

[40] S. Zheng, D. Qiu and J. Gruska, Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata. Inf. Comput. 241 (2015) 197–214 | DOI | MR | Zbl

[41] S. Zheng, L. Li and D. Qiu, Two-tape finite automata with quantum and classical states. Int. J. Theor. Phys. 50 (2011) 1262–1281 | DOI | MR | Zbl

[42] S. Zheng, D. Qiu and L. Li, Some languages recognized by two-way finite automata with quantum and classical states. Int. J. Found. Comput. Sci. 23 (2012) 1117–1129 | DOI | MR | Zbl

[43] S. Zheng, J. Gruska and D. Qiu, On the state complexity of semi-quantum finite automata. RAIRO: ITA 48 (2014) 187–207 | Numdam | MR | Zbl

[44] S. Zheng, D. Qiu, J. Gruska, L. Li and P. Mateus, State succinctness of two-way finite automata with quantum and classical states. Theor. Comput. Sci. 499 (2013) 98–112 | DOI | MR | Zbl

Cité par Sources :