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


1 Answer 1


QMA verification includes three registers, with appropriate bounds on the length of each register:

  • $x$, a (classical) description of the (quantum) circuit used for verification, along with the promised gap;
  • $\vert w\rangle$, the (quantum) witness provided by Merlin; and
  • $\vert\eta\rangle$, the ancilla workspace used by Arthur.

It seems as if you are asking what problems may arise (for example, in the strong error-reduction of Marriott-Watrous), if $x$ where quantum rather than classical (for example, if $\vert x\rangle$ where in some superposition of states).

But the classical description of the circuit is meant to be agreed-upon by Arthur and Merlin a-priori. If Merlin were to send $\vert x\rangle$ in superposition, Arthur could initially start his verification procedure by measuring $\vert x\rangle$ to get a classical string $x$. Merlin doesn't gain anything by sending $\vert x\rangle$ itself in superposition, and cannot improve his completeness/soundness.

Sevag Gharibian has a very good lecture (clocking in at about 2 hours and 40 minutes) on QMA and MW here. I've been enjoying this lecture series very much.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.