X-posted on physics.stackexchange

In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic speedup over the best possible classical algorithm.

On the gate model of quantum computing, a phase oracle is used in Grover's algorithm. The phase oracle can be implemented by simulating the classical circuit that defines the function $f$, where $f$ indicates if an element (of the database for example) is marked ($f(x) = 1$) or not ($f(x) = 0$).

There exists a version of Grover's algorithm for the adiabatic quantum computer architecture as well.

However here the final Hamiltonian has a very similar form to the phase oracle in the gate model.

The phase oracle had to be constructed with a quantum circuit simulating the classical circuit, that defines $f$.

But in the adiabatic case, how can the final Hamiltonian be constructed?

The problem is, that the Hamiltonian contains a projector onto the unknown state/the marked element.


3 Answers 3


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})$.
  • $\begingroup$ Hello, thank you so much for answering! I have a question: In the 2001 Adiabatic case, we need to apply an interpolation of the blackbox Hamiltonian and our initial Hamiltonian. Do you know how we do this? Do we just control how much of the initial Hamiltonian we add? $\endgroup$ Commented May 3, 2021 at 20:26
  • 1
    $\begingroup$ @MahathiVempati This would depend on how the Hamiltonian is given to us: for example, let's say we are given the qubit-qubit couplings (quadratic terms) and field strengths for each qubit (linear terms), without being told which state $|a\rangle = |\omega \rangle$ is the jackpot. At the half-way point, we would simply apply those couplings and field strengths with equal weight compared to how we would apply the couplings and field strengths for the initial Hamiltonian. At the beginning we would only apply the couplings and fields of the initial Hamiltonian. We weight everything by $s=t/T$. $\endgroup$ Commented May 3, 2021 at 22:07
  • $\begingroup$ The runtime of the adiabatic algorithm depends on the energy gap and scales as the square root of N, just like Grover's original algorithm. However, Grover's algorithm requires a precise number of iterations based on the number of solutions, while the adiabatic process should not oscillate. can we use the adiabatic process without knowing the number of solutions, possibly running a bit more slowly? $\endgroup$
    – inq
    Commented Jul 26, 2023 at 23:14
  • $\begingroup$ Yes we can use it. $\endgroup$ Commented Jul 27, 2023 at 13:21

For adiabatic Grover you want the ground state of the final Hamiltonian to be the marked item. The key idea with Grover is that the item is hard to find but easy to verify. So the idea is you embed the 'easy to verify' into the Hamiltonian, which is the similar as marking the item via the phase oracle in the gate model.

For example consider a simple case where the database is an unordered collection of integers $\mathcal{D} = \{z: z \in \mathbb{Z}\}$ given in a binary representation $z = \{0,1\}^n$. We want to find the $x \in \mathbb{Z}$ item, thus we want our Hamiltonian to have it ground state when $x = z$.

The easiest way to encode this, for a predetermined $x$ value, the easy to verify part, is $\min (x - z)^2 \rightarrow z$. If we expand this out with the binary encoding for $x$ and the $z$ variables we can can get a system of second order interactions which we can assign coupling strengths to. This gives us the final adiabatic Hamiltonian with a ground state for $x = z$.

Of course this is a trivial example, instead consider an item defined by $M$ qubits, we could use the first $n$ qubits to encode a unique 'label' and then $M-n$ qubits to encode the item data. Therefore we can use the above method to search for an item with label $x$, where the Hamiltonian does not act on the $M-n$ data qubits.

  • $\begingroup$ In your third paragraph, how exactly would the final Hamiltonian look like in this case and what would be the dimension of the Hilbert space it acts on? Wouldn't the marked element x still be a parameter of this Hamiltonian? $\endgroup$ Commented Apr 13, 2021 at 14:13
  • $\begingroup$ you would have to predefine $x$, so say I want to find the element $x=3$, assuming I am using a 2 qubit representation, I then use the binary representation $[11]$ or using the binary coefs $(2 + 1)$ then expand out $ ((2 + 1) - (z_2 + z_1) )^2$ to find the coupling and field terms for the $z$ qubits as the coefficents of the expanded terms of $z_1$ and $z_2$. Then just arrange these into a matrix. n.b. You will get a constant term $K$ in the expansion that can't be directly added to the Hamiltonian but this can be ignored as it only shift the value of the minimum, not the location. $\endgroup$
    – Sam Palmer
    Commented Apr 13, 2021 at 14:28
  • $\begingroup$ If I understand correctly, your approach only works if you already know that x = 3, which makes the algorithm pointless. Thinking about the practical implementation of the final Hamiltonian, where you don't know x, the only thing known is that f(x) = 1 and f(y) = 0 for all other configurations y != x. The couplings in the (2-local) final Hamiltonian almost all depend on x, and these coupling-strengths have to be known in order to implement them. $\endgroup$ Commented Apr 13, 2021 at 17:45
  • $\begingroup$ You need to know what you are looking for, so you need some sort of input, as I said that is an extreme simple example, but the concept is the same where you need to encode f(X) as a ground state. For example if you want to find all odd numbers then set the Hamiltonian so the bit $z=1$ has a field of say -100, then the ground state will be a superposition of all odd numbers. $\endgroup$
    – Sam Palmer
    Commented Apr 13, 2021 at 18:19
  • $\begingroup$ Ok, but how would you implement the function f, if f had no mathematical structure that you can make use of? Let's say f would be a hash function, mapping an input bitstring to an output bitstring using a bunch of logical gates (the exact definition of f in terms of locial gates is known). One chosen output bit-string is mapped to the number 1 and all other output bit-strings are mapped to 0. The goal is to find the input bit-string x, which is mapped to 1. In the circuit model, the phase oracle can (theoretically) easily implement f by simulating the classical circuit defining it. $\endgroup$ Commented Apr 13, 2021 at 19:07

For me, Sam Palmer's answer starts to have the right sort of structure. But, for the sake of being more explicit:

We're interested in solving problems that are in the class NP, i.e. they have a function that lets you recognise correct answers. It is sufficient for me to talk about one specific case: 3-SAT. That is because this case is NP-complete - every problem in NP can be solved by solving an instance of 3-SAT.

Just to recall 3-SAT: you're given a bunch of clauses on triples of variables, all of which must hold true. So, you can construct positive semi-definite Hamiltonian terms $H_i$ corresponding to each term such that $H_i|x\rangle=0$ if and only if the binary string $x$ satisfies clause $i$. You'd typically want all other eigenvalues of $H_i$ to be well separated from $0$. Indeed, you'd probably set $H_i=\Delta(I-P_i)$ where $P_i$ is a projector onto all the terms satisfying clause $i$.

So, each term $H_i$ encodes your problem specification. Then, $$ H=\sum_iH_i $$ has a ground state energy of 0 if and only if there's a satisfying instance. You only use what you knew of the 3-sat problem specification, and definitely do not already know the answer. Of course, this says nothing about the energy of the first excited state. That's probably a bit messier...


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.