Learning finite automata (termed as model learning) 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 quantum learning theory and quantum machine learning, in this paper, our purpose is to initiate the study of learning QFA with queries (naturally it may be termed as quantum model learning), 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.

Some of the most interesting and important results concerning quantum finite automata arethose showing that they can recognize certain languages with (much) less resources thancorresponding classical finite automata. This paper shows three results of such a typethat are stronger in some sense than other ones because (a) they deal with models ofquantum finite automata with very little quantumness (so-called semi-quantum one- andtwo-way finite automata); (b) differences, even comparing with probabilistic classicalautomata, are bigger than expected; (c) a trade-off between the number of classical andquantum basis states needed is demonstrated in one case and (d) languages (or the promiseproblem) used to show main results are very simple and often explored ones in automatatheory or in communication complexity, with seemingly little structure that could beutilized.

We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical automata.