Can adiabatic quantum computing be faster than Grover's algorithm?

Question

It has been proven that adiabatic quantum computing is equivalent to "standard", or gate-model quantum computing. Adiabatic computing, however, shows promises for optimisation problems, where the objective is to minimise (or maximise) a function which is in some way related to the problem – that is, finding the instance that minimises (or maximises) this function immediately solves the problem.

Now, it seems to me that Grover's algorithm can essentially do the same: by searching over the solution space, it will find one solution (possibly out of many solutions) that satisfies the oracle criterion, which in this case equates to the optimality condition, in time $O(\sqrt N)$, where $N$ is the size of the solution space.

This algorithm has been shown to be optimal: as Bennett et al. (1997) put it, "the class $\rm NP$ cannot be solved on a quantum Turing machine in time $o(2^{n/2})$". In my understanding, this means there is no way to construct any quantum algorithm that finds a solution by searching through the space faster than $O(\sqrt N)$, where $N$ scales with the problem size.

So my question is: while adiabatic quantum computing is often presented as being superior when it comes to optimisation problems, can it really be faster than $O(\sqrt N)$? If yes, this seems to contradict the optimality of Grover's algorithm, since any adiabatic algorithm can be simulated by a quantum circuit. If not, what is the point of developing adiabatic algorithms, if they are never going to be faster than something we can systematically construct with circuits? Or is there something wrong with my understanding?

Answer 1

Good question. For unstructured search, adiabatic quantum computation indeed gives the exact same $\sqrt{N}$ speedup that the standard gate-based Grover's algorithm does, as proven in this important paper by Roland and Cerf. This agrees with the equivalence between adiabatic and gate-based quantum computation that you mentioned.

(One minor correction to your question: you're correct that in the setup for the oracle-search problem, you need to frame your search query as a yes/no question that the oracle can answer. But the question isn't actually taken to be "does $x$ extremize the function $f(x)$?", as you proposed. Instead, it's "is $f(x)$ less than or equal to $M$?" See slides 9 and 10 here. That's because an oracle for the latter question is considered a more realistic model for a physical setup, where it's conceivable that one could directly compute or measure $f(x)$ for a given $x$, but not $f(x) - f_\text{min}$.)

Nevertheless, there are two potential advantages to adiabatic QC, both of which are difficult to study theoretically. The first is practical: actually building large coherent quantum circuits is a whole lot harder that just drawing them in a journal article. Even though adiabatic QC doesn't have any fundamental advantage over the traditional setup, it might be much easier to implement experimentally.

Secondly, the same huge caveat applies to AQC as to the standard Grover's algorithm: it only applies to unstructured or "black-box" search, where we complete ignore any correlations between the answers that the oracle gives when fed in "similar" or "related" queries. Any actual search problem that we care about will by definition have some structure to it, although this structure may be far too complicated for us to analyze. For example, if we think of the function to be extremized as an energy landscape, it seems reasonable that the system can more easily tunnel between "nearby" local minima than between "faraway" ones.

So to really rigorously compare the relative benefits of the adiabatic vs. gate-based setups in a real experiment, you'd need to "overcome the relativization barrier" and consider the structure of the specific function that you're trying to extremize, which is usually really hard to do. This makes it very difficult to draw general conclusions about the two approach's relative advantages in the real world. It's also why it's so hard to prove unconditional complexity separations theoretically. For all we know, for real-world rather than oracle problems, quantum computers might be able to give exponential speedups - possibly even for NP-complete problems, which would imply that NP $\subset$ BQP, although this is considered very unlikely.

Answer 2

Adiabatic quantum computation cannot do anything faster than circuit-based quantum computation from a computational complexity perspective. This is because there is a mathematical proof that circuit-based quantum computation can efficiently simulate adiabatic quantum computation [see section 5 of this paper].

can it really be faster than $\mathcal{O}(\sqrt{N})$?

The answer is no. This is because if AQC could do it in, say, $\mathcal{O}(\log{N})$, then circuit-based QC could also do it in $\mathcal{O}(\log{N})$ by the algorithm in section 5 of the paper I linked above. This would violate the optimality of $\mathcal{O}(\sqrt{N})$ for unstructured search.