Looking for Pairs that Hard to Separate: A Quantum Approach

详细信息    查看全文

• 关键词：Quantum finite automaton ; Zero ; error ; Nondeterminism ; Succinctness ; Promise problems
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9705
• 期：1
• 页码：213-223
• 全文大小：197 KB
• 参考文献：1.Ambainis, A., Watrous, J.: Two-way finite automata with quantum and classical states. Theor. Comput. Sci. 287(1), 299–311 (2002)MathSciNet CrossRef MATH
  2.Ambainis, A., Yakaryılmaz, A.: Automata: from mathematics to applications. In: Automata and Quantum Computing (to appear). arXiv:​1507.​01988
  3.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
  4.Borel, A.: On free subgroups of semisimple groups. L’Enseignement Mathématique 29, 151–164 (1983)MathSciNet MATH
  5.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)CrossRef
  6.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
  7.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 MathSciNet CrossRef MATH
  8.Goralčík, P., Koubek, V.: On discerning words by automata. In: Kott, L. (ed.) Automata, Languages and Programming. LNCS, vol. 226. Springer, Heidelberg (1986)
  9.Hirvensalo, M.: Quantum automata with open time evolution. Int. J. Nat. Comput. 1(1), 70–85 (2010)CrossRef
  10.Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theor. Comput. Sci. 237(1–2), 275–306 (2000)MathSciNet CrossRef MATH
  11.Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information, 10th edn. Cambridge University Press, Cambridge (2010)CrossRef MATH
  12.Robson, J.M.: Separating strings with small automata. Inf. Process. Lett. 30(4), 209–214 (1989)MathSciNet CrossRef MATH
  13.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)
  14.Thom, A.: Convergent sequences in discrete groups. Can. Math. Bull. 56(2), 424–433 (2013). arXiv:​1003.​4093 MathSciNet CrossRef MATH
  15.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)
  16.Yakaryılmaz, A., Montoya, J.A.: On discerning strings with finite automata. In: 2015 Latin American Computing Conference, pp. 1–5. IEEE (2015)
  17.Yakaryılmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10(9&10), 747–770 (2010)MathSciNet MATH
  18.Yakaryılmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Inf. Comput. 279(6), 873–892 (2011)MathSciNet CrossRef MATH
  
• 作者单位：Aleksandrs Belovs (15)
  J. Andres Montoya (16)
  Abuzer Yakaryılmaz (17)
  
  15. CWI, Amsterdam, The Netherlands
  16. Universidad Nacional de Colombia, Bogotá, Colombia
  17. National Laboratory for Scientific Computing, Petrópolis, RJ, Brazil
  
• 丛书名：Implementation and Application of Automata
• ISBN：978-3-319-40946-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9705

文摘

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.