<p>I'm interested in the basic amplification procedure for QMA: the prover sends $O(r)$ copies of his witness to the verifier, which decreases the error probability to $2^{-O(r)}$ (Chernoff bound). The only difficulty is to show when $x \notin \mathcal{L}$ that the prover will not gain anything if he entangles the copies. There are complicated proofs of this result (see <a href="http://dl.acm.org/citation.cfm?id=335387" rel="nofollow noreferrer">[KW00]</a>,<a href="http://dl.acm.org/citation.cfm?id=863284" rel="nofollow noreferrer">[KSV02]</a>), but I have also seen one-line proofs that use convexity. See these <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-845-quantum-complexity-theory-fall-2010/lecture-notes/MIT6_845F10_lec14.pdf" rel="nofollow noreferrer">lectures notes</a> from Aaronson from instance:</p>

<blockquote>
  <p>Now what if Merlin sends witness states that are entangled with each
  other? <strong>By convexity</strong>, some pure state $|\psi\rangle$ maximizes the probability that
  Arthur accepts. Even after Arthur has performed an experiment on a
  register, Merlin can hope for nothing better than for the next
  register Arthur acts on to contain $|\psi\rangle$. But then, why not just put the
  unentangled state $|\psi\rangle$ there? So, entangling registers doesn't win Merlin anything.</p>
</blockquote>

<p>I don't understand the convexity argument here. Assume that the acceptance probability is given by $||\Pi |\psi\rangle ||^2$ for some projector $\Pi$. I know that $||\cdot||^2$ is convex but I don't see how to use it here. For instance, if $|\psi\rangle = \sum_i \alpha_i |\psi^i_1\rangle \otimes \cdots \otimes |\psi^i_r\rangle$ for orthogonal unit vectors $|\psi^i_1\rangle \otimes \cdots \otimes |\psi^i_r\rangle$ (thus $\sum_i |\alpha_i|^2 = 1$) we would like to have $||\Pi |\psi\rangle ||^2 \leq \sum_{i,j} |\alpha_i|^2 \cdot ||\Pi |\psi^i_j\rangle ||^2$ but this is not what convexity means...</p>

CC BY-SA 3.0
2017-06-04T02:07:02.093Z
I suspect that the "By convexity" part is just trying to imply that Merlin's state for the n experiments can assumed to be pure, since the optimal point of a linear function over a convex can assumed to be an extreme point. To then derive the fact that this pure state can be assumed to be a product state,  I don't think convexity is directly involved (I would guess one can just take partial traces? Otherwise, I believe it should work to write down semi-definite programs for the one experiment case and the n experiment case, and relate the values of the corresponding duals).
Abel Molina
CC BY-SA 3.0
2017-06-05T04:36:15.007Z
I don't think the convexity argument is used to show that the whole state sent by Merlin is pure, because this question was already adressed in the previous paragraph of the lecture notes: "What if Merlin keeps some qubits that are entangled with the witness states he sends? Then, from Arthur's view, Merlin has sent mixed states, so Arthur's probability of accepting is a weighted mean of the probability of accepting each component pure state. So, again, Merlin would be at least as well off sending the pure part with highest acceptance probability."
permanganate
<quantum-computing>
Convexity argument in QMA Amplification
permanganate
# Convexity argument in QMA Amplification

(Asked by: username_0 on 2017-05-29)

I'm interested in the basic amplification procedure for QMA: the prover sends $O(r)$ copies of his witness to the verifier, which decreases the error probability to $2^{-O(r)}$ (Chernoff bound). The only difficulty is to show when $x \notin \mathcal{L}$ that the prover will not gain anything if he entangles the copies. There are complicated proofs of this result (see [[KW00]](http://dl.acm.org/citation.cfm?id=335387),[[KSV02]](http://dl.acm.org/citation.cfm?id=863284)), but I have also seen one-line proofs that use convexity. See these [lectures notes](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-845-quantum-complexity-theory-fall-2010/lecture-notes/MIT6_845F10_lec14.pdf) from Aaronson from instance:

> Now what if Merlin sends witness states that are entangled with each
> other? **By convexity**, some pure state $|\psi\rangle$ maximizes the probability that
> Arthur accepts. Even after Arthur has performed an experiment on a
> register, Merlin can hope for nothing better than for the next
> register Arthur acts on to contain $|\psi\rangle$. But then, why not just put the
> unentangled state $|\psi\rangle$ there? So, entangling registers doesn't win Merlin anything.

I don't understand the convexity argument here. Assume that the acceptance probability is given by $||\Pi |\psi\rangle ||^2$ for some projector $\Pi$. I know that $||\cdot||^2$ is convex but I don't see how to use it here. For instance, if $|\psi\rangle = \sum\_i \alpha\_i |\psi^i\_1\rangle \otimes \cdots \otimes |\psi^i\_r\rangle$ for orthogonal unit vectors $|\psi^i\_1\rangle \otimes \cdots \otimes |\psi^i\_r\rangle$ (thus $\sum\_i |\alpha\_i|^2 = 1$) we would like to have $||\Pi |\psi\rangle ||^2 \leq \sum\_{i,j} |\alpha\_i|^2 \cdot ||\Pi |\psi^i\_j\rangle ||^2$ but this is not what convexity means...

**Tags:** quantum-computing
> **Comments:**
> **username_1**: I suspect that the "By convexity" part is just trying to imply that Merlin's state for the n experiments can assumed to be pure, since the optimal point of a linear function over a convex can assumed to be an extreme point. To then derive the fact that this pure state can be assumed to be a product state,  I don't think convexity is directly involved (I would guess one can just take partial traces? Otherwise, I believe it should work to write down semi-definite programs for the one experiment case and the n experiment case, and relate the values of the corresponding duals).  
> **username_0**: I don't think the convexity argument is used to show that the whole state sent by Merlin is pure, because this question was already adressed in the previous paragraph of the lecture notes: "What if Merlin keeps some qubits that are entangled with the witness states he sends? Then, from Arthur's view, Merlin has sent mixed states, so Arthur's probability of accepting is a weighted mean of the probability of accepting each component pure state. So, again, Merlin would be at least as well off sending the pure part with highest acceptance probability."  

---

## 0 answers

