3
$\begingroup$

My question is about the witness preserving amplification scheme for QMA proposed by Marriott and Watrous in 2005 (see http://arxiv.org/abs/cs/0506068 and http://www.cims.nyu.edu/~regev/teaching/quantum_fall_2005/ln/qma.pdf).

The original (quantum verifier) circuit $A$ takes as input $|\psi\rangle \otimes |0^k\rangle$ (where $|\psi\rangle$ is the witness and $|0^k\rangle$ the auxiliary qubits) and it ouptuts (on its first row) the answer of the computation.

The amplifying circuit is defined using $A$ as follow:enter image description here

So it repeats several times the following two measurements (see section 3 of http://arxiv.org/abs/cs/0506068, or http://www.cims.nyu.edu/~regev/teaching/quantum_fall_2005/ln/qma.pdf):

  1. apply $A$, measure if output qubit of $A$ is 1, apply $A^{\dagger}$
  2. measure if auxiliary qubits are $0$

What I don't understand is how the auxiliary qubits could not be equal to 0. The initial state is $|\psi\rangle \otimes |0^k\rangle$ and then $AA^{\dagger} = I$, so we should always have state $|\psi\rangle \otimes |0^k\rangle$ at the second step (and so always obtaining Yes at this step)?

$\endgroup$
3
$\begingroup$

Since we measure the output in step 1, we do not apply $AA^\dagger$, but rather $$ A\vert0\rangle\langle 0\vert_1 A^\dagger $$ or $$ A\vert1\rangle\langle 1\vert_1 A^\dagger\ , $$ depending on the measurement outcome, which is generally not equal to the identity.

$\endgroup$

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.