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). More details are sufficiently summarized in this Wikipedia article if requested.

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, $\mathcal{L}$(MO-1QFA) = $\mathcal{L}$(MM-1QFA). However, I have not been able to find a proof showing that $\mathcal{L}$(MM-1QFA) > $\mathcal{L}$(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 seemed 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 actually strictly more powerful than MO-1QFA.

  • $\begingroup$ Error? MO can throw false positives/negatives. MM uses additional queries to statistically certify the final result. That outcome can be wrong too, but its chance of failure is compounded toward zero with every measurement. $\endgroup$ – Lem n Mar 21 '20 at 21:38
  • 1
    $\begingroup$ @Lem n, thanks for your comment. Intuitively this seems plausible. On the other hand, when regarding general 1QFA (where the transitions are not restricted to unitary operators but may be more general trace-preserving quantum operations), it was shown by Li12 that multiple measurements do not increase the recognition power. So, why is this the case for the non-general version? $\endgroup$ – catalyst Mar 22 '20 at 8:58

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.