Looking at the oblivious AA (OAA) : https://docs.microsoft.com/en-us/azure/quantum/user-guide/libraries/standard/algorithms

I am trying to figure out the eigendecomposition of Q, which leads to below. Any help or suggestion on how to derive these would be highly appreciated!

$$ |\psi\rangle=\frac{-i}{\sqrt{2}}\left(e^{i \theta}\left|\psi_{+}\right\rangle+e^{-i \theta}\left|\psi_{-}\right\rangle\right) $$ where $\left|\psi_{\pm}\right\rangle$are eigenvectors of $Q$ with eigenvalues $e^{\pm 2 i \theta}$ and only have support on the $+1$ eigenvectors of $P_{0}$ and $P_{1}$.

Here are the key sentences from the website

Each iteration of Amplitude amplification requires that two reflection operators be specified. Specifically, if $Q$ is the amplitude amplification iterate and $P_{0}$ is a projector operator onto the initial subspace and $P_{1}$ is the projector onto the marked subspace then $Q=-\left(\mathbf{1}-2 P_{0}\right)\left(\mathbf{1}-2 P_{1}\right)$. Recall that a projector is a Hermitian operator that has eigenvalues $+1$ and 0 and as a result $\left(\mathbf{1}-2 P_{0}\right)$ is unitary because it has eigenvalues that are roots of unity (in this case $\pm 1$ ). As an example, consider the case of Grover's search with initial state $H^{\otimes n}|0\rangle$ and marked state $|m\rangle, P_{0}=H^{\otimes n}|0\rangle\langle 0| H^{\otimes n}$ and $P_{1}=|m\rangle\langle m| .$ In most applications of amplitude amplification $P_{0}$ will be a projector onto an initial state meaning that $P_{0}=\mathbf{1}-2|\psi\rangle\langle\psi|$ for some vector $|\psi\rangle ;$ however, for oblivious amplitude amplification $P_{0}$ will typically project onto many quantum states (for example, the multiplicity of the $+1$ eigenvalue of $P_{0}$ is greater than 1 ).

The logic behind amplitude amplification follows directly from the eigen-decomposition of $Q .$ Specifically, the eigenvectors of $Q$ that the initial state has non-zero support over can be shown to be linear combinations of the $+1$ eigenvectors of $P_{0}$ and $P_{1}$. Specifically, the initial state for amplitude amplification (assuming it is a $+1$ eigenvector of $P_{0}$ ) can be written as $$ |\psi\rangle=\frac{-i}{\sqrt{2}}\left(e^{i \theta}\left|\psi_{+}\right\rangle+e^{-i \theta}\left|\psi_{-}\right\rangle\right) $$ where $\left|\psi_{\pm}\right\rangle$are eigenvectors of $Q$ with eigenvalues $e^{\pm 2 i \theta}$ and only have support on the $+1$ eigenvectors of $P_{0}$ and $P_{1}$. The fact that the eigenvalues are $e^{\pm i \theta}$ implies that the operator $Q$ performs a rotation in a two-dimensional subspace specified by the two projectors and the initial state where the rotation angle is $2 \theta$. This is why after $m$ iterations of $Q$ the success probability is $\sin ^{2}([2 m+1] \theta)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.