{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:46:04Z","timestamp":1756572364695,"version":"3.40.5"},"reference-count":73,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:italic>Learning finite automata<\/jats:italic> (termed as <jats:italic>model learning<\/jats:italic>) has become an important field in machine learning and has been useful realistic applications. Quantum finite automata (QFA) are simple models of quantum computers with finite memory. Due to their simplicity, QFA have well physical realizability, but one-way QFA still have essential advantages over classical finite automata with regard to state complexity (two-way QFA are more powerful than classical finite automata in computation ability as well). As a different problem in <jats:italic>quantum learning theory<\/jats:italic> and <jats:italic>quantum machine learning<\/jats:italic>, in this paper, our purpose is to initiate the study of <jats:italic>learning QFA with queries<\/jats:italic> (naturally it may be termed as <jats:italic>quantum model learning<\/jats:italic>), and the main results are regarding learning two basic one-way QFA (1QFA): (1) we propose a learning algorithm for measure-once 1QFA (MO-1QFA) with query complexity of polynomial time and (2) we propose a learning algorithm for measure-many 1QFA (MM-1QFA) with query complexity of polynomial time, as well.<\/jats:p>","DOI":"10.1017\/s0960129523000373","type":"journal-article","created":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T08:24:59Z","timestamp":1701332699000},"page":"128-146","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Learning quantum finite automata with queries"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1275-7599","authenticated-orcid":false,"given":"Daowen","family":"Qiu","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,11,30]]},"reference":[{"key":"S0960129523000373_ref11","doi-asserted-by":"crossref","unstructured":"Ambainis, A. and Yakaryilmaz, A. (2021). Automata and quantum computing. In: Pin, J.-E. (ed.) Handbook of Automata Theory (II), 1457\u20131493. arXiv:1507.01988.","DOI":"10.4171\/automata-2\/17"},{"key":"S0960129523000373_ref27","doi-asserted-by":"publisher","DOI":"10.26421\/QIC12.7-8-3"},{"volume-title":"Computational Methods of Linear Algebra","year":"1963","author":"Faddeev","key":"S0960129523000373_ref26"},{"key":"S0960129523000373_ref65","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704412910"},{"key":"S0960129523000373_ref7","unstructured":"Angluin, D. , Eisenstat, S. and Fisman, D. 2015. Learning regular languages via alternating automata. In: Proceeding of the 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, AAAI Press, 3308\u20133314."},{"key":"S0960129523000373_ref43","first-page":"129","article-title":"Gedanken-experiments on sequential machines","volume":"34","author":"Moore","year":"1956","journal-title":"Automata Studies, Annals of Mathematics Studies"},{"key":"S0960129523000373_ref24","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/18\/7\/073011"},{"key":"S0960129523000373_ref57","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.06.008"},{"key":"S0960129523000373_ref23","doi-asserted-by":"publisher","DOI":"10.1038\/nature23474"},{"key":"S0960129523000373_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.03.001"},{"key":"S0960129523000373_ref68","doi-asserted-by":"crossref","unstructured":"T\u00eerna\u02d8uca\u02d8, C. and Knuutila, T. (2007). Polynomial time algorithms for learning k-reversible languages and pattern languages with correction queries. In: Hutter, M. , Servedio, R. , and Takimoto, E. (eds.) Algorithmic Learning Theory: 18th International Conference, ALT\u2019 2007, Lecture Notes in Artificial Intelligence, vol. 4754, Springer-Verlag, 272\u2013284.","DOI":"10.1007\/978-3-540-75225-7_23"},{"key":"S0960129523000373_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.01.003"},{"key":"S0960129523000373_ref31","doi-asserted-by":"publisher","DOI":"10.1126\/science.abn7293"},{"key":"S0960129523000373_ref55","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.026"},{"key":"S0960129523000373_ref69","doi-asserted-by":"publisher","DOI":"10.1145\/2967606"},{"key":"S0960129523000373_ref70","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.109.050505"},{"key":"S0960129523000373_ref45","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.4.010328"},{"key":"S0960129523000373_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1263-x"},{"key":"S0960129523000373_ref63","doi-asserted-by":"publisher","DOI":"10.1080\/00107514.2014.964942"},{"key":"S0960129523000373_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0099-2"},{"key":"S0960129523000373_ref48","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.2.013089"},{"key":"S0960129523000373_ref25","doi-asserted-by":"publisher","DOI":"10.26421\/QIC16.7-8-4"},{"key":"S0960129523000373_ref61","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"S0960129523000373_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322334"},{"key":"S0960129523000373_ref54","first-page":"225","article-title":"Black box checking","volume":"7","author":"Peled","year":"2002","journal-title":"Journal of Automata Languages and Combinatorics"},{"key":"S0960129523000373_ref62","first-page":"045016","article-title":"A comparative study of different machine learning methods for dissipative quantum dynamics","volume":"3","author":"Rodriguez","year":"2022","journal-title":"Machine Learning: Science and Technology"},{"key":"S0960129523000373_ref37","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646094"},{"key":"S0960129523000373_ref8","unstructured":"Ambainis, A. and Freivalds, R. (1998). One-way quantum finite automata: Strengths, weaknesses and generalizations. In: Proceeding of the 39th Foundations of Computer Science, FOCS 1998, IEEE Computer Society Press, 332\u2013341."},{"key":"S0960129523000373_ref15","unstructured":"Bhatia, A. S. and Kumar, A. (2019). Quantum Finite Automata: Survey, Status and Research Directions, arXiv:1901.07992v1."},{"key":"S0960129523000373_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23021-4_1"},{"key":"S0960129523000373_ref10","first-page":"1","article-title":"Optimal quantum sample complexity of learning algorithms","volume":"19","author":"Arunachalam","year":"2018","journal-title":"Journal of Machine Learning Research"},{"key":"S0960129523000373_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979326091X"},{"key":"S0960129523000373_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45007-6_1"},{"key":"S0960129523000373_ref36","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"S0960129523000373_ref67","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-019-0163-x"},{"key":"S0960129523000373_ref32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"S0960129523000373_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"S0960129523000373_ref47","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.2.013089"},{"key":"S0960129523000373_ref73","doi-asserted-by":"publisher","DOI":"10.1007\/s42484-019-00004-7"},{"key":"S0960129523000373_ref58","unstructured":"Qiu, D. W. , Luo, L. and Xiao, L. (2022). Distributed Grover\u2019s Algorithm, arXiv:2204.10487v4."},{"key":"S0960129523000373_ref20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799353443"},{"key":"S0960129523000373_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116828"},{"key":"S0960129523000373_ref34","first-page":"1","article-title":"Quantum recommendation systems","volume":"49","author":"Kerenidis","year":"2017","journal-title":"Innovations in Theoretical Computer Science Conference"},{"key":"S0960129523000373_ref51","unstructured":"Paschen, K. (2000). Quantum Finite Automata using Ancilla Qubits, University of Karlsruhe, Technical report."},{"volume-title":"Quantum Computation and Quantum Information","year":"2000","author":"Nielsen","key":"S0960129523000373_ref50"},{"key":"S0960129523000373_ref66","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992862"},{"key":"S0960129523000373_ref71","doi-asserted-by":"publisher","DOI":"10.26421\/QIC16.7-8-1"},{"key":"S0960129523000373_ref42","doi-asserted-by":"publisher","DOI":"10.21468\/SciPostPhysLectNotes.29"},{"key":"S0960129523000373_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"volume-title":"Quantum Computing","year":"1999","author":"Gruska","key":"S0960129523000373_ref28"},{"key":"S0960129523000373_ref6","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.104.052404"},{"key":"S0960129523000373_ref46","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.98.032309"},{"key":"S0960129523000373_ref53","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-06-30-752"},{"volume-title":"Introduction to Probabilistic Automata","year":"1971","author":"Paz","key":"S0960129523000373_ref52"},{"key":"S0960129523000373_ref60","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.040"},{"key":"S0960129523000373_ref13","unstructured":"Bollig, B. , Habermehl, P. , Kern, C. and Leucker, M. (2009). Angluin-style learning of NFA. In: Proceeding of the 21st International Joint Conference on Artificial Intelligence, IJCAI-09, AAAI Press, 1004\u20131009."},{"key":"S0960129523000373_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3106700.3106710"},{"key":"S0960129523000373_ref59","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-011-0139-6"},{"key":"S0960129523000373_ref16","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10891"},{"key":"S0960129523000373_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.03.021"},{"key":"S0960129523000373_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00191-1"},{"key":"S0960129523000373_ref38","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3029"},{"key":"S0960129523000373_ref1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"S0960129523000373_ref41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.121.040502"},{"key":"S0960129523000373_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139194655"},{"key":"S0960129523000373_ref64","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13350-8_16"},{"key":"S0960129523000373_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293123"},{"key":"S0960129523000373_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"S0960129523000373_ref35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.107.010101"},{"key":"S0960129523000373_ref17","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab4eb5"},{"key":"S0960129523000373_ref72","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.10.007"},{"key":"S0960129523000373_ref49","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.07.002"},{"key":"S0960129523000373_ref56","unstructured":"Qiu, D. W. , Li, L. , Mateus, P. and Gruska, J. (2012). Quantum Finite Automata. In: Wang, J. (ed.) Finite State-Based Models and Applications, CRC Handbook, 113\u2013144."}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129523000373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,5]],"date-time":"2024-02-05T11:24:31Z","timestamp":1707132271000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129523000373\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,30]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["S0960129523000373"],"URL":"https:\/\/doi.org\/10.1017\/s0960129523000373","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2023,11,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}