My question concerns a proof in https://people.eecs.berkeley.edu/~vazirani/pubs/qao.pdf, "Limits on Quantum Adiabatic Optimization - Warning: Rough Manuscript!" by Wim van Dam and Umesh Vazirani. It seems that it was never completed, although it has been cited several times since. In particular, Lemma 2 states (summarized and paraphrased):

If a quantum adiabatic algorithm is carried out on a graph of size $n$ with diameter $w$, with a Hamiltonian whose entries are polynomial in $\log(n)$, the optimization will take time $2^{(w \log w)}$

This is a bit interpretation on my part, because the proof is very incomplete and inconsistent. Now, if this statement is true, we could* apply it to an expander graph with degree $d = \log^k(n)$, and get a graph of width $w = c\log(n)/\log(d)$ for some constant $c$.

That would imply a runtime of

$$d 2^{w\log w} = \log^k(n) 2^{(c \log n/k \log\log n) (\log\log n)} \le \log^k(n) 2^{(c \log n/k)}$$

Then by taking $k$ to be sufficiently large, say, $4/c$, this gives you a $poly(log(n))*2^{\log(n)/4}$, which appears to outperform Grover's algorithm, which is strong evidence that something here has gone wrong. :) As pointed out in the second answer to this question, there might currently be some loopholes to allow adiabatic computing to outperform gate models, but that seems extremely unlikely -- I assume I am not understanding the Lemma 2 from van Dam's manuscript, or the relevant expander graphs don't exist somehow (e.g. $c$ would depend on $n$ in some nontrivial way or something.)

Can anyone explain what's going on here, and perhaps provide a proof of that Lemma 2?

[*] This requires the existence of a such a graph. Moore graphs seem sufficient (a degree-$d$ tree branching out for $w$ levels). Ramanujan graphs might work, if they exist small enough; for example, for the case of Ramanujan graphs, the second-largest eigenvalue is bounded by $\lambda_2 \le 2\sqrt{d-1}$, and the edge expansion is lower-bounded by $\frac{1}{2}(d-\lambda_2) \ge \frac{d}{3}$. A graph with $n$ vertices and edge expansion $\phi$ has diameter bounded by $2\log(n)/\log(1+\phi)$.

  • $\begingroup$ hmm if I insert $d=3$ I get $1/2(3-2\sqrt 2)=0.08\ngeq 1$ $\endgroup$ – draks ... May 6 '20 at 9:59
  • $\begingroup$ Sorry @draks..., I was being a little bit sloppy there, I was speaking asymptotically. I mean that if $\lambda_2$ is at most $O(\sqrt{d})$, then $\frac{1}{2}(d-\lambda_d) = \frac{1}{2}(d-O(\sqrt{d})) \approxeq \frac{d}{2}$. The inequality I wrote there is only true assuming $d\ge 35$, but I'm considering the large-$d$ case anyway. $\endgroup$ – Alex Meiburg May 6 '20 at 17:50
  • $\begingroup$ Oh, sad, I'm interested in cubic graphs. Can one say something about their diameter as well? $\endgroup$ – draks ... May 6 '20 at 17:53
  • $\begingroup$ @draks... There are cubic Ramanujan graphs, see link.springer.com/article/10.1007%2FBF01285816 . This means an edge expansion of at least 0.08, as you said, so those graphs have diameter at most $2\log(n)/\log(1+0.08) = 26.7 \log(n)$. So those are graphs you can traverse efficiently. $\endgroup$ – Alex Meiburg May 6 '20 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.