<p>While dealing with quantum finite automata (QFA), I repeatedly come across the statement that <em>measure-many</em> QFA (MM-1QFA, <a href="https://cs.uwaterloo.ca/~watrous/Papers/QuantumFiniteAutomata.pdf" rel="nofollow noreferrer">KW97</a>) are <strong>strictly</strong> more powerful than <em>measure-once</em> QFA (MO-1QFA, <a href="https://arxiv.org/abs/quant-ph/9707031" rel="nofollow noreferrer">MC97</a>). More details are sufficiently summarized in this <a href="https://en.wikipedia.org/wiki/Quantum_finite_automata" rel="nofollow noreferrer">Wikipedia article</a> if requested.</p>

<p>So far, I found a proof in <a href="https://arxiv.org/pdf/1308.3301.pdf" rel="nofollow noreferrer">L19</a> (p.5, prop.1) which shows that, for any MO-1QFA and any input string <em>w</em>, there is an MM-1QFA accepting <em>w</em> with the same probability (only bounded error considered here). Therefore, <span class="math-container">$\mathcal{L}$</span>(MO-1QFA) = <span class="math-container">$\mathcal{L}$</span>(MM-1QFA). However, I have not been able to find a proof showing that <span class="math-container">$\mathcal{L}$</span>(MM-1QFA) > <span class="math-container">$\mathcal{L}$</span>(MO-1QFA) indeed. </p>

<p>There are informal arguments by Brodsky and Pippenger <a href="https://arxiv.org/pdf/quant-ph/9903014.pdf" rel="nofollow noreferrer">BP18</a> (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 <a href="https://arxiv.org/pdf/quant-ph/9802062.pdf" rel="nofollow noreferrer">AF98</a> (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".</p>

<p>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".</p>

<p>Based on all this, I would be glad if someone could help me to see why MM-1QFA are actually <strong>strictly</strong> more powerful than MO-1QFA.</p>

CC BY-SA 4.0
2020-03-21T21:38:12.750Z
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.
Lem n
CC BY-SA 4.0
2020-03-22T08:58:03.167Z
@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](https://reader.elsevier.com/reader/sd/pii/S0304397511008917?token=E0FEE5882EE6944A728EE608C595AECD8D3F1727318C82AECEA16A0D7E4D6F57DDDAF9F8EA0A60BEE59484ED7C91A660) that multiple measurements do not increase the recognition power. So, why is this the case for the non-general version?
catalyst
<fl.formal-languages><quantum-computing><automata-theory>
Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? (Quantum automata)
catalyst
# Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? (Quantum automata)

(Asked by: username_0 on 2020-03-21)

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that *measure-many* QFA (MM-1QFA, [KW97](https://cs.uwaterloo.ca/~watrous/Papers/QuantumFiniteAutomata.pdf)) are **strictly** more powerful than *measure-once* QFA (MO-1QFA, [MC97](https://arxiv.org/abs/quant-ph/9707031)). More details are sufficiently summarized in this [Wikipedia article](https://en.wikipedia.org/wiki/Quantum_finite_automata) if requested.

So far, I found a proof in [L19](https://arxiv.org/pdf/1308.3301.pdf) (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](https://arxiv.org/pdf/quant-ph/9903014.pdf) (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](https://arxiv.org/pdf/quant-ph/9802062.pdf) (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.

**Tags:** fl.formal-languages, quantum-computing, automata-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1, 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](https://reader.elsevier.com/reader/sd/pii/S0304397511008917?token=E0FEE5882EE6944A728EE608C595AECD8D3F1727318C82AECEA16A0D7E4D6F57DDDAF9F8EA0A60BEE59484ED7C91A660) that multiple measurements do not increase the recognition power. So, why is this the case for the non-general version?  

---

## 0 answers

