Grover's algorithm
We are given a function $f(a)$ such that $f(a)=0$ for all of the $N$ possible values of $a$, except when $a=\omega$ in which case we have $f(\omega)=1$. Assuming that this $f(a)$ can be calculated using a classical reversible code or hardware, we can find $\omega$ with $\mathcal{O}(\sqrt{N})$ steps using a quantum circuit as opposed to a classical computer which will on average require $N/2$ evaluations of the function $f(a)$.
Adiabatic version (1996, Farhi & Gutman)
We are given a Hamiltonian $H$ and we are told that the eigenvalues corresponding to all of the $N$ possible eigenvectors $|a\rangle$ are 0, except when $|a\rangle= |\omega\rangle$ in which case we have an eigenvalue of 1. Assuming this Hamiltonian can be calculated by a quantum computer, we can find $|\omega\rangle$ with $\mathcal{O}(\sqrt{N})$ runtime on an adiabatic quantum computer as opposed to a classical computer which would require checking on average $N/2$ eigenvectors for a diagonal Hamiltonian $H$.
Notice that the above two paragraphs are the same except "function" is now "Hamiltonian" and $a$ is now $|a\rangle$ and $\omega$ is now $|\omega\rangle$.
Do we need to know the "answer" in advance?
Basically, in the circuit-based version you need some classical code/hardware (possibly black-box!) that can give you the function $f$ on demand.
- It could be the case that the person that wrote that code or built that hardware, used an unstructured database of $f(a)$ values to make it, and while doing so they found the needle $\omega$ in the haystack of $a$ values.
- Maybe they even used the fact that $f(\omega)=1$ and $f(a)=0$ for all other $a$ in order to build the classical circuit, so they knew the golden $\omega$ value in advance.
The point is that you don't know the $\omega$ value, and maybe the person who wrote the code doesn't either (they could have forgot, or they won't tell you, or they never knew in the first place). If you have a spreadsheet with a long column with every entry being 0 except for one that is a 1, sure the person who made the spreadsheet may know where the 1 is, as does the computer does, but you don't know it. The same is the case for the Hamiltonian $H$ in the adiabatic version, which I'll explain in more detail below.
Detailed explanation of the 1996 adiabatic version:
We are given $H = |\omega\rangle \langle \omega |$ which has an eigenvalue of 1 for the eigenvector $|\omega\rangle$ and an eigenvalue of 0 for all other eigenvectors $|0\rangle$. There is some quantum hardware (a packaged system of qubits with certain couplers and fields) embodies the Hamiltonian $H$. This hardware might be a black-box, and the person who made it may or may not know $|\omega\rangle$ but the point is that you don't know $|\omega\rangle$ and you want to find it.
Pick a random state $|s\rangle$ and add the Hamiltonian $|s\rangle \langle s |$ to the Hamiltonian you were given earlier. You can easily do this physically, by simply adding the couplings and fields in $|s\rangle \langle s |$ to whatever was present in the package you started with.
Starting with $|s\rangle$ and calculating the state at time $t$ by $|\psi \rangle = e^{-\textrm{i}Ht} | s\rangle$ results in the following state (in the 2D subspace with basis states $|\omega \rangle$ followed by $|s\rangle$):
$$\tag{1}
|\psi \rangle = e^{-\textrm{i}t} \begin{pmatrix}
x \cos (xt) - \textrm{i} \sin (xt) \\
\sqrt{1-x^2} \cos(xt)
\end{pmatrix},
$$
where $x = \langle s | \omega \rangle$. The probability of finding your desired state $|\omega \rangle$ is then:
$$\tag{2}
|\langle w| \psi \rangle |^2 = \sin^2(xt) + x^2 \cos^2(xt).
$$
The probability of finding the system in the desired state $|\omega \rangle$ will be 1 when $t = \frac{\pi}{2x}$ and since the expected values of $x$ is $\mathcal{O}(1/\sqrt{N})$ if you pick a nomralized $|s\rangle$ randomly we will have $|\langle s | \omega \rangle |^2 = 1/N$, so the runtime $t = \mathcal{O}(\sqrt{N})$.
Adiabatic version (2001, van Dam, Mosca, Vazirani)
Here the eigenvalues in the final Hamiltonian are 1 for all states $|a\rangle$ except for $|\omega \rangle$ which has eigenvalue 0:
$$\tag{3}
H = \sum_{a\ne \omega} |a\rangle \langle a|.
$$
The initial Hamiltonian is defined similarly but in the Hadamard basis and with ground state $|0\rangle$:
$$\tag{4}
H_i = \sum_{a\ne 0} |\bar{a}\rangle \langle \bar{a}|.
$$
The time-dependent gap between the two lowest eigenvalues of the time-dependent Hamiltonian:
$$\tag{5}
\left( 1 - s \right) H_0 + s H,
$$
where $s\equiv t/T$ is:
$$\tag{6}
g(s) = \sqrt{\frac{N + 4(N -1)(s^2 - s)}{N}}.
$$
At $t = T/2$ we get $g(s) = \min_s g(s) = 1/\sqrt{N}.$
Now to get the runtime, we calculate:
\begin{align}
\int_{s=0}^1 \frac{1}{g(s)^2} \textrm{d}s &= \frac{N\arctan{\left(\sqrt{N-1} \right)}}{\sqrt{N-1}}\tag{7}\\
&= \mathcal{O}(N/sqrt{N})\tag{8}\\
&= \mathcal{O}(\sqrt{N})\tag{9}.
\end{align}
Some extra notes
I'll also give you some notes I made on the 1996 paper years ago. It took me so long to find the file on my computer, so it's probably a good thing anyway that I've now been convinced by you to share them more publicly:
- The paper didn't mention that if you are unlucky enough to pick and $|s\rangle$ that is orthogonal to $|\omega \rangle$, your probability of getting $|\omega\rangle$ becomes 0 (just plug $\langle s |\omega \rangle = x=0$ into Eq. 2. Another way to think of this is to say that the runtime would be $t = +\infty$ if you were unlucky enough to pick this state.
The way I found around this was to bound the runtime by some maximum time $t_{\textrm{max}}$ and if that time limit is reached, give up on the chosen $|s\rangle$ and try a different one. How big does $t_{\textrm{max}}$ have to be though? The paper doesn't say.
- The algorithm involves picking a random vector $|s\rangle$. For some vectors, the time it takes for $P(t)$ (ie. the probability of finding $|w\rangle$, defined in Eq. 2 to become 1 will be short (such as if $|s\rangle$ happens to be $|w\rangle$), and for some it will be long. On average the authors say the runtime will be $\mathcal{O}(\sqrt{N})$. Out of all possible random vectors $|s\rangle$ that can be chosen, if it is possible that $\sqrt{N}$ of them require runtimes of $t_{\textrm{max}}$ worse than $\mathcal{O}(\sqrt(N))$, then we would need to run the algorithm for worse than $\mathcal{O}(\sqrt{N})$ each time ($t_{\textrm{max}}$ would have to be worse than $\mathcal{O}(\sqrt{N})$), or we might want to run the algorithm for a time $t_{\textrm{max}} = \mathcal{O}(\sqrt{N})$, but more than $\mathcal{O}(\sqrt{N})$ times, making the total runtime bigger than $N$. The classical runtime for the search is at worst $kN$ where $k$ is the time it takes to check whether or not one entry of the database (one input for the function) has the value (gives the output) we're seeking, so it's possible for a classical computer to get the answer faster than this quantum-based algorithm, but unless we are met with this type of bad luck, the quantum-based algorithm should give us the answer with a runtime of $\mathcal{O}(\sqrt{N})$.
