What is the difference between Grover's and Amplitude Amplification?

Question

I'm confused about what precisely is the difference between Grover's Algorithm and Amplitude Amplification. I've heard some sources say they are different algorithms and others say they are the same thing. As I currently understand it,

• In Grover's algorithm you are searching for a state $|\omega\rangle$ (or multiple states) marked by an oracle, and you find this by applying Grover iterations that comprise of phase inversion $I-2|\omega\rangle\langle \omega|$ and mean inversion $I-2|s\rangle\langle s|$ in alternation.

• In Amplitude Amplification, you have a projection operator P that projects you on to a "good" subspace, which seems to essentially boil down to marking a set of states. Then you have an operator $S_P = 1 - 2P$ that does phase inversion on those states and $S_\psi = 1 - 2|\psi\rangle\langle \psi|$ which seems to invert about your initial state $|\psi\rangle$.

So is the difference that in AA you are starting in an arbitrary state $|\psi\rangle$ and in Grover's you set $|\psi\rangle$ to be the uniform superposition state $|s\rangle$? Are there other important differences I am missing?

Answer 1

Grover's algorithm is a special case of the amplitude amplification algorithm where the number of good entries $G$ in the $N$-item database is $1$.

In a nutshell:

1. In the Grover's algorithm Wiki page that you linked, the keyword is "unique". Given $f:\{0, \ldots, N-1\} \to \{0, 1\}$ such that $f(x) = 1$ for exactly one $x$ (say $\omega$), Grover's algorithm amplifies the quantum state corresponding to $\omega$. Amplitude amplification is the generalized version that can amplify the quantum states corresponding to multiple entries, given their output is $1$.

2. In both the algorithms you begin with a uniform superposition state

   $$|\psi\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1}|k\rangle$$ where $N$ is the number of database entries (cf. here). No difference there.

3. The amplitude amplification algorithm calls the subspace (of the Hilbert space $\mathcal{H}$) of strings $x$'s for which output of $f$ is $1$ as the good subspace. They are just dividing the entire Hilbert space $\mathcal{H}$ into two mutually orthogonal subspaces $\mathcal{H}_1$ and $\mathcal{H}_0$, just like in Grover's algorithm, but there the good subspace $\mathcal{H}_1$ was single-dimensional i.e., corresponding to the unique marked state $|\omega\rangle$.

---

Edit: Upon further reading, it appears Brassard et al. (2000) generalized Grover's original algorithm (1997) in more ways than one, and were the first to coin the term quantum amplitude amplification. For a quick summary, refer to the concluding remarks section on pages 25-26.