I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard finite automata (FA). There is one-way QFA (1QFA) and two-way QFA (2QFA). For each model, we can either have "measure-once" (MO) or "measure-many" (MM) version. I thought MO-1QFA was stronger than FA but apparently it is not. I also thought MM-1QFA is same as one-way probabilistic finite automata. Apparently, MO-1QFA is weaker than MM-1QFA. This is a little puzzling because measure-many quantum Turing machines are same as probabilistic Turing machines. However, measure-once Turing machines are stronger than the measure-many version.

Could you please state which models are actually computationally stronger than the other? Where do we place 1-way and 2-way probabilistic finite automata (1PFA, 2PFA) in this picture?

Thank you in advance.

  • 3
    $\begingroup$ Have you checked the following recent comprehensive survey? arxiv.org/pdf/1901.07992.pdf $\endgroup$ – Yuval Filmus May 1 at 17:35
  • $\begingroup$ Thank you, this looks like a very good survey paper. $\endgroup$ – acevik May 2 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.