Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
added 746 characters in body
Source Link
mavzolej
  • 2.2k
  • 8
  • 18

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.

UPDATE

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?

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.

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.

UPDATE

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?

Source Link
mavzolej
  • 2.2k
  • 8
  • 18

Reflection operator in amplitude amplification for block encoding

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.