Quantum Computing Asked by bean on February 7, 2021
$defbraket#1#2{langle#1|#2rangle}defbra#1{langle#1|}defket#1{|#1rangle}$
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.
QMA verification includes three registers, with appropriate bounds on the length of each register:
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 xrangle$ 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 xrangle$ in superposition, Arthur could initially start his verification procedure by measuring $vert xrangle$ to get a classical string $x$. Merlin doesn't gain anything by sending $vert xrangle$ 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.
Answered by Mark S on February 7, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP