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.
Tuesday, August 08, 2006
Confessions of a Quantum Computing Skeptic