4 ms·

Is there any evidence it will ever be better than a classical computer?

FeepingCreature 8y ago
For the record, the concept is called Quantum Supremacy [1]. So far, there is no demonstration of quantum supremacy, but it seems like it may just be a matter of time. [1] https://en.wikipedia.org/wiki/Quantum_supremacy https://en.wikipedia.org/wiki/Quantum_supremacy
- deleted 8y ago
  [deleted]
- stochastic_monk 8y ago
  It’s related, but quantum supremacy is about asymptotic speedups rather than actual speed differences. Additionally, it’s worth keeping in mind that D-Wave machines aren’t true quantum computers in the sense that they can’t perform Grover’s or Shor’s algorithms.
  - garmaine 8y ago
    It’s not clear what “true quantum computer” means. There are many different types of quantum computers, and quantum annealing, what D-wave does, is one. It’s just the least interesting of the bunch...
- throwawaymath 8y ago
  Quantum supremacy is not merely about quantum computers performing tasks better than classical computers. It's about quantum computers achieving a superpolynomial speedup over classical computers, such that classical computers can't feasibly perform the task in a reasonable amount of time for all inputs. That's an important distinction because it's significantly more difficult to achieve a fundamental asymptotic improvement instead of an iterative speedup for the same factor. If a quantum computer completes a task with complexity O(2n) that a classical computer requires O(10n) to complete, you don't have quantum supremacy. If your quantum computer can accomplish a task in O(2n) that your classical computer needs O(2^n) to perform, you've got supremacy. Given that nuance, I wouldn't say it may be a matter of time before we demonstrate quantum supremacy. There is still an undercurrent of skepticism in the research community.
krastanov 8y ago
There is no evidence that quantum annealing (what D-Wave does) is any better than classical computers. There is a lot of evidence that quantum computers (the gate model) or, equivalently, quantum adiabatic computing is better than classical computing. All of it is based on a family of conjectures about the complexity classes P, BQP, and NP. Scott Aaronson's blog is one of my go-to suggestions for rigorous introduction to the topic.

For the record, the concept is called Quantum Supremacy [1]. So far, there is no demonstration of quantum supremacy, but it seems like it may just be a matter of time. [1] https://en.wikipedia.org/wiki/Quantum_supremacy https://en.wikipedia.org/wiki/Quantum_supremacy

deleted 8y ago
[deleted]
stochastic_monk 8y ago
It’s related, but quantum supremacy is about asymptotic speedups rather than actual speed differences. Additionally, it’s worth keeping in mind that D-Wave machines aren’t true quantum computers in the sense that they can’t perform Grover’s or Shor’s algorithms.
- garmaine 8y ago
  It’s not clear what “true quantum computer” means. There are many different types of quantum computers, and quantum annealing, what D-wave does, is one. It’s just the least interesting of the bunch...
throwawaymath 8y ago
Quantum supremacy is not merely about quantum computers performing tasks better than classical computers. It's about quantum computers achieving a superpolynomial speedup over classical computers, such that classical computers can't feasibly perform the task in a reasonable amount of time for all inputs. That's an important distinction because it's significantly more difficult to achieve a fundamental asymptotic improvement instead of an iterative speedup for the same factor. If a quantum computer completes a task with complexity O(2n) that a classical computer requires O(10n) to complete, you don't have quantum supremacy. If your quantum computer can accomplish a task in O(2n) that your classical computer needs O(2^n) to perform, you've got supremacy. Given that nuance, I wouldn't say it may be a matter of time before we demonstrate quantum supremacy. There is still an undercurrent of skepticism in the research community.

krastanov 8y ago

There is no evidence that quantum annealing (what D-Wave does) is any better than classical computers. There is a lot of evidence that quantum computers (the gate model) or, equivalently, quantum adiabatic computing is better than classical computing. All of it is based on a family of conjectures about the complexity classes P, BQP, and NP. Scott Aaronson's blog is one of my go-to suggestions for rigorous introduction to the topic.