Spidy

Via Saheli, I find a test to determine which superhero I am.
My results:
You are Spider-Man

Spider-Man
85%
Iron Man
75%
Superman
55%
The Flash
55%
Green Lantern
55%
Hulk
50%
Supergirl
48%
Robin
48%
Wonder Woman
43%
Catwoman
35%
Batman
30%
You are intelligent, witty,
a bit geeky and have great
power and responsibility.


Click here to take the Superhero Personality Test

Power and responsibility? Huh.

All of Physics

One thing that bugs the heck out of me, is when I hear particle physicists talk about their field as if it is all of physics. I have a great love of particle physics, so I’m not dissing the field at all, nor arguing that it isn’t more fundamental, but it rubs me the wrong way to disregard all of the rest of physics that is currently going on. This especially irritates me since it gives students the wrong impression that the only exciting physics is in particle physics. (Yeah, I know, I’m in a CS department, so what do I know about physics 🙂 BTW)
Why bring this up? Because over a Nanoscale Views, Doug Natelson has just put up a blog post with a list of Hot Topics and Controversies in condensed matter/nanoscience. And if the topics listed don’t show you an exciting field full of important open problems, then you’re crazy! The eventual goal of the post is to discuss each of the items on this list in latter blog posts which is a great idea which I am sourly tempted to steal and try out here with quantum hot topics and controversies (okay, maybe the entire field is controversial!)

Not Replacing, Enhancing!

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.

Nullius in Verba

In October I get to go to London for the 7th European QIPC Workshop Quantum Information Processing and Communication which is being hosted by the Royal Society of London (Which is cool, because the original society was founded, IIRC, as a meeting to discuss the ideas of one Sir Francis Bacon!) The theme of this workshop is “Physicists and Computer Scientist Reunite!” Here is a blurb which Scott Aaronson produced after taking a huge verbose statement I wrote about this theme (those computer scientists have fine compression algorithms, I do say):

In the early days of quantum information science, physicists and computer scientists could make great progress by just sitting down at the same table and explaining the basic concerns of their respective fields. But those halcyon days are gone. Today the major discoveries of the mid-nineties have essentially morphed into separate disciplines. One can now work on quantum error correction without knowing anything about, say, quantum complexity or ion traps. Whereas the early days were distinguished by conferences in which computer scientists were forced to listen to physicists and vice versa, today the field is large enough that cross-disciplinary traffic has been reduced to a trickle. Yet quantum information is still just a fifteen-year-old teenager, so it would be astonishing indeed if the borderlands between physics and computer science were already picked clean. What connections remain to be discovered? What recent work in physics should computer scientists know about, and vice versa?
Quantum information scientists of the world, unite!

And indeed the workshop will have an interesting format with each one hour time slot consisting of one topic as seem by a more physics perspective and a more computer science perspective. It will be interesting to see if the audience will be able to withstand this dual sided barrage of perspectives!

All You Compute, and All You QFT, Is All Your Life Will Ever Be

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!

Wither Funding?

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.

Quantum Doctor

Here is an interesting article by Dominik Janzing and Thomas Beth, both from Karlsruhe, Germany. The jist of the article is that if the world were more quantum, doctors would have to learn Bell inequalities!

On the potential influence of quantum noise on measuring effectiveness in clinical trials
ABSTRACT:To test the effectiveness of a drug, the medical researcher can instruct two randomly selected groups of patients to take the drug or not to take it. Each group should comply with the instructions exactly or else the causal effect cannot be identified satisfactorily. This holds true even when those who do not comply are identified afterwards, since latent factors such as patient’s personality can influence both his decision and his physical response. However, one can still give bounds on the effectiveness of the drug depending on the rate of compliance. They are described by 16 inequalities. Remarkably, the proofs for these bounds given in the literature rely on models that represent all relevant latent factors influencing patient’s behavior by hidden classical variables. In a strong analogy to the violation of Bell’s inequality, half of the inequalities fail if patient behavior is influenced by latent quantum processes (e.g. in his nervous system). Quantum effects could fake an increase in the recovery rate by about 13%, although the drug would hurt as many patients as it would help if everyone took it. We show that the other eight inequalities remain true even in the quantum case. We do not present a realistic model showing the above effect. We only point out that the physics of decision-making could be relevant for the causal interpretation of every-day life statistical data. Our derivation of the remaining eight inequalities suggests how to avoid problematic hidden-variable models in classical causal reasoning by representing all latent factors by quantum systems.

I’m guessing that this won’t help in the battle physicist’s have when teaching premed students (“Ooooh, but please just give me one more point on this quiz. Pleeeease!”)

Stay At Home Poker Dad

Tired of your job? Good at poker? Do what my friend Ben Foster did, quit your job and play poker online for a living. From the Wired articled linked above:

Last summer, Ben Foster quit his $110,000-a-year job as a senior product manager at eBay to play online poker full-time. In the months leading up to his decision, the 28-year-old with a degree in statistics had been tracking his winnings on a detailed spreadsheet. After checking and rechecking the numbers, he came to the conclusion that he could earn more money playing poker than working at eBay. Plus, his wife was pregnant with their second child, and he was needed around the house. Foster decided to become a stay-at-home poker dad.

[As a side note, Ben has indeed taken much money from me at poker. But that was before I learned to play poker. That was when I learned that I just shouldn’t play with him. “Strange game Dr. FalconFalken, the only way to win is not to play.”]