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?


2 Answers 2


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.

  • $\begingroup$ Excellent answer, many thanks! One more thing: what exactly do you mean by "overcoming the relativisation barrier"? $\endgroup$ Jun 18, 2018 at 21:20
  • $\begingroup$ @DonKiwi That's a strange bit of theoretical CS jargon. Often we can't find a proof for a claim, but we can prove a meta-result about what kind of proofs would or wouldn't work to prove the claim. A "barrier" refers to a result that some broad class of proofs aren't powerful enough to prove a claim. For example, any proof that some particular search algorithm for a structured problem gives a faster than $\sqrt{N}$ speedup would need to take advantage of the details of the particular problem structure - because if it didn't then it couldn't possibly be faster than Grover's algorithm, $\endgroup$
    – tparker
    Jun 19, 2018 at 18:59
  • $\begingroup$ which has been proven to be optimal for unstructured search. That's what it means that the proof would need to "overcome the relativization barrier". Similarly, there exists an oracle $O$ relative to which $\mathbf{P}^O = \mathbf{NP}^O$, so any prove that $\mathbf{P}\neq \mathbf{NP}$ cannot relativize either (it can't use oracles). Remarkably, some proofs do relativize; for example, the proof of the time hierarchy theorem. This means that not only is $\mathbf{P} \neq \mathbf{EXPTIME}$, but $\mathbf{P}^O \neq \mathbf{EXPTIME}^O$ for any oracle $O$! $\endgroup$
    – tparker
    Jun 19, 2018 at 19:06
  • $\begingroup$ Ah, this makes sense now. I'll be really interested to see any developments in this area. $\endgroup$ Jun 20, 2018 at 21:29

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.

  • $\begingroup$ I wonder where the downvote came from... $\endgroup$ Oct 23, 2018 at 22:40
  • 1
    $\begingroup$ This claim does not follow from the linked paper: there it is only shown that a circuit-based quantum computation can simulate an adiabatic one with at most a polynomial overhead. It might follow however from more recent results on Hamiltonian simulation. $\endgroup$
    – smapers
    Mar 11, 2020 at 14:25
  • $\begingroup$ @smapers: I do not understand what you are trying to say. $\endgroup$ Mar 11, 2020 at 15:48
  • $\begingroup$ You are claiming that AQC cannot be faster than CQC because CQC can efficiently simulate AQC. The reference that you provide only proves this up to a polynomial overhead, so that a $T$-step AQC might for instance take $T^2$ steps in the circuit model. As such, this argument does not exclude, for instance, an AQC search algorithm with complexity $O(N^{1/4})$. $\endgroup$
    – smapers
    Mar 11, 2020 at 15:54
  • 1
    $\begingroup$ I don't agree: simulation of Hamiltonian evolution in the circuit model is a highly nontrivial problem. What you seem to be saying is "simply apply the gate $\exp(-iH(t)\delta)$" at timestep $t$, but you cannot simply do that in the circuit model: your circuit must be built up from some fixed set of gates. $\endgroup$
    – smapers
    Mar 12, 2020 at 7:13

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.