3
$\begingroup$

$\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.

$\endgroup$

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.