In the beginning of this paper about amplitude amplification algorithm, the author stated the conventions of amplitude amplification which I quoted the important part for your convenience as follows:

Let $|\Psi\rangle=\mathcal{A}|0\rangle$ denote the superposition obtained by applying algorithm $\mathcal{A}$ on the initial state $|0\rangle$. Let $\left|\Psi_{1}\right\rangle=$ $\mathbf{P}_{\text {good }}|\Psi\rangle$ where $\mathbf{P}_{\text {good }}=\sum_{x: \chi(x)=1}|x\rangle\langle x|$ denotes the projection onto the subspace spanned by the good basis states, and similarly let $\left|\Psi_{0}\right\rangle=\mathbf{P}_{\mathrm{bad}}|\Psi\rangle$ where $\mathbf{P}_{\mathrm{bad}}=\sum_{x: \chi(x)=0}|x\rangle\langle x| .$ Let $a=\left\langle\Psi_{1} \mid \Psi_{1}\right\rangle$ denote the probability that a measurement of $|\Psi\rangle=\mathcal{A}|0\rangle$ yields a good state, and let $b=\left\langle\Psi_{0} \mid \Psi_{0}\right\rangle$ denote the probability that a measurement of $|\Psi\rangle$ yields a bad state. We then have that $|\Psi\rangle=\left|\Psi_{1}\right\rangle+\left|\Psi_{0}\right\rangle$ and $1=a+b$. Finally, let angle $\theta$ be so that $0 \leq \theta \leq \pi / 2$ and $a=\sin ^{2}(\theta)$

So from the statement above, I didn't see the requirement that $|\Psi\rangle$ need be state like $\frac{1}{\sqrt{N}}\sum_i|i\rangle$, i.e., the equal superposition state. It seems there's no wrong theoretically, but shouldn't we prepare an equal superposition state considering we don't have any idea which one is the answer? It's kind of weird for me.

Did I misunderstand the Amplitude Amplification algorithm or it is exactly what I said above just for theoretical generality?


1 Answer 1


You've understood it correctly. The whole point of amplitude amplification is that it generalises Grover's Search so that it works with non-uniform superpositions.

One of the key applications of this is for effectively generating non-linear function applications (such as in the HHL algorithm) where you can produce an operation $$ |x\rangle|0\rangle\mapsto |x\rangle(\cos\theta_x|0\rangle+\sin\theta_x|1\rangle) $$ and you effectively want to post-select on the second system being in the $|1\rangle$ state no matter what the coefficients of the initial state $\sum_xc_x|x\rangle$.

  • $\begingroup$ But just a bit weird I think. If the initial state $|\Psi\rangle$ is a non-uniform superposition state, then the target state might also be a non-uniform superposition state. Then, if we have several answers, and try to find all the answers by executing the algorithm over and over again until we find all the solutions. But since the non-uniform superposition of the target state, some answer states might have a low probability which against us to find them. $\endgroup$
    – narip
    Dec 2, 2021 at 6:50
  • 1
    $\begingroup$ There is only a single target state $P_{\text{good}}|\Psi\rangle$. It is the state that you are trying to produce (usually) in this instance, not individual solutions (corresponding to populated basis states inside the state). If your goal is to sample all solutions uniformly, then you'll just stick with Grover. $\endgroup$
    – DaftWullie
    Dec 2, 2021 at 8:40

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.