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?

up vote 5 down vote accepted

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 $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.

  • Excellent answer, many thanks! One more thing: what exactly do you mean by "overcoming the relativisation barrier"? – Dyon J Don Kiwi van Vreumingen Jun 18 at 21:20
  • @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, – tparker Jun 19 at 18:59
  • 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$! – tparker Jun 19 at 19:06
  • Ah, this makes sense now. I'll be really interested to see any developments in this area. – Dyon J Don Kiwi van Vreumingen Jun 20 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.

  • I wonder where the downvote came from... – user1271772 Oct 23 at 22:40

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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