The class of problems nondeterministically recognized by Moore-Crutchfield Quantum Finite Automata. These are automata that undergo a unitary transformation for each symbol consumed, and at the end are observed to be in an accepting state or not. The "nondeterminism" refers to the fact that the automaton will accept with positive probability if in the language, or with exactly zero probability otherwise.
Has the same caveats as NQP and EQP because of the exact acceptance probabilities.
Initially studied in <ref>Cristopher Moore and James P. Crutchfield. Quantum automata and quantum grammars.Theoretical ComputerScience, 237(1-2):275–306, 2000.</ref>, although they described QRL as probabilities over words, rather a language in the strict sense. Several important properties established by <ref>Alberto Bertoni and Marco Carpentieri. Analogies and differences between quantum and stochastic automata.Theoretical Computer Science, 262(1-2):69–81, 2001</ref>, where it was shown that QRL has no finite-size languages, but also contains several non-regular languages.
Also called NMCL, in <ref>Abuzer Yakaryilmaz, A. C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081</ref>, in order to disambiguate from NQL.
Contrast with NQL, which is an analogous class for a different model of quantum finite automaton: there the automaton is measured after each step for acceptance or rejection.
Alternative name for QRL. Named such in <ref>Abuzer Yakaryilmaz, A. C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081</ref>.
Not to be confused with the similar NQL.
An unfortunate name collision. The class of problems nondeterministically recognized by Kondacs-Watrous Quantum Finite Automata. These are automata that undergo a unitary transformation for each symbol consumed, and are measured after each step to check for acceptance or rejection. The "nondeterminism" refers to the fact that the automaton will accept with positive probability if in the language, or with exactly zero probability otherwise.
Has the same caveats as NQP and EQP because of the exact acceptance probabilities.
Initially studied in <ref>A. Kondacs; J. Watrous. On the power of quantum finite state automata. https://ieeexplore.ieee.org/document/646094</ref>, where they show that it contains all regular languages. In <ref>Abuzer Yakaryılmaz and A.C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081v2</ref> it was shown that this inclusion was strict. Also showed that NQL = S≠
Contrast with QRL, which is a different model of quantum finite automaton, in which measurement only occurs at the end.
Unrelated to the other NQL above.