Quantum finite automata with control language

Mereghetti, Carlo; Palano, Beatrice

doi:10.1051/ita:2006007

Mereghetti, Carlo ; Palano, Beatrice

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 315-332.

Résumé

Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1-20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e., to have less states) than the corresponding classical (deterministic) automata.

EuDML MR Zbl

DOI : 10.1051/ita:2006007

Classification : 68Q10, 68Q19, 68Q45
Mots-clés : quantum computing, quantum finite automata

@article{ITA_2006__40_2_315_0,
     author = {Mereghetti, Carlo and Palano, Beatrice},
     title = {Quantum finite automata with control language},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {315--332},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {2},
     year = {2006},
     doi = {10.1051/ita:2006007},
     mrnumber = {2252642},
     zbl = {1112.68064},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita:2006007/}
}

TY  - JOUR
AU  - Mereghetti, Carlo
AU  - Palano, Beatrice
TI  - Quantum finite automata with control language
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 315
EP  - 332
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita:2006007/
DO  - 10.1051/ita:2006007
LA  - en
ID  - ITA_2006__40_2_315_0
ER  -

%0 Journal Article
%A Mereghetti, Carlo
%A Palano, Beatrice
%T Quantum finite automata with control language
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 315-332
%V 40
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita:2006007/
%R 10.1051/ita:2006007
%G en
%F ITA_2006__40_2_315_0

Mereghetti, Carlo; Palano, Beatrice. Quantum finite automata with control language. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 315-332. doi : 10.1051/ita:2006007. https://www.numdam.org/articles/10.1051/ita:2006007/

Bibliographie
Cité par

[1] A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M. Mercer and D. Thérien, Algebraic Results on Quantum Automata. Theory Comput. Syst. 39 (2006) 165-188. | Zbl

[2] A. Ambainis and 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 and 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. Lect. Notes Comput. Sci. 2010 (2001) 305-316. | Zbl

[4] A. Bertoni and M. Carpentieri, Regular languages accepted by quantum automata. Inform. Comput. 165 (2001) 174-182. | Zbl

[5] A. Bertoni, C. Mereghetti and B. Palano, Quantum computing: 1-way quantum automata, in Proc. 7th International Conference on Developments in Language Theory. Lect. Notes Comput. Sci. 2710 (2003) 1-20. | Zbl

[6] A. Bertoni, C. Mereghetti and B. Palano, Golomb Rulers and Difference Sets for Succinct Quantum Automata. Int. J. Found. Comp. Sci. 14 (2003) 871-888. | Zbl

[7] A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theoret. Comput. Sci. 340 (2005) 394-407. | Zbl

[8] A. Bertoni, C. Mereghetti and B. Palano, Some formal tools for analyzing quantum automata. Theoret. Comput. Sci. 356 (2006) 14-25.

[9] A. Brodsky and N. Pippenger, Characterizations of 1-Way Quantum Finite Automata. SIAM J. Comput. 5 (2002) 1456-1478. | Zbl

[10] M. Golovkins and M. Kravtsev, Probabilistic Reversible Automata and Quantum Automata, in Proc. 8th International Computing and Combinatorics Conference. Lect. Notes Comput. Sci. 2387 (2002) 574-583. | Zbl

[11] J. Gruska, Quantum Computing. McGraw-Hill (1999). | MR

[12] J. Gruska, Descriptional complexity issues in quantum computing. J. Automata, Languages and Combinatorics 5 (2000) 191-218. | Zbl

[13] J. Hopcroft and J. Ullman, Formal Languages and Their Relation to Automata. Addison-Wesley (1969). | MR | Zbl

[14] A. Kondacs and 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.

[15] C. Moore and J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci. 237 (2000) 275-306. | Zbl

[16] M. Marcus and H. Minc, Introduction to Linear Algebra. The Macmillan Company (1965). Reprinted by Dover (1988). | MR | Zbl

[17] M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities. Prindle, Weber & Schmidt (1964). Reprinted by Dover (1992). | MR | Zbl

[18] C. Mereghetti and B. Palano, On the Size of One-way Quantum Finite Automata with periodic behaviors. RAIRO-Inf. Theor. Appl. 36 (2002) 277-291. | EuDML | Numdam | Zbl

[19] C. Mereghetti, B. Palano and G. Pighizzini, Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO-Inf. Theor. Appl. 35 (2001) 477-490. | EuDML | Numdam | Zbl

[20] A. Nayak, Optimal lower bounds for quantum automata and random access codes, in Proc. 40th Symposium on Foundations of Computer Science (1999) 369-376. | MR

[21] J.E. Pin, On Languages Accepted by finite reversible automata, in Proc. 14th Int. Coll. Automata, Languages and Programming. Lect. Notes Comput. Sci. 267 (1987) 237-249. | MR | Zbl

