Posted by: jonkatz | February 15, 2011

Quantum computers impractical?

Interesting food for thought from Ron Rivest (at least according to this article):

…there’s not likely to be any motivation for building [a quantum computer], since it might have no other real purpose than defeating RSA — and once it was in existence, everyone would stop using RSA, so “there would be no use for it anymore.”

Advertisements

Responses

  1. Besides that quantum computers have unbounded applications beyond cryptography, this still seems senseless. To paraphrase, there is not likely to be any motivation for breaking *any* cryptosystem, since once it was in existence everyone would stop using that cryptosystem.

  2. Ron Rivest, it goes without saying, is much smarter than me. But still I don’t see how he can claim that quantum computers will be useless for anything beyond factoring.

    First of all this ignores a large body of research on using quantum computers to simulate quantum systems. If you look at where a large chunk of, say, the DOEs use of supercomputing CPU cycles go, it is explicitly toward simulating quantum systems. So I’d call this problem “quite practical.” Quantum simulation was, of course, one of the original motivations for thinking about quantum computers, and is likely to be their most practical application. For interesting papers to read about recent progress in quantum simulations I recommend http://arxiv.org/abs/0911.3635 and http://arxiv.org/abs/1001.1130 . There are lots of great open questions about quantum simulations, but already one can see the outlines of some very powerful tools. Talking, for example, with my physical chemist friends, makes me very optimistic about even the most basic things we currently know how to do using quantum computers.

    The second reason I don’t understand this point of view is that it explicitly leaps to a conclusion that the only thing quantum computers can do that is practical is factoring. While I could list off some recent algorithms that put chinks in this armor (http://arxiv.org/abs/0811.3171 is provocative and exciting, for example) I think the real question is what evidence do we have that this is true. Since I don’t think anyone will agree on what is meant by evidence here I would just note that the community of people who are actively pursuing new quantum algorithms is extremely small (as even a first order approximation one could count the number of researchers hired into US CS departments who do quantum computing theory and you’d find the answer of about one hire per year.) Give me more worker hours and I’d increase my agreement with Rivest!

    Finally, while it is easy to belittle the polynomial query complexity speedups in quantum computers, I’m not so certain that these types of results aren’t that important. Of course they won’t be important if quantum computing cannot be made competitive with classical computing in terms of basic gate times and parallelism…but to say something about whether this is, or is not, possible seems a question of technology not one for which one can pass such quick judgment.

    Anyway I enjoy lurking on your blog…though every time I see the picture in your header I wonder how anyone gets work done at UCSB 🙂

  3. I agree with Anonymous – this is a really silly comment (especially if it truly comes from Rivest). Furthermore, the real killer app for Quantum Computers is to simulate Quantum Mechanics; this is something we don’t think we can do classically. Furthermore, Quantum Computers give exponential speedups on a lot of different problems (including search!). Finally, Quantum Computers would be the ultimate validation of Quantum Mechanics.

  4. I was at the talk. It was clearly meant as a joke, and people laughed. However, as every (good) joke, it has an element of truth in it…

    Plus, one very practical motivation would be to build a quantum computer for breaking RSA in the precious timeframe after the computer is built, but before people (or banks!) stop using RSA :).

    –Yevgeniy

  5. Even if everyone dropped RSA immediately after the quantum computer was build I suppose it would still be interesting to break old RSA encryptions.

    @Ross Snider: Does quantum really give exponential speed up to search? I always thought of this as one of the disappointments og quantum (that it did not).

  6. “quantum computers have unbounded applications beyond cryptography”: Can anyone provide a brief summary/reminder of some applications of quantum computing, beyond cryptography, that someone really cares about?

  7. Hmm…I’m afraid people missed the point of my post. It wasn’t meant as a referendum on the usefulness of quantum computing (and for all I know, Rivest was joking or misquoted). The interesting bit to me was this: let’s assume that quantum computers will be expensive to build, cannot be built in secret, and are only useful for breaking factoring/dlog-based cryptosystems. Then it does seem to be the case that there is no point in building them. It’s just an application of backward induction, but I still found it interesting because it seems so counter-intuitive. (I think when we usually think of building quantum computers to break cryptosystems, we assume they can be built in secret by some gov’t organization. But if not, then the rationale for building them for that purpose appears to go away.)

  8. (Exponential speedup on search was a mistake)

  9. here is the link to Ron’s talk (I know that’s not the point of this post, but the talk was excellent to watch): http://techtv.mit.edu/videos/10590-killian-lecture—ronald-l-rivest

  10. OK, one important application of quantum computation is quantum simulation. Can anyone give the thumbnail summary of why quantum simulation is important? What are some example applications of quantum simulation?

    I feel a little bit like I’m overhearing the following conversation:

    Mathematician: Schessinger’s Theorem has many important applications.
    Engineer in the audience: Cool. Can you give me an example?
    Mathematician: Well, it can be used to prove Amberthroft’s Theorem.
    Engineer: ???

  11. What are some example applications of quantum simulation?

    Tons of problems in science (physics, chemistry, even biochemistry) come down to asking about the behavior of quantum systems. In simple cases we may get analytic solutions, but in general we will have to resort to simulation to figure out what is going on. This would be an awful lot easier if there were efficient algorithms for quantum simulation.

  12. Hello.

    Please see my paper regarding factoring and P vs. NP problem at:

    http://www.optimization-online.org/DB_HTML/2011/02/2920.html

    Thanks,

    Yuly


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: