The class of languages L for which there is a real number p, and probabilistic finite automaton M, such that:
* If x is in L, then M accepts x with some probability not exactly equal to p* If x is not in L, then M accepts x with probability exactly equal to p.
Defined in <ref>Abuzer Yakaryılmaz and A.C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081v2</ref>, where it was shown that S≠ = 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.