Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Confessions of a Quantum Computing Skeptic

Expand Messages
  • Lance
    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
    Message 1 of 1 , Aug 8, 2006
    • 0 Attachment
      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?
      Q: No.
      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

    Your message has been successfully submitted and would be delivered to recipients shortly.