The Quantum Pontiff

Long article appearing on CNNmoney written for Fortune magazine on quantum computers. My favorite quote from the article:

But quantum computing scientists are surprisingly bullish, for scientists. “This is the most exciting time of my life, and I’m not young,” says Eli Yablonovitch, professor of electrical engineering at UCLA. “We’re looking forward to a direct impact on everybody in the world.”

And the most interesting quote is

Granted, changing the spin of an electron is a long way from building a circuit out of the same, and history is littered with promising technologies that didn’t pan out. Intel CEO Paul Otellini is one major quantum skeptic, increasingly reluctant to fund R&D for it. Reports of the death of silicon have been greatly exaggerated, he says

What is interesting, I think is that the article makes it sound like Paul Otellini thinks that quantum computers are somehow meant to be computers “beyond Moore’s law,” i.e. as a technology that moves beyond today’s Silicon based transistor technology. I think this is kind of crazy. The point of quantum computers is not that they will be “beyond Moore” but that there is an entirely new form of computing beyond the form of computing we are executing today. I’m skeptical of quantum computers as devices “beyond Moore’s law” too, mostly because I figure there is always a factor in the error correction needed to achieve quantum error correction over classical error correction. Thus any quantum computer I design, say from the single spin up, could probalby be put to use as a classical computer with less overhead needed for error correction. I think this view of quantum computers comes about because an argument made for quantum computing is usually to put up Moore’s law and point out that if it continues, it will eventually make atom sized transistors. This is kind of a silly argument and hides the idea that the reason you build a quantum computer is because it is an entirely new form of computation.

I think if I had to choose an official question for quantum computing it would be the question “where are all the quantum algorithms?” I mean, every time I talk to someone outside of quantum computing it seems like this is the first question they ask (followed closely by “when is a large quantum computer going to be built?”)
Of course this question ignores a lot of hard work put in by a lot of people to come up with new quantum algorithms. Efficient quantum algorithms like solving Pell’s equation, estimating certain Gauss sums, solving hidden shift problems (more here), and solving certain non-abelian hidden subgroup problems, just for example. But when you mention these algorithms, you invariably find that these algorithms are just viewed as “variants of Shor’s algorithm.” In a sense this is true, but how true is it? Certainly many of the algorithms listed above require a lot more than “just Shor.”
In my mind it is useful to partition Shor’s algorithm for factoring into two parts (pun, pun, pun.) One part of Shor’s algorithm is the part of the algorithm that uses a fourier transform to efficiently solve a hidden subgroup problem. The second part is realizing that the solution of a hidden subgroup problem can be used to efficiently factor. What most people mean when they say that our quantum algorithms are “just Shor” is that they mimic the first part of the algorithm, i.e. they use a fourier transform. And indeed, all of the algorithms I list above use, in some manner, quantum fourier transforms. But they certainly don’t necessarily use them in the same, straightforward, manner they are used in Shor’s algorithm.
Last week I was in San Diego at a meeting on quantum algorithms. During part of the meeting we broke up into small groups and attempted to reason about where the field of quantum algorithms was going and then regroup to hear what each group had said. Wim van Dam made the following observation, which I found both funny and very striking. Wim noted that the Toffoli gate and the Hadamard gate are universal for quantum computing (see here for a simple proof by Dorit Aharonov.) The Toffoli gate is, of course, a “classical” gate which is universal for classical computation. The Hadamard gate is nothing more that the quantum fourier transform over the simplest of all groups, the cyclic group with two elements, Z_2. What does this mean? This means, as Wim said, that EVERY QUANTUM ALGORITHM IS NOTHING MORE THAN FOURIER TRANSFORMS AND CLASSICAL COMPUTATION! Ha! I love it!
Of course this points out the absurdity of in calling all algorithms after Shor, “like Shor.” Certainly they bear a resemblance, but isn’t this resemblance due to the fact that classical computations plus fourier transforms is all the quantum algorithms will ever be able to achieve? In one manner I ask this question in jest, but in another more serious manner, I do not think this view is all that crazy. That universal gate set of classical computing plus the Hadamard is, I think, a striking result. Might it be a key to understanding all our quantum algorithms and coming up with new ones? I think this is a great question and since I won’t be teaching until winter term I will have plenty of hours to mull it over!

DARPA (Defense Advanced Research Projects Agency) has, over the years, been an important source of funding for all sorts of important computer science research (It was [D]ARPA funding which helped start the Internet!) For example, DARPA was an early and important source of funding for quantum computing research. Recently, there have been claims that DARPA has shifted its focus from more long term projects to more short term and classified programs. Here is a very interesting article about this controversy and, in particular, about the rebuttle of these charges by DARPA director Tony Tether in front of a House science committee meeting.