# Oblivious Amplitude Amplification & Eigenstate decomposition

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)$$

## 1 Answer

This is all proved in pgs. 9-11 of the paper that first introduced OAA, but I can summarize the important points here.

The starting point is assuming access to a block-encoding of some desired unitary action $$V$$ which lives inside a larger unitary $$U$$, and is accessed by successfully projecting into the 'good' subspace $$|0^\mu\rangle \otimes I$$:

\begin{align} U |0^\mu\rangle|\psi\rangle = \sin(\theta)|0^\mu\rangle V|\psi\rangle + \cos(\theta) |\Phi^\perp\rangle \equiv U |\Psi\rangle = \sqrt{p} |\Phi\rangle + \sqrt{1-p} |\Phi^\perp\rangle \end{align}

Since we only succeed with some probability ($$p = \sin^2(\theta)$$), we want to boost the weight of this term, but standard amplitude amplification would require knowing $$|\psi\rangle$$, which could be arbitrary. The trick is to attach that $$|0^\mu\rangle$$ register so that in fact, we do know the subspace that contains the desired state, because its simply the space defined by the projector $$R = 2\Pi - I$$, with $$\Pi = |0^\mu\rangle\langle 0^\mu| \otimes I$$. We only need to figure out how to do the iterated reflections about these subspaces, which together should produce a rotation of $$2\theta$$ between the subspaces. In that paper, it is shown that the action of $$U$$ takes the following form \begin{align} U = \begin{bmatrix} \sin{\theta} & \cos{\theta} \\ \cos\theta & -\sin{\theta} \end{bmatrix} \end{align} but in a special basis, where $$\{ |\Psi\rangle, |\Psi^\perp\rangle \}$$ is mapped to $$\{ |\Phi\rangle, |\Phi^\perp\rangle \}$$. As a result, $$U^\dagger$$ has the same form, but maps from the $$\Phi$$-basis back to the $$\Psi$$-basis. This matrix has eigenvalues $$-1,+1$$ and so it is a reflection. If you sandwich it with the other reflection defined earlier to produce the operator $$S = -U R U^\dagger R$$, you can work out the action of $$S$$ to be \begin{align} S = \begin{bmatrix} \cos{2\theta} & \sin{2\theta} \\ -\sin2\theta & \cos{2\theta} \end{bmatrix} \end{align} which is a now a rotation of angle $$2\theta$$ between the input and output subspaces. The action of $$S$$ can be written in terms of its spectral decomposition \begin{align} S = e^{-i2\theta} |v^{\Phi}_1\rangle\langle v_1^{\Psi}| + e^{i2\theta} |v_2^{\Phi} \rangle\langle v_2^{\Psi}| \end{align} where $$|v^{\Psi}_1\rangle = i |\Psi\rangle + |\Psi^\perp\rangle$$ and $$|v^{\Psi}_2\rangle = -i |\Psi\rangle + |\Psi^\perp\rangle$$ (and similarly for the $$\Phi$$ superscripts). The input state $$U|\Psi\rangle$$ expressed in the $$\Phi$$-basis eigenvectors has the form given in the Microsoft link (if you also renormalize the final state, I think).

The secret going on behind the scenes is that a certain result called Jordan's Lemma says that a product of reflections decomposes as a direct sum over 1 and 2-dimensional subspaces, which in this case are invariant under the action of the projectors $$\Pi$$ and $$U^\dagger \Pi U$$. Although these projectors are rank-$$2^n$$, they act as rank-1 projectors in each of these spaces, and therefore define the space(s) in which $$S$$ performs its rotations.