Author: dabacon

The world is quantum mechanical, damnit, and so (the party line goes) it shouldn’t be surprising if we find that a theory of computation based on quantum theory is more elegant than one based on machines whose concept of reality is so restrictive as to not allow cats both alive and dead. Okay, so we can say this half in jest, half seriously, but does it really hold any water? In order to solve this question of asthetics (joke about mathematics deleted), I propose that we hold a Quantum versus Classical beauty contest. Now since quantum computers are at least as powerful as classical computers, we can’t just say that an algorithm is better because it has a better runtime or better use of space, etc. Instead we need to use our artistic taste, i.e. pretend we have a clue about what it means for a result to be elegant (and yes, that was a dig at a certain popular science book 😉 )
Round 1
So I propose we perform this artistic measuring with a quantum versus classical exponent SMACKDOWN! (the exclamation mark is a part of the word.) Consider, for example, the recent quantum algorithm for evaluating a NAND tree (here and here with an explanation by the traveling complexity theory salesman here. Also the awesome NAND formula paper here) This quantum algorithm has a running time of [tex]$O(N^{1/2 + epsilon})$[/tex]. Now compare this with the best and optimal classical algorithm for this problem. The result? [tex]$O(N^{0.753 dots})$[/tex] where [tex]$0.753 dots approx log_2(1+sqrt{33})-2$[/tex]. Bleh. Round One of the Quantum Versus Classical Exponent SMACKDOWN! most certainly goes to the quantum world. One half is certainly better than something which is has both a logarithm and a square root of thirty three!
Round 2
But ha, say the classical complexity theorists. What about Grover’s problem? Sure in this unstructured query search the quantum world achieves a speedup from [tex]$O(N)$[/tex] classically to [tex]$O(N^{1/2})$[/tex] quantum mechanically, but look at your exponent. One half? Who the hell ordered one half. I mean if you had gotten log of N or even constant, then you would have something to brag about. But a square root speedup. Who ordered that? Round two of the Quantum verus Classical Exponent SMACKDOWN! most certainly goes to the classical world were weird square root speedups are not ubiquitous for straightforward unstructured query searches.
Round 3
To be continued!

The Keck Foundation helps support the new Center for Extreme Quantum Information Theory at MIT (xQIT). Seth Lloyd and Jeffrey Shapiro to lead the new center.

Bah (posted without long line of four letter words I would really like to print but am forced, by my good nature and good upbringing, to avoid printing on this family friendly blog.):

“Businesses aren’t too fascinated about the details of quantum mechanics, but academics have their own axes to grind. I can assure you that our VCs look at us a lot closer than the government looks at the academics who win research grants,” Martin said.

Note to D-wave. We aren’t skeptical that you built a device. We are skeptical that your path forward will ever work (some more skpetical than others…me I’m an optimist!) and we are even more skeptical of your statements trying to sell quantum devices by advertising unsubstantiated computational power. I also know VCs who looked closely at your company and said something very similar to what those lazy no good bum academics are saying.