# van Dam's proof for adiabatic optimization and graph diameter

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

• hmm if I insert $d=3$ I get $1/2(3-2\sqrt 2)=0.08\ngeq 1$ – draks ... May 6 at 9:59
• 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. – Alex Meiburg May 6 at 17:50
• Oh, sad, I'm interested in cubic graphs. Can one say something about their diameter as well? – draks ... May 6 at 17:53
• @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. – Alex Meiburg May 6 at 20:38