{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:46Z","timestamp":1740142786079,"version":"3.37.3"},"reference-count":20,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T00:00:00Z","timestamp":1726790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/501100006048","name":"Universidad de la Rep\u00fablica","doi-asserted-by":"publisher","award":["CSIC 22520220100073UD"],"award-info":[{"award-number":["CSIC 22520220100073UD"]}],"id":[{"id":"10.13039\/501100006048","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002923","name":"Consejo Nacional de Investigaciones Cient\u00edficas y T\u00e9cnicas","doi-asserted-by":"publisher","award":["PIP 11220200100368CO"],"award-info":[{"award-number":["PIP 11220200100368CO"]}],"id":[{"id":"10.13039\/501100002923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100022965","name":"Ministerio de Ciencia, Tecnolog\u00eda e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PICT-2019-1272,PICT-2021-I-A-00090"],"award-info":[{"award-number":["PICT-2019-1272,PICT-2021-I-A-00090"]}],"id":[{"id":"10.13039\/100022965","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,1,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this paper, we introduce classically time-controlled quantum automata or classically time-controlled quantum automaton (CTQA), which is a reasonable modification of Moore\u2013Crutchfield quantum finite automata that uses time-dependent evolution and a \u2018scheduler\u2019 defining how long each Hamiltonian will run. Surprisingly enough, time-dependent evolution provides a significant change in the computational power of quantum automata with respect to a discrete quantum model. Indeed, we show that if a scheduler is not computationally restricted, then a CTQA could even decide the Halting problem. In order to unearth the computational capabilities of CTQAs, we study the case of a computationally restricted scheduler. In particular, we showed that depending on the type of restriction imposed on the scheduler, a CTQA can (i) recognize non-regular languages with cut-point, even in the presence of Karp\u2013Lipton advice, and (ii) recognize non-regular promise languages with bounded-error. Furthermore, we study the cutpoint-union of cutpoint languages by introducing a new model of Moore\u2013Crutchfield quantum finite automata with a rotating tape head. CTQA presents itself as a new model of computation that provides a different approach to a formal study of \u2018classical control, quantum data\u2019 schemes in quantum computing.<\/jats:p>","DOI":"10.1093\/comjnl\/bxae089","type":"journal-article","created":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T05:11:29Z","timestamp":1726895489000},"page":"23-31","source":"Crossref","is-referenced-by-count":0,"title":["Classically time-controlled quantum automata: definition and properties"],"prefix":"10.1093","volume":"68","author":[{"given":"Alejandro","family":"D\u00edaz-Caro","sequence":"first","affiliation":[{"name":"DCyT , Universidad Nacional de Quilmes, Roque S\u00e1enz Pe\u00f1a 352, Bernal, Buenos Aires,","place":["Argentina"]},{"name":"Instituto de Ciencias de la Computaci\u00f3n (CONICET-UBA) , Pabell\u00f3n Cero+Infinito, Ciudad Universitaria, Buenos Aires,","place":["Argentina"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcos","family":"Villagra","sequence":"additional","affiliation":[{"name":"Universidad Nacional de Asunci\u00f3n , Campus, San Lorenzo,","place":["Paraguay"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,9,20]]},"reference":[{"volume-title":"Conventions for quantum pseudocode","author":"Knill","key":"2025012013013983900_ref1","doi-asserted-by":"crossref","DOI":"10.2172\/366453"},{"key":"2025012013013983900_ref2","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1017\/S0960129506005238","article-title":"A lambda calculus for quantum computation with classical control","volume":"16","author":"Selinger","year":"2004","journal-title":"Math Struct Comput Sci"},{"key":"2025012013013983900_ref3","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/2499370.2462177","article-title":"Quipper: A scalable quantum programming language","volume":"48","author":"Green","year":"2013","journal-title":"ACM SIGPLAN Notices (PLDI\u201913)"},{"key":"2025012013013983900_ref4","first-page":"846","article-title":"Qwire A core language for quantum circuits","volume-title":"Proceedings of the 44th ACM SIGPLAN symposium on principles of programming languages, New York, NY, USA. POPL","author":"Paykin","year":"2017"},{"key":"2025012013013983900_ref5","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0304-3975(02)00138-X","article-title":"Two-way finite automata with quantum and classical states","volume":"287","author":"Ambainis","year":"2002","journal-title":"Theor Comput Sci"},{"journal-title":"Electronic Colloquium on Computational Complexity","article-title":"Public-qubits versus private-coins","author":"Yakaryilmaz","key":"2025012013013983900_ref6"},{"key":"2025012013013983900_ref7","first-page":"45","article-title":"Public qubits versus private coin","volume-title":"Proceedings of workshop on quantum and classical complexity","author":"Yakaryilmaz"},{"key":"2025012013013983900_ref8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.11.030","article-title":"Interactive proofs with quantum finite automata","volume":"568","author":"Nishimura","year":"2015","journal-title":"Theor Comput Sci"},{"key":"2025012013013983900_ref9","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0304-3975(98)00191-1","article-title":"Quantum automata and quantum grammars","volume":"237","author":"Moore","year":"2000","journal-title":"Theor Comput Sci"},{"key":"2025012013013983900_ref10","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1137\/S0097539799353443","article-title":"Characterizations of 1-way quantum finite automata","volume":"31","author":"Brodsky","year":"2002","journal-title":"SIAM J Comput"},{"key":"2025012013013983900_ref11","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-030-04070-3_21","article-title":"Classically time-controlled quantum automata","volume-title":"Theory and Practice of Natural Computing (TPNC 2018), Lecture Notes in Computer Science, 11324","author":"D\u00edaz-Caro"},{"key":"2025012013013983900_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13350-8_16","volume-title":"Quantum Finite Automata: A Modern Introduction","author":"Say","year":"2002"},{"key":"2025012013013983900_ref13","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-19225-3_24","article-title":"Quantum state complexity of formal languages","volume-title":"Proceedings of the 17th International Workshop on Descriptional Complexity of Formal Systems (DCFS), LNCS, 9118","author":"Villagra","year":"2015"},{"key":"2025012013013983900_ref14","first-page":"332","article-title":"1-way quantum finite automata: strengths, weaknesses and generalizations","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Ambainis","year":"2015"},{"key":"2025012013013983900_ref15","doi-asserted-by":"crossref","first-page":"643","DOI":"10.2307\/1968538","article-title":"On one-parameter unitary groups in Hilbert space","volume":"33","author":"Stone","year":"1932","journal-title":"Ann Math"},{"key":"2025012013013983900_ref16","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.ic.2014.10.003","article-title":"One-way reversible and quantum finite automata with advice","volume":"239","author":"Yamakami","year":"2014","journal-title":"Inform Comput"},{"key":"2025012013013983900_ref17","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/j.jcss.2014.06.008","article-title":"Exponentially more concise quantum recognition of non-RMM regular languages","volume":"81","author":"Qiu","year":"2015","journal-title":"J Comput Syst Sci"},{"key":"2025012013013983900_ref18","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1051\/ita:2006007","article-title":"Quantum finite automata with control language","volume":"40","author":"Mereghetti","year":"2006","journal-title":"RAIRO - Theor Inform Appl"},{"key":"2025012013013983900_ref19","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.ipl.2012.01.001","article-title":"Superiority of exact quantum automata for promise problems","volume":"112","author":"Ambainis","year":"2012","journal-title":"Inform Process Lett"},{"key":"2025012013013983900_ref20","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2009.08.031","article-title":"Theory of one-tape linear-time Turing machines","volume":"411","author":"Tadaki","year":"2010","journal-title":"Theor Comput Sci"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/68\/1\/23\/59214976\/bxae089.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/68\/1\/23\/59214976\/bxae089.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T13:01:56Z","timestamp":1737378116000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/68\/1\/23\/7762872"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,20]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,9,20]]},"published-print":{"date-parts":[[2025,1,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxae089","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2025,1]]},"published":{"date-parts":[[2024,9,20]]}}}