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 1


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.


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.