Díaz-Caro, Alejandro; Villagra, Marcos Classically time-controlled quantum automata: definition and properties, The Computer Journal, Volume 68 (2025) no. 1, p. 23 | DOI:10.1093/comjnl/bxae089
Mereghetti, Carlo; Palano, Beatrice; Raucci, Priscilla Unary Quantum Finite State Automata with Control Language, Applied Sciences, Volume 14 (2024) no. 4, p. 1490 | DOI:10.3390/app14041490
Huang, Feidan Decompositions of average probability uninitialized sequential quantum machines, Soft Computing, Volume 26 (2022) no. 13, p. 5965 | DOI:10.1007/s00500-022-07063-2
Mereghetti, Carlo; Palano, Beatrice Guest Column, ACM SIGACT News, Volume 52 (2021) no. 3, p. 38 | DOI:10.1145/3494656.3494666
Mereghetti, Carlo; Palano, Beatrice; Cialdi, Simone; Vento, Valeria; Paris, Matteo G. A.; Olivares, Stefano Photonic realization of a quantum finite automaton, Physical Review Research, Volume 2 (2020) no. 1 | DOI:10.1103/physrevresearch.2.013089
Huang, Feidan On Coverings of Products of Uninitialized Sequential Quantum Machines, International Journal of Theoretical Physics, Volume 58 (2019) no. 5, p. 1418 | DOI:10.1007/s10773-019-04031-9
Bianchi, Maria Paola; Mereghetti, Carlo; Palano, Beatrice Quantum finite automata: Advances on Bertoni's ideas, Theoretical Computer Science, Volume 664 (2017), p. 39 | DOI:10.1016/j.tcs.2016.01.045
Li, Lvzhou; Qiu, Daowen Lower bounds on the size of semi-quantum finite automata, Theoretical Computer Science, Volume 623 (2016), p. 75 | DOI:10.1016/j.tcs.2015.09.031
Zheng, Shenggen; Qiu, Daowen; Gruska, Jozef Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata, Information and Computation, Volume 241 (2015), p. 197 | DOI:10.1016/j.ic.2015.02.003
Bianchi, Maria Paola; Mereghetti, Carlo; Palano, Beatrice On the Power of One-Way Automata with Quantum and Classical States, International Journal of Foundations of Computer Science, Volume 26 (2015) no. 07, p. 895 | DOI:10.1142/s0129054115400055
Qiu, Daowen; Li, Lvzhou; Mateus, Paulo; Sernadas, Amilcar Exponentially more concise quantum recognition of non-RMM regular languages, Journal of Computer and System Sciences, Volume 81 (2015) no. 2, p. 359 | DOI:10.1016/j.jcss.2014.06.008
Li, Lvzhou; Feng, Yuan On hybrid models of quantum finite automata, Journal of Computer and System Sciences, Volume 81 (2015) no. 7, p. 1144 | DOI:10.1016/j.jcss.2015.01.001
Bianchi, Maria Paola; Mereghetti, Carlo; Palano, Beatrice Complexity of Promise Problems on Classical and Quantum Automata, Computing with New Resources, Volume 8808 (2014), p. 161 | DOI:10.1007/978-3-319-13350-8_12
Bianchi, Maria Paola; Mereghetti, Carlo; Palano, Beatrice On the Power of One-Way Automata with Quantum and Classical States, Implementation and Application of Automata, Volume 8587 (2014), p. 84 | DOI:10.1007/978-3-319-08846-4_6
Bianchi, Maria Paola; Mereghetti, Carlo; Palano, Beatrice Size lower bounds for quantum automata, Theoretical Computer Science, Volume 551 (2014), p. 102 | DOI:10.1016/j.tcs.2014.07.004
Zheng, Shenggen; Qiu, Daowen; Gruska, Jozef; Li, Lvzhou; Mateus, Paulo State succinctness of two-way finite automata with quantum and classical states, Theoretical Computer Science, Volume 499 (2013), p. 98 | DOI:10.1016/j.tcs.2013.06.005
Bianchi, Maria Paola; Mereghetti, Carlo; Palano, Beatrice Size Lower Bounds for Quantum Automata, Unconventional Computation and Natural Computation, Volume 7956 (2013), p. 19 | DOI:10.1007/978-3-642-39074-6_4
Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice Descriptional Complexity of Pushdown Store Languages, Descriptional Complexity of Formal Systems, Volume 7386 (2012), p. 209 | DOI:10.1007/978-3-642-31623-4_16
Zheng, Shenggen; Qiu, Daowen; Li, Lvzhou; Gruska, Jozef One-Way Finite Automata with Quantum and Classical States, Languages Alive, Volume 7300 (2012), p. 273 | DOI:10.1007/978-3-642-31644-9_19
Li, Lvzhou; Qiu, Daowen; Zou, Xiangfu; Li, Lvjun; Wu, Lihua; Mateus, Paulo Characterizations of one-way general quantum finite automata, Theoretical Computer Science, Volume 419 (2012), p. 73 | DOI:10.1016/j.tcs.2011.10.021
Gruska, Jozef Algebraic Methods in Quantum Informatics, Algebraic Informatics, Volume 4728 (2007), p. 87 | DOI:10.1007/978-3-540-75414-5_6

Cité par 21 documents. Sources : Crossref