$\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. Because QMA is a language of classical bitstrings, this in some sense amplification with a classical input and quantum witness.

Is there an analogue of Mariott-Watrous amplification for when the input is quantum? To me it seems like naively pushing it through fails for the following reason:

In the classical case, if $x$ is the input and $A(x,\ket{w})$ is the verifier, then Marriott-Watrous amplification relies being able to apply $A_x := A(x, \cdot)$ and $A_x^{\dagger}$ many times. This is fine because even if we modify $x$ throughout the course of computing $A_x$, we can just prepare a copy in advance so that we always have $x$ accessible to us. However, if the input is instead an arbitrary quantum state $\ket{x}$, no-cloning forbids us from doing this. As such, we may corrupt $\ket{x}$ over the course of computation and all bets are off.


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.