[Computational Complexity] Confessions of a Quantum Computing Skeptic
Will we ever have useful quantum computers? Despite the "breakthroughs" we seem to have nearly every month, we are a long way off from controlling even a handful of quantum bits certainly not the tens of thousands of qbits one needs for meaningful computation.
But I'm not a physicist or an engineer and suppose we can overcome these obstacles and actually build a working machine. Then I can imagine the following conversation in 2025:
Quantum People: We now have a working quantum computer.
Public: Yes after 30 years and 50 billion dollars in total funding. What can it do?
Q: It can simulate quantum systems.
P: I'm happy for you. What can it do for the rest of us?
Q: It can factor numbers quickly.
P: Yes, I know. We've had to change all of our security protocols because of your machine. Does factoring have any purpose other than to break codes?
Q: Not really. But we can use Grover's algorithm for general search problems.
P: That sounds great! So we can really solve traveling salesperson and scheduling problems much faster than before?
Q: Not exactly. The quadratic speed-up we get from Grover's algorithm isn't enough the offset the slow-down by using a quantum computer combined with error correction. But we can solve Pell's equation, approximate the Jones polynomial and a few other things very quickly.
P: Are those algorithms particularly useful?
P: They why did you build a quantum computer?
Q: Because we could.
Posted by Lance to Computational Complexity at 8/08/2006 11:26:00 AM