# What languages does a (1-way) quantum finite state automata recognize?

Sorry if this is well known, but most of the research is paywalled.

So far I know that it is a subset of the regular languages, but I cannot seem to find any (available) research which pins it down.

Thanks!

Quantum finite automata (QFAs) are quantum counterparts of the usual finite automata.

In [1] it is shown that 1-way QFAs recognize a proper subset of the regular languages:

Proposition 6: Let $L$ be any language recognized by a 1QFA with bounded error. Then $L$ is regular.

Proposition 7: The language $L = \{a,b\}^*a$ cannot be recongized by a 1QFA with bounded error.

However in [2] :

... Our first results consider relations between 1-way QFAs and 1-way reversible automata. Clearly, a 1-way reversible automaton is a special case of a QFA and, therefore, cannot recognize all regular languages. It is a natural question whether 1-way QFAs are more powerful than 1-way reversible automata. Interestingly, the answer depends on the accepting probability of a QFA. If a QFA gives a correct answer with a large probability (greater than 7/9), it can be replaced by a 1-way reversible automaton. However, this is not true for 0.68... and smaller probabilities.

Then, we show that QFAs can be much more space-efficient than deterministic and even probabilistic finite automata. Namely, there is a 1-way QFA that can check whether the number of letters received from the input is divisible by a prime p with only $O(\log p)$ states (this is equivalent to $\log \log p$ bits of memory). Any deterministic or probabilistic finite automaton needs p states ($\log p$ bits of memory). We think that this space-efficient quantum algorithm may be interesting for design of other quantum algoritms as well....

For a quick introduction see:

• Additional comments to Vor: The first QFA models defined in some restricted ways and so they do not reflect the full power of "quantumness". Unitary operators are reversible but (quantum) measurement operators are not. So, you do not need to restrict yourself with reversibility constraint. Up to date, QFAs are defined with superoperators which can simulate any probabilistic operator (see above: Abuzer Yakaryilmaz and A. C. Cem Say, Unbounded-error quantum computation with small space bounds;). Therefore, QFAs can exactly simulate their classical counterparts. Feb 26, 2014 at 20:51

@Vor's answer was great, but incomplete. I found an amazing paper, the introduction of which answered virtually every question I had (and confirmed or disproved many of my suspicions):

Characterizations of one-way general quantum finite automata

(Theoretical Computer Science, Volume 419, 17 February 2012, Pages 73-91, ISSN 0304-3975)

• Lvzhou Li
• Daowen Qiu
• Xiangfu Zou
• Lvjun Li
• Lihua Wu
• Paulo Mateus

Abstract:

Generally, unitary transformations limit the computational power of quantum finite automata (QFA). In this paper, we study a generalized model named one-way general quantum finite automata (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata (MO-1gQFA) where a measurement deciding to accept or reject is performed at the end of a computation, and measure-many one-way general quantum finite automata (MM-1gQFA) where a similar measurement is performed after each trace-preserving quantum operation on reading each input symbol.

We characterize the measure-once model from three aspects: the closure property, the language recognition power, and the equivalence problem. We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. Our results imply that some models of quantum finite automata proposed in the literature, which were expected to be more powerful, still cannot recognize non-regular languages.

We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, in sharp contrast with traditional MO-1QFA and MM-1QFA, the former being strictly less powerful than the latter. Finally, we present a necessary and sufficient condition for two MM-1gQFA to be equivalent.

Thank you everyone who responded.

• Thanks for coming back to share a relevant resource! I encourage you to edit your answer to provide a proper citation to the paper (at least title & authors), in case the link dies. Also, please edit your answer to summarize the key points. People here tend to dislike link-only answers, because links don't remain valid forever.
– D.W.
Mar 2, 2014 at 15:58