I am trying to figure out equation (2.33) here.

Given that

\begin{gather} U_{\psi_0}|{0^m}\rangle|{0^n}\rangle=\sqrt{p_0}|{0^m}\rangle|{\psi_0}\rangle+\sqrt{1-p_0}|{\perp}\rangle,\\ (\Pi\otimes I_n)|{\perp}\rangle=0, \quad \Pi=|{0^m}\rangle\langle{0^m}|, \end{gather}

we call $|\psi_{\rm good}\rangle=|0^m\rangle|\psi_0\rangle$ and would like to prepare $|\psi_0\rangle$ in the second register with $O(1)$ probability. The recipe is to define

\begin{gather} R_{\mathrm{good}}=(1-2|{0^m}\rangle\langle{0^m}|)\otimes I_n=(1-2\Pi)\otimes I_n,\\ R_{\psi_0}=U_{\psi_0}(2|{0^{m+n}}\rangle\langle{0^{m+n}}|-I)U^{\dagger}_{\psi_0}. \end{gather}

and to "apply $G^k=(R_{\mathrm{good}}R_{\psi_0})^k$ to $|\psi_0\rangle$ for $k=O(1\sqrt{p_o})$ times." (I think that there's a typo, and we should actually apply $G^k$ to the first equation above, correct?)

What I do not understand here is why the so-defined $R_{\mathrm{good}}$ is equivalent to $(1-2|\psi_{\rm good}\rangle\langle \psi_{\rm good}|)= (1-\Pi \otimes\Pi_{\rm good})$, which is the original definition requried for the amplitude amplification. The line after (2.33) says: "This is because $|{\psi_{\mathrm{good}}}\rangle$ can be entirely identified by measuring the ancilla qubits."

So at which point in this process do we measure ancillas? It seems that measuring ancillas each time after we apply $R_{\mathrm{good}}$ would ruin the whole procedure. If we don't measure anything until the very end, then, as I said above, it's unclear why $R_{\mathrm{good}} = (1-2|\psi_{\rm good}\rangle\langle \psi_{\rm good}|)$ and how this construction reduces to amplitude amplification.


OK, I still don't understand what the sentence "This is because $|\psi_{\rm good}\rangle$ can be entirely identified by measuring the ancilla qubits." after (2.33) means but I just checked the following:

\begin{gather} (1-2\Pi\otimes\Pi_{\rm good}) (\sqrt{p_0}|0^m\rangle |\psi_0\rangle + \sqrt{1-p_0}|\perp\rangle = (1-2\Pi) (\sqrt{p_0}|0^m\rangle |\psi_0\rangle + \sqrt{1-p_0}|\perp\rangle \,, \end{gather} because in the first term $\Pi_{\rm good}$ acts trivially and in the second term $\Pi$ annihilates $|\perp\rangle$ anyways.

On later steps the same happens, as the only thing that's changing is the amplitudes.

So I'm assuming that no measurements of ancillas are required until the very end. Correct?

  • $\begingroup$ Are you still wondering about this? $\endgroup$
    – kηives
    Nov 16, 2022 at 21:15

1 Answer 1


This is because when you're in the subspace where the block-encoding was applied, the ancilla qubits are in the $|0\rangle$ state. So you can boost the success probability on the state $|0\rangle|\psi\rangle_{\text{good}}$, by using amplitude amplification with the Grover iterate providing a phase kickback. The reflector picks out the state in which to perform the sign flip on. It's basically a Pauli Z-gate in the $\{|\psi\rangle_\text{good}, |\perp\rangle\}$ basis.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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