Algebraic Characterization of the Class of Languages Recognized by Measure Only Quantum Automata

• Autorzy: Comin C.

Identyfikatory

DOI

10.3233/FI-2014-1105

• Języki publikacji: EN

Abstrakty

EN

We study a model of one-way quantum automaton where only measurement operations are allowed (MON-1QFA). We give an algebraic characterization of LMO(Σ), showing that the syntactic monoids of the languages in LMO(Σ) are exactly the J-trivial literally idempotent syntactic monoids, where J is the Green’s relation determined by two-sided ideals. We also prove that LMO(Σ) coincides with the literal variety of literally idempotent piecewise testable languages. This allows us to prove the existence of a polynomial-time algorithm for deciding whether a regular language belongs to LMO(Σ).

Słowa kluczowe

EN

quantum automata; quantum measurement; syntactic monoids; piecewise testable languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 3/4
• Strony: 335--353
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Comin C.

• Dipartimento di Informatica, Università degli Studi di Milano, via Comelico 39/41, Milano, Italy

Bibliografia

• [1] A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M. Mercer, D. Thérien, Algebraic Results on Quantum Automata, Theory Comp. Syst., vol. 39(1), (2006), 165-188.
• [2] A. Bertoni, A. Brambilla, G. Mauri, N. Sabadini An application of the theory of free partially commutative monoids: asymptotic densities of trace languages, In: Proceedings of the 10th mathematical foundations of computer science. (1981) LNCS 118, Springer, 205-215.
• [3] A. Bertoni, M. Carpentieri, Regular Languages Accepted by Quantum Automata, Inf. Comput., vol. 165(2), (2001), 174-182.
• [4] A. Bertoni, C. Mereghetti, B. Palano, Quantum Computing: 1-Way Quantum Automata Developments in Language Theory 2003: 1-20.
• [5] A. Bertoni, C. Mereghetti, B. Palano, Trace monoids with idempotent generators and measure-only quantum automata, Natural Comp., vol. 9(2), (2010), 383-395.
• [6] A. Brodsky, N. Pippenger, Characterizations of 1-Way Quantum Finite Automata, SIAM J. Comput., vol. 31(5), (2002), 1456-1478.
• [7] V. Diekert, G. Rozenberg, The book of traces, (1995) World Scientific, Singapore.
• [8] S. Eilenberg, Automata, languages, and machines, vol. A, vol. B, Academic Press, 1976.
• [9] Z. Esik and M. Ito, Temporal logic with cyclic counting and the degree of aperiodicity in finite automata, Acta Cybernetica 16 (2003), 1-28.
• [10] Z. Esik and K.G. Larsen, Regular languages defined by Linström quantifiers, Theoretical Informatics and Applications 37 (2003), 197-242.
• [11] D. Gottesman , I. Chuang (1999) Quantum teleportation as a universal computational primitive. Nature 402:390393. arXiv:quant-ph/9908010.
• [12] J. Gruska, Quantum computing, (1999), McGraw-Hill.
• [13] J.E. Hopcroft, An N Log N Algorithm for Minimizing States in a Finite Automaton, Technical Report. Stanford University, Stanford, CA, USA, 1971.
• [14] H. Straubing, Finite automata, formal logic, and circuit complexity, Progress in Theoretical Computer Science, Birkhäuser Boston Inc., Boston, MA, 1994.
• [15] O. Klıma, L. Polák, On Varieties of Literally Idempotent Languages, ITA 42(3), (2008), 583-598.
• [16] M. Kunc, Equational description of pseudovarieties of homomorphisms, Theoretical Informatics and Applications 37 (2003), 243-254.
• [17] A. Kondacs, J. Watrous, On the Power of Quantum finite-state Automata, FOCS (1997) 66-75.
• [18] D. W. Leung (2004) Quantum computation by measurements, Int J Quant Inf 2:3343. arXiv:quant-ph/0310189, 2003.
• [19] Nielsen MA (2003) Quantum computation by measurement and quantum memory, Phys Lett A 308:96100. arXiv:quant-ph/0108020.
• [20] J. E. Pin, Varieties of formal languages, North Oxford, London and Plenum, New-York, 1986.
• [21] I. Simon, Piecewise testable events, Automata Theory and Formal Languages, (1975), Springer, Lecture Notes in Computer Science, vol 33.
• [22] H. Straubing, On logical descriptions of regular languages, Proc. Latin 2002, Springer Lecture Notes In Computer Science, Vol. 2286, 2002, 528-538.
• [23] A.N. Trahtman, Piecewise and Local Threshold Testability of DFA, FCT (2001), 347-358.