5
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
10
  • 2
    $\begingroup$ I'm not sure that it's just that. If I remember correctly, in N&C Grover's algorithm is also called as such when there are $N$ targets. I would have said that amplitude amplification is the generalisation for arbitrary inputs, and when we do not care about how the two reflections are expressed in terms of elementary gates, but I also wouldn't know which reference to use in support of this statement $\endgroup$
    – glS
    Nov 1, 2019 at 17:28
  • $\begingroup$ @glS Well, the amplitude amplification algorithm was later independently rediscovered by Grover and some textbooks club it with "Grover's algorithm". I'm not sure where you found the "we do not care about how the reflections are expressed as elementary gates" version though. Did you check the original papers? (I didn't.) $\endgroup$ Nov 1, 2019 at 17:53
  • $\begingroup$ @glS Grover's 1996 paper clearly mentions "This paper applies quantum computing to a mundane problem in information processing and presents an algorithm that is significantly faster than any classical algorithm can be. The problem is this: there is an unsorted database containing N items out of which just one item satisfies a given condition - that one item has to be retrieved" $\endgroup$ Nov 1, 2019 at 17:57
  • $\begingroup$ @glS It seems Brassard and Hoyer's 1997 paper solved the more general case; check page 6. Note that Grover isn't a mathematician by training (his approach was often handwavy at places) and even his later papers (including the 1998 version) were not as mathematically elegant, unlike Brassard and Hoyer's. $\endgroup$ Nov 1, 2019 at 18:06
  • 1
    $\begingroup$ in fairness, it might be just me, but I have never seen discussions about "amplitude amplification" in which an explicit decomposition in terms of elementary gates was provided. It doesn't seem to be in the original Brassard paper as well. In Grover's case the reflection is easy to compile because the reflection wrt the initial state can be implemented by just acting locally (via the $H^{\otimes n}$) and changing phases in the computational basis. I don't know if this would work for more general initial states. Eh, this might make for a good new question actually $\endgroup$
    – glS
    Nov 1, 2019 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.