$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$ In MW05 the authors demonstrate so-called "in-place" amplitude amplification for QMA, exhibiting a method for Arthur to amplify his success probability without requiring any increase in the size of Merlin's witness state. Call the original machine $M$ and the amplified machine $M'$.

Suppose that $x$ is the input, the original machine is $M(x,w)$ and the amplified machine is $M'(x,w)$. The approach of MW05 does not guarantee that a witness state that was in the accepting set for $M(x,\cdot)$ (i.e. that made $M$ accept input $x$ with probability exceeding, say, $\frac{2}{3}$) is still in the accepting set for $M'(x, \cdot)$ (i.e. those states that make $M'(x, \cdot)$ accept with amplified probability). I explain why I think that it's actually not possible to make their method do this below the line.

Q: Is there a way to perform amplification of QMA machines without increasing the length of Merlin's witness and while also guaranteeing that all initially valid witnesses for a given input stay valid witnesses for this input?

Without explaining too much context and using their notation, the issue that seems to arise is that MW05 first proves that their approach works for states that are eigenvectors of $Q$. This is good enough for completeness because if there's a state that accepts with probability $p \geq a$ then there's an eigenvector with success probability at least $p$. However, I don't think this can be used to show that any "good" witness also accepts w.h.p. after amplification.

In general a "good" witness $\ket{\psi}$. will be some linear combination of eigenvectors $\sum_j \alpha_j\ket{\psi_j}$, some of which are "good" and have acceptance probability $\geq a$ and others of which are "bad" and have acceptance probability $\leq b$. Let $S$ be the set of "good" witness eigenvectors. Then, once we amplify, our success probability is roughly (for $r$ large enough I guess)

$$\sum_{j \in S} |\alpha_j|^2(1-2^{-r}).$$

In general $\sum_{j \in S} |\alpha_j|^2$ isn't $1$ so we're in trouble. In the worst case of witness eigenvectors, we can even construct a "good" witness $\ket{\psi}$ that after $r$-rounds of amplification accepts with probability roughly $\frac{a-b}{1-b}(1-2^{-r}) \leq \frac{1}{2}$ for $(a,b) = (\frac{2}{3}, \frac{1}{3})$.


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.