While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97); both models are sufficiently described in this Wikipedia article.
So far, I found a proof in L19 (p.5, prop.1) which shows that, for any MO-1QFA and any input string w, there is an MM-1QFA accepting w with the same probability (only bounded error considered here). Therefore, MO-1QFA = MM-1QFA. However, I have not been able to find a proof showing that MM-1QFA > MO-1QFA indeed. There are informal arguments by Brodsky and Pippenger BP18 (p.9, start of sec.4), just saying that this is because MM-1QFA are allowed to terminate before reading the entire input string (due to their measurements after every transition). Furthermore, Ambainis and Freivalds AF98 (end of p.3) say that any finite language can be recognized by MM-1QFA, but no finite non-empty language can be recognized by MO-1QFA.
Though these claims seem reasonable to me at first, I have failed to construct an example (let alone an idea for a general proof) that would make them clear to me. One issue is that I do not see how a MM-1QFA would know "when to stop".
Based on all this, I would be glad if someone could help me to see why MM-1QFA are strictly more powerful than MO-1QFA.
