Category: Quantum

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.

The Perimeter Institute along with the University of Waterloo together form probably the largest concentration of the theorists in quantum computing in the world. And they just keep growing! So, in the past few years, I have been calling those two institutions “the black hole of quantum computing.” When I told this to Andrew Landahl at a meeting I was just attending in San Diego, he came up with a great correction to my description. Really I should have been calling it “the blackberry hole of quantum computing!”

A previous article on the meeting at Bell labs that I attended. Notable:

The National Institute of Standards and Technology and the super-secret National Security Agency are backing U.S. quantum projects.
NSA spokesman Ken White declined to elaborate, “given the sensitivities about our work to understand the secret communications of our foreign adversaries while protecting our own communica tions, and given our desire to preserve our nation’s unique advan tages in these pursuits.”

Ack. Quick, better shut down quant-ph!

Via Michael Nielsen comes the first announcement of QIP 2006

Dear Colleagues,
This is the first announcement for the tenth QIP (Quantum Information
Processing) Workshop, to be held in Brisbane, Australia, from January 30
through February 3, 2007.
The deadline for abstract submission for contributed talks (long and
short) and for posters is 4 November, 2006.
The deadline for early bird registration is 24 November, 2006.
Full details are available at the workshop website:
http://qipworkshop.org/
Hope to see you in Brisbane in 2007!
Regards,
Michael Nielsen

QIP is the premier quantum information science conference for theorists (why it is called a workshop is beyond me!) I’m teaching winter term, but I hope to be able to take the week to attend QIP.
As a dedicated consipiracy theorist, I think it is interesting to note that QIP has been moving towards progressively warmer climates. I mean the QIPs in the early 2000s were all totally freezing (-12 is cold in both F and C) or accompanied by major storms. I suspect this is a sign of the maturation of the field. On the other hand, Brisbane was the site of a horrible massive huricane last year (crap I hope I didn’t just jinx Brisvegas.)