Geodesic
On finite automata with quantum and classical states
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 10 (2013), pp. 676-688.

Voir la notice de l'article provenant de la source Math-Net.Ru

Several quantum computational models were proposed in order to study how the quantum structure of matter could improve computational tasks. Among them, there are some that are based on finite automata, which are simpler computational devices, that helps to understand how a finite number of qubits could help to increase the power of the model. In this work, we study two-way finite automata with quantum and classical states (2QCFA), focusing on computability and complexity questions. We show results presented in the literature involving languages recognizability and closure properties and we then present some partial results on languages not recognized by the model.
Keywords: quantum automata, 2QCFA. 
@article{SEMR_2013_10_a39,
     author = {A. B. Grilo and A. V. Moura},
     title = {On finite automata with quantum and classical states},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {676--688},
     publisher = {mathdoc},
     volume = {10},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2013_10_a39/}
}
TY  - JOUR
AU  - A. B. Grilo
AU  - A. V. Moura
TI  - On finite automata with quantum and classical states
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2013
SP  - 676
EP  - 688
VL  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2013_10_a39/
LA  - en
ID  - SEMR_2013_10_a39
ER  - 
%0 Journal Article
%A A. B. Grilo
%A A. V. Moura
%T On finite automata with quantum and classical states
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2013
%P 676-688
%V 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2013_10_a39/
%G en
%F SEMR_2013_10_a39
A. B. Grilo; A. V. Moura. On finite automata with quantum and classical states. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 10 (2013), pp. 676-688. http://geodesic.mathdoc.fr/item/SEMR_2013_10_a39/

[1] M. Amano, K. Iwama, “Undecidability on quantum finite automata”, Proceedings of the thirty-first annual ACM symposium on Theory of computing, STOC'99 (New York, NY, USA, 1999), ACM, 368–375 | MR

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

[3] V. D. Blondel, E. Jeandel, P. Koiran, N. Portier, “Decidable and undecidable problems about quantum automata”, SIAM Journal on Computing, 34:5 (2005), 1464–1473 | MR | Zbl

[4] D. Deutsch, “Quantum theory, the {C}hurch–{T}uring principle and the universal quantum computer”, Proceedings of the Royal Society of London Ser. A, 400 (1985), 97–117 | MR | Zbl

[5] D. Deutsch, “Quantum computational networks”, Royal Society of London Proceedings Series A, 425 (1989), 73–90 | MR | Zbl

[6] Richard P. Feynman, “Simulating physics with computers”, International Journal of Theoretical Physics, 21:6–7 (1982), 467–488 | MR

[7] A. B. Grilo, A. V. Moura, “Language classes and quantum finite automata”, Proceedings of the IV Workshop-School in Quantum Computation and Information, WECIC'12, 2012, 90–95

[8] J. E. Hopcroft, J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley series in computer science, Addison-Wesley, 1999 | MR

[9] M. Huschenbett, Quantenautomaten und das cut-point-theorem for beschrinkte erkennbare potenzreihen, 2009

[10] A. Kondacs, J. Watrous, “On the power of quantum finite state automata”, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (Washington, DC, USA, 1997), IEEE Computer Society, 66

[11] M. Macko, On Closure Properties of Quantum Finite Automata, Ph. D. thesis, Comenius University, 2006

[12] C. Moore, J. P. Crutchfield, “Quantum automata and quantum grammars”, Theor. Comput. Sci., 237:1–2 (2000), 275–306 | MR | Zbl

[13] M. A. Nielsen, I. L. Chuang, Quantum computation and quantum information, Cambridge Series on Information and the Natural Sciences, Cambridge University Press, 2000 | MR | Zbl

[14] D. Qiu, “Some observations on two-way finite automata with quantum and classical states”, Proceedings of the 4th international conference on Intelligent Computing: Advanced Intelligent Computing Theories and Applications — with Aspects of Theoretical and Methodological Issues, ICIC'08, Springer-Verlag, Berlin–Heidelberg, 2008, 7–8

[15] S. C. Reghizzi, Formal Languages and Compilation, Texts in Computer Science, Springer, 2009 | Zbl

[16] D. Qiu, S. Zheng, L. Li, Some languages recognized by two-way finite automata with quantum and classical states, 2011 | MR

[17] D. Qiu, S. Zheng, L. Li, State succinctness of two-way finite automata with quantum and classical states, CoRR, , 2012 1202.2651 | MR

[18] M. Sipser, Introduction to the Theory of Computation, Thomson Course Technology, 2006 | Zbl

[19] Abuzer Yakaryilmaz, A. C. Cem Say, “Languages recognized by nondeterministic quantum finite automata”, Quantum Info. Comput., 10:9 (2010), 747–770 | MR | Zbl

[20] N. S. Yanofsky, M. A. Mannucci, Quantum computing for computer scientists, Cambridge University Press, 2008 | MR | Zbl