Posts

Posted on

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!

Posted on

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.

Posted on

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

Posted on

Back To Tech, Back to Unreality

I’m at SQuint 2007 which is being held on the campus of Caltech this year. Quite a turnout this year: something like 150 people attending! In fine Caltech tradition the night of my arrival I got pretty much no sleep. And I keep getting the feeling that I have a homework due somewhere on campus.
Cool work by Patricia Lee at NIST:

Abstract. We report on the experimental demonstration of radio frequency addressing of atoms in every other site of a double-well optical lattice, independent of their nearest neighbors at a distance of less than an optical wavelength. By dynamically controlling the lattice and the vector light shifts, the atoms’s spatial and spin degrees of freedom are entangled in each double well. We have also observed a coherent spin-exchange interaction between pairs of atoms in the double-well lattice, which can be used as a mechanism for a square-root-of-swap gate.

During the talks on quantum error correction, it was mentioned that in the very cool threshold paper of Aliferis, Gottesman, and Preskill (quant-ph/0504218), they call the inductive proof of the threshold theorem for fault-tolerance the “threshold dance.” This, of course, brings up the interesting question of what the dance moves are in this dance and the even more important question which is should this dance be part of my upcoming wedding?

Posted on

For 100 Billion I Could Do It, I Think

From a Boston Herald article (appears to be an AP news release):

“Users don’t care about quantum computing – users care about application acceleration. That’s our thrust,” he said. “A general purpose quantum computer is a waste of time. You could spend hundreds of billions of dollars on it” and not create a working computer.

And you’re probably happy that you don’t have an account on fool.com or else you might read this article comparing the demonstration to December 17, 1903.

Posted on

IICQI 2007

Want to go to Iran for a quantum computing conference? IICQI07, website here:

The first International Iran Conference on Quantum Information (IICQI) will be held at Kish Island 7-10 September 2007. The conference will feature the latest developments in theoretical and experimental quantum information science, feature talks by leading international researchers, and provide the opportunity for research discussions and collaborations between international and Iranian quantum information researchers.

Posted on

QEC07

A new conference: the First International Conference on Quantum Error Correction. QEC07 website here. Dec 17-21, 2007:

Quantum error correction of decoherence and faulty control operations forms the backbone of all of quantum information processing. In spite of remarkable progress on this front ever since the discovery of quantum error correcting codes a decade ago, there remain important open problems in both theory and applications to real physical systems. In short, a theory of quantum error correction that is at the same time comprehensive and realistically applicable has not yet been discovered. Therefore the subject remains a very active area of research with a continuing stream of progress and breakthroughs.
The First International Conference on Quantum Error Correction will bring together a wide group of experts to discuss all aspects of decoherence control and fault tolerance. The subject is at this point in time of a mostly theoretical nature, but the conference will include talks surveying the latest experimental progress, and will seek to promote an interaction between theoreticians and experimentalists.
Topics of interest include, in random order: fault tolerance and thresholds, pulse control methods (dynamical decoupling), hybrid methods, applications to cryptography, decoherence-free subspaces and noiseless subsystems, operator quantum error correction, advanced codes (convolutional codes, catalytic, entanglement assisted, …), topological codes, fault tolerance in the cluster model, fault tolerance in linear optics QC, fault tolerance in condensed matter systems, unification of error correction paradigms, self-correcting systems, error correction/avoidance via energy gaps, error correction in adiabatic QC, composite pulses, continuous-time QEC, error correction for specific errors (e.g., spontaneous emission), etc.