Computational power of quantum finite automata

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.


Source : Link , Question Author : acevik , Answer Author : Community

Leave a Comment