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!
Quantum Computing to the Max
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.
Skepticism….Check. Axes….Ummm…
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.
They Built….a Brain!
The mystery of what exactly was built up north has been resolved. They built a brain:
Within Holistic Quantum Relativity lies the realm of the human mind and the observable universe running like Quantum Computers: this technological synthesis offers the possibility of solving what computer science calls “NP-complete” problems. Last week D-Wave Systems, a privately-held Canadian firm Headquartered near Vancouver, BC, demonstrated what it calls the world’s first commercially viable Quantum Computer at the Computer History Museum in Mountain View, California. These are problems which are impossible or nearly impossible to calculate on a classical digital computer. Picking out a single pattern from a collection of patterns, such as one’s mother, father, or child, from a photo of people, is easy for the human mind, but beyond the reach of a conventional desk-top computer!
Can't you hear, can't you hear the thunder?
Traveling in a fried-out combie, on a hippie trail, head full of zombie, I found a new quantum blog: we don’t need no “sticking” room 408, it made me nervous, but it linked to me which is sort of like breakfast.
Factoring Bacteria
No sooner do I attack biologists as the common mortal enemy of computer scientists and physicists in my last post when along comes quant-ph/0702203. Yet another nomination, in that great cosmic contest: “best paper title ever!” (said with the comic book guy accent, of course.) quant-ph/0702203:
Purple bacteria and quantum Fourier transform
Author: Samir Lipovaca
Abstract: The LH-II of purple bacteria Rhodospirillum (Rs.) molischianum and Rhodopseudomonas (Rps.) acidophila adopts a highly symmetrical ring shape, with a radius of about 7 nm. In the case of Rps. acidophila the ring has a ninefold symmetry axis, and in LH-II from Rs. molischianum the ring has an eightfold symmetry axis. These rings are found to exibit two bands of excitons. A simplified mathematical description of the exciton states is given in Hu, X. & Schulten, K. (1997) Physics Today 50, 28-34. Using this description, we will show, by suitable labeling of the lowest energy (Qy) excited states of individual BChls, that the resulting exciton states are the quantum Fourier transform of the BChls excited states. For Rs. molischianum ring exciton states will be modeled as the four qubit quantum Fourier transform and the explicit circuit will be derived. Exciton states for Rps. acidophila ring cannot be modeled with an integer number of qubits. Both quantum Fourier transforms are instances of the hidden subgroup problem and this opens up a possibility that both purple bacteria implement an efficient quantum circuit for light harvesting.
Boy are we going to have mud on our face when we discover that Bacteria have beaten even D-wave towards the construction of a useful quantum computer 😉
Welcome to the Feast, Tums Provided
Over at Shtetl-Optimized, Scott goes a little ballistic on criticism he’s received over the wording of his and Umesh Vazirani’s letters to the Economist. (As a side note, it is kind of sad to see such a poorly written article in the Economist: I know for a fact that an early Economist article on Shor’s algorithm drew a lot of great people into the field of quantum computing.) Part of Scott’s issue is with “physicists” insisting on rigor when they themselves are “the headmasters of handwaving.” So when Scott says
Today it is accepted that quantum computers could not solve NP-complete problems in a reasonable amount of time.
and he gets a lot of flack from physicists insisting that his statement might be interpreted as BQP not containing NP, he gets rather ticked off since those “headmasters of handwaving” themselves make all sorts of statements like this and don’t seem to mind. “Double standard!” shouts Da Optimizer!
Now one could take Scott’s rant and turn it into a great computer-science physics flamewar, but what fun would that be? And I’m a softy (or a Chinese restaurant placemat, depending on your perspective), so I’d like to take what Scott has said and turn it around. Therefore, let me declare the following Pontiffical edict:
Welcome to the headmasters of handwaving club, theoretical computer scientists! We’ve got a seat ready for you right here at our table, all full of delightful theorems and lemmas which you can eat….without having to give a proof of their validity. Our feasts our grand, our parties even wilder, and our nights filled with wonder and awe. Sure you may get a little indigestion, what with the unproven or even, dare I mention the word, wrong, theorems, tumbling around in your belly, but look at what you get in return! Did I mention the wild parties?
I guess in my mind, I actually think that computer science and physics have a lot more in common with each other than either side would ever dare admit. For example, researchers from both fields, it seems to me, can be placed (borrowing the terminology of physics only because of stuff in my past light-cone) neatly on a linear diagram from “experimentalist” to “theorist.” Just as “experimental computer scientists” complain to death about the lack of usefulness of the algorithms invented by “theoretical computer scientists”, “experimental physicists” spend vast hours complaining about the indigestability of the vast body of the “theoretical physics.” But every so often, in this tension, the theorist from both sides do something so remarkable and so practically important that the experimentalists get really excited and actually take the theory and put it to use. Similarly, theorists from both sides who don’t take heed of the experimental side of their field are, it seems to me, destined for obscurity. For example a theoretical physicist who ignores the fact that thier pet theory violates nearly every experiment ever performed, or a theoretical computer scientist who works with a model of computation so irrelevant to modern computation that no one notices (and no I don’t put the entire complexity zoo into this category: the reasons for studying the zoo go far beyond simply defining complexity classes so obscure as to be irrelevant…the beauty of the best complexity classes is exactly in their relevance to our real world computation questions.) both share a common destiny in the dustbin of irrelevant results.
So, rejoice, physicist and computer scientists! You masters of the twentieth century, makers of the grandest constructions in the world and in our minds, and find peace in fighting against your common rising enemy: those damn pesky biologists!
And Now a Word From the Funders of the Inventors of the Interwebs
Wired’s “Danger Room” blog interviews DARPA chief Tony Tether:
NS: Does Darpa’s mission change at all when it’s dealing with a low technological surprise as opposed to a high technological surprise?
TT: No. A lot of people think that, when we look at an effort that, unless it’s going to take us 20 years to do it we’re not interested. When we look at ideas and efforts, we look to see what the impact would be if something could be done. And if it takes 20 years, that’s fine. But if it takes a year, that’s fine too. So we evaluate more by the impact of the idea than we do by the length of time it happens to take to do it.
NS: Right.
S: One area that we really are concerned with — quite frankly, I’m a little uncertain about it, so I won’t go into any details – is quantum computing. Quantum computing is where you create a computer that uses the fact that you can have photons or something coherently coupled —
NS: Sure, encryptions.
TT: You can get great, great parallel processing. That is something that, if somebody else got it before us, would be a great technological surprise. And so we’re looking into that.
NS: And that concerns you more than biological [weapons] development or –
TT: No, no. It’s equal. The biological, I think, is a little bit more worrisome because it’s more potentially near-term. But the impact of the quantum computer, if it can be done, will be really, really revolutionary.
NS: But isn’t it a little bit ironic that Darpa is funding BBN [Technologies — one of the original developers of the Internet’s precursor, Arpanet] to do quantum computing? So, aren’t you in some senses bringing about the thing that you’re scared of?
TT: I know, that’s always a worry, isn’t it. And, in some cases, obviously when we are worried about a technology that we don’t want to teach the world how to do, as we’re learning how to do it, well, we put controls on it.
Turing Award Announced
Frances E. Allen wins the Turing Award.
Citation: For pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution.
D-wave Scattering
Da Optimizer makes it into Nature () with comments on D-wave. See, Nature publishes CS researchers! 🙂 Scott expresses the concern most researchers in quantum computing have with the hype:
“If it fizzles out,” he says, “people might say that quantum computing as a whole is just bunk.”
[For a picture of real D-wave scattering, see here.]
