Behaviours of Unary Quantum Automata

• Autorzy: Bianchi M.P. , Palano B.
• Języki publikacji: EN

Abstrakty

EN

We study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whether the induced event is d-periodic. These algorithms run in polynomial time whenever the MM-qfa given in input has complex amplitudes with rational components. We also characterize the recognition power of unary MM-qfa's, by proving that any unary regular language can be accepted by a MM-qfa with constant cut point and isolation. Yet, the amount of states of the resulting MM-qfa is linear in the size of the corresponding minimal dfa. We also single out families of unary regular languages for which the size of the accepting MM-qfa's can be exponentially decreased.

Słowa kluczowe

EN

quantum automata; periodic events; unary languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 1/2
• Strony: 1--15
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Bianchi M.P.

autor

Palano B.

• Dipartimento di Scienze dell'Informazione, Universita degli Studi di Milano, via Comelico 39, 20135 Milano, Italy.,

Bibliografia

• [1] A. V. AHO, J. E. HOPCROFT, J. D. ULLMAN. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
• [2] A. AMBAINIS, R. FREIVALDS. 1-way quantum finite automata: strengths, weaknesses and generalizations. In: Proc. 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1998, 332-342.
• [3] A. AMBAINIS, A. KIKUSTS, M. VALDATS. On the class of languages recognizable by 1-way quantum finite automata. In: Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science. LNCS 2010, Springer, 2001, 75-86.
• [4] A. AMBAINIS, A. NAYAK, A. TA-SHMA, U. VAZIRANI. Dense quantum coding and quantum finite automata. J. ACM 49 (2002), 496-511.
• [5] A. AMBAINIS, J. WATROUS. Two-way finite automata with quantum and classical states. Theoretical Computer Science 287 (2002), 299-311.
• [6] A. BERTONI, M. CARPENTIERI. Regular languages accepted by quantum automata. Information and Computation 165 (2001) 174-182.
• [7] A. BERTONI, C. MEREGHETTI, B. PALANO. Quantum computing: 1-way quantum automata. In: Proc. 7th International Conference on Developments in Language Theory. LNCS 2710, Springer, 2003, 1-20.
• [8] A. BERTONI, C. MEREGHETTI, B. PALANO, Small size quantum automata recognizing some regular languages. Theoretical Computer Science 340 (2005) 394-407.
• [9] V.D. BLONDEL, E. JEANDEL, P. KOIRAN, N. PORTIER. Decidable and undecidable problems about quantum automata. SIAM J. Comput. 34 (2005) 1464-1473.
• [10] A. BRODSKY, N. PIPPENGER. Characterizations of 1-way quantum finite automata. SIAM J. Computing 5 (2002) 1456-1478.
• [11] J. GRUSKA. Quantum Computing. McGraw-Hill, 1999.
• [12] J. GRUSKA. Descriptional complexity issues in quantum computing. J. Automata, Languages and Combinatorics 5 (2000) 191-218.
• [13] R.I.G. HUGHES. The Structure and Interpretation of Quantum Mechanics. Harvard University Press, Cambridge, MA, 1992.
• [14] J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 2001.
• [15] A. KONDACS, J. WATROUS. On the power of quantum finite state automata. In: Proc. 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1997, 66-75.
• [16] C. MOORE, J. CRUTCHFIELD. Quantum automata and quantum grammars. Theoretical Computer Science 237 (2000) 275-306.
• [17] C. MEREGHETTI, B. PALANO. Quantum automata for some multiperiodic languages. Theoretical Computer Science 387 (2007) 177-186.
• [18] I. NIVEN. Irrational numbers. Carus Monographs, Vol. 11, The Mathematical Association of America (distributed by John Wiley and Sons), 1956.
• [19] A. PAZ. Introduction to Probabilistic Automata. Academic Press, New York, London, 1971.
• [20] J.E. PIN. On languages accepted by finite reversible automata. In: Proc. 14th Int. Coll. Automata, Lang. And Prog. LNCS 267, Springer-Verlag, 1987, 237-249.
• [21] G. SHILOV. Linear Algebra. Prentice Hall, 1971. Reprinted by Dover, 1977.