Abstract
Determining the minimum number of states required by a deterministic finite automaton to separate a given pair of different words (to accept one word and to reject the other) is an important challenge. In this paper, we ask the same question for quantum finite automata (QFAs). We classify such pairs as easy and hard ones. We show that 2-state QFAs with real amplitudes can separate any easy pair with zero-error but cannot separate some hard pairs even in nondeterministic acceptance mode. When using complex amplitudes, 2-state QFAs can separate any pair in nondeterministic acceptance mode, and here we conjecture that they can separate any pair also with zero-error. Then, we focus on (a more general problem) separating a pair of two disjoint finite set of words. We show that QFAs can separate them efficiently in nondeterministic acceptance mode, i.e., the number of states is two to the power of the size of the small set.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ambainis, A., Watrous, J.: Two-way finite automata with quantum and classical states. Theor. Comput. Sci. 287(1), 299–311 (2002)
Ambainis, A., Yakaryılmaz, A.: Automata: from mathematics to applications. In: Automata and Quantum Computing (to appear). arXiv:1507.01988
Belovs, A., Montoya, J.A., Yakaryılmaz, A.: Can one quantum bit separate any pair of words with zero-error? Technical report (2016). arXiv:1602.07967
Borel, A.: On free subgroups of semisimple groups. L’Enseignement Mathématique 29, 151–164 (1983)
Demaine, E.D., Eisenstat, S., Shallit, J., Wilson, D.A.: Remarks on separating words. In: Holzer, M. (ed.) DCFS 2011. LNCS, vol. 6808, pp. 147–157. Springer, Heidelberg (2011)
Díaz-Caro, A., Yakaryılmaz, A.: Affine computation and affine automaton. In: Computer Science - Theory and Applications. LNCS, vol. 9691, pp. 1–15. Springer (2016). arXiv:1602.04732
Elkasapy, A., Thom, A.: About Gotô’s method showing surjectivity of word maps. Indiana Univ. Math. J. 63(5), 1553–1565 (2014). arXiv:1207.5596
Goralčík, P., Koubek, V.: On discerning words by automata. In: Kott, L. (ed.) Automata, Languages and Programming. LNCS, vol. 226. Springer, Heidelberg (1986)
Hirvensalo, M.: Quantum automata with open time evolution. Int. J. Nat. Comput. 1(1), 70–85 (2010)
Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theor. Comput. Sci. 237(1–2), 275–306 (2000)
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information, 10th edn. Cambridge University Press, Cambridge (2010)
Robson, J.M.: Separating strings with small automata. Inf. Process. Lett. 30(4), 209–214 (1989)
Say, A.C.C., Yakaryılmaz, A.: Quantum finite automata: a modern introduction. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Gruska Festschrift. LNCS, vol. 8808, pp. 208–222. Springer, Heidelberg (2014)
Thom, A.: Convergent sequences in discrete groups. Can. Math. Bull. 56(2), 424–433 (2013). arXiv:1003.4093
Villagra, M., Yakaryılmaz, A.: Language recognition power and succintness of affine automata. In: Calude, C.S., Dinneen, M.J. (eds.) UCNC 2015. LNCS, vol. 9252. Springer, Heidelberg (2015)
Yakaryılmaz, A., Montoya, J.A.: On discerning strings with finite automata. In: 2015 Latin American Computing Conference, pp. 1–5. IEEE (2015)
Yakaryılmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10(9&10), 747–770 (2010)
Yakaryılmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Inf. Comput. 279(6), 873–892 (2011)
Acknowledgement
We thank Andreas Thom for the discussions on our conjecture and anonymous reviewers for their helpful comments. The first author acknowledges the support provided by FP7 FET Proactive project QALGO. The second author acknowledges the support provided by Universidad Nacional de Colombia project Hermes 32083. The third author acknowledges the support provided by CAPES, grant 88881.030338/2013-01. Moreover, some parts of the work were done while the third author was visiting Bogotá, Colombia in December 2014.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Belovs, A., Montoya, J.A., Yakaryılmaz, A. (2016). Looking for Pairs that Hard to Separate: A Quantum Approach. In: Han, YS., Salomaa, K. (eds) Implementation and Application of Automata. CIAA 2016. Lecture Notes in Computer Science(), vol 9705. Springer, Cham. https://doi.org/10.1007/978-3-319-40946-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-40946-7_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-40945-0
Online ISBN: 978-3-319-40946-7
eBook Packages: Computer ScienceComputer Science (R0)