6

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

glS
  • 27,510
  • 7
  • 37
  • 125
bean
  • 341
  • 1
  • 4

1 Answers1

3

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.

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83