4 ms·

The title of the article "Performance of quantum computer no better than ordinary PC" is just flat out wrong. The real issue that physicists are concerned abou

The title of the article "Performance of quantum computer no better than ordinary PC" is just flat out wrong. The real issue that physicists are concerned about is whether the D-wave machine is a quantum computer or not. The issue is not whether quantum computers are "better" than classical ones. Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases. This has been mathematically proven. (EDIT: No it hasn't apparently. See Michael Nielsen's response below.)

michael_nielsen 12y ago
Your first paragraph is quite right. But the second paragraph is wrong: for (non-oracle) problems quantum computers are merely suspected to be faster in principle than conventional classical computers. It's never been proven.
- Xcelerate 12y ago
  I guess I'm confused then. I thought that quantum algorithms had been proven to be faster than the best known classical algorithms (for instance, Shor's factorization), assuming the correctness and completeness of the postulates of QM. In other words, the order of the algorithm is derivable from the postulates. Is that not the case? I think there's a few people (t'Hooft if I remember correctly?) that believe a quantum computer will never be able to experimentally demonstrate this speed-up because some aspect of quantum mechanics is incomplete/incorrect. Edit: Here's the thread I was thinking of where t'Hooft and Shor discuss this http://physics.stackexchange.com/questions/34217/why-do-people-categorically-dismiss-some-simple-quantum-models http://physics.stackexchange.com/questions/34217/why-do-peop...
  - michael_nielsen 12y ago
    Shor's algorithm is exponentially faster than the best existing classical algorithm for factoring. But that doesn't mean there's not an exponentially faster classical algorithm which would be comparable in speed to Shor's algorithm. Some noted experts believe this is possible, and even likely. Richard Lipton believes it, and claims that Peter Sarnak does too: http://rjlipton.wordpress.com/2013/04/27/sex-lies-and-quantum-computers/ http://rjlipton.wordpress.com/2013/04/27/sex-lies-and-quantu... Yes, 't Hooft and others, including Leonid Levin and Oded Goldreich, believe that quantum computers won't function because of quantum mechanics breaking down. See, e.g.: http://www.wisdom.weizmann.ac.il/~oded/on-qc.html http://www.wisdom.weizmann.ac.il/~oded/on-qc.html http://www.cs.bu.edu/fac/lnd/expo/qc.htm http://www.cs.bu.edu/fac/lnd/expo/qc.htm
    - axilmar 12y ago
      Aren't algorithms like Shor's essentially faster than others in their respected categories due to parallelization? I.e. isn't quantum superposition just a form of parallelization? if the quantum step in Shor's algorithm is replaced with a classical step executed in parallel in many cpus, then the speed up would be of the same order of magnitude as when using a quantum step.
      - keeperofdakeys 12y ago
        Not really, if that was the case, quantum computers really would be faster than classical computers. A qubit is basically a normal bit, with probability a that it's in the 0 state, and b that it's in the 1 state, with a^2 + b^2 = 1. If you do some clever maths, you can get these probabilities to cancel out, and give you something that will collapse to the proper state when read. http://en.wikipedia.org/wiki/Shor's_algorithm#Finding_the_period http://en.wikipedia.org/wiki/Shor's_algorithm#Finding_the_pe... Shor's algorithm is still very theoretical though, we need to actually build a quantum computer to run it first.
- tzs 12y ago
  What about searching an unsorted database? Quantum can do it in O(N^0.5). Hasn't it been proven that classical computers need O(N)?
  - michael_nielsen 12y ago
    That's right. The search result, however, assumes the only way of accessing the database is through a black box oracle. That's why I wrote "non-oracle" in my previous comment. It's called an oracle because the internals of the black box are assumed to be unknown. That assumption is necessary in order to prove that classical computers need ~ N operations. If you know something about the internals of the oracle, then it may well be possible to exploit what you know to search faster. The quantum search algorithm is very interesting. However, most people in the field would, I think, agree that a non-oracle separation between quantum and classical would be vastly more interesting. Oracle results feel a little too close to cheating. There is, incidentally, a nice paper showing that for computing total Boolean functions the quantum oracle model can be no more than polynomially faster than a classical model. This means there can be no exponential speedup for such functions, which is a real pity. http://arxiv.org/abs/quant-ph/9802049 http://arxiv.org/abs/quant-ph/9802049
colanderman 12y ago
Calm down dude. "Quantum computer" in the title refers specifically to the D-wave. Headlines leave out specifiers all the time. ex.: "Man bites dog" doesn't mean "all of mankind bit a dog", it means "this man bit a dog".
- EpicEng 12y ago
  Except no one, ever, would take "dog bites man" as "one dog bit all of mankind". The title is misleading and, at least one person (myself), took it to mean "quantum computing in general". P.S. why did you go with "man bites dog"?
  - graedus 12y ago
    It's a saying. http://en.wikipedia.org/wiki/Man_bites_dog_(journalism) http://en.wikipedia.org/wiki/Man_bites_dog_(journalism)
    - EpicEng 12y ago
      Ahhh, I'd never heard that before.
  - baddox 12y ago
    I think you misread "quantum computer" as "quantum computers." The headline is very clearly talking about a single specific computer that is marketed as a "quantum computer."
    - EpicEng 12y ago
      Obviously it's not "very clear" as I was not the only one who took at as a more general statement. Just read through this thread.
deleted 12y ago
[deleted]
baddox 12y ago
It's just a slight grammatical ambiguity in the title, worsened by the "headline grammar" and the fact that it's a newspaper with a general audience. The headline is intended to be interpreted as "the performance of a particular computer that is marketed as a quantum computer is no better than the performance of an ordinary PC." But it's pretty easy to quickly read the headline and interpret it as "the performance of ideal quantum computers is no better than the performance of ordinary PCs." > Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases. I'm not sure about this part either. Some smart CS guys apparently think that quantum computing isn't even possible. Leonid Levin (yes, of the Cook-Levin theorem seems to be one of them: http://www.cs.bu.edu/fac/lnd/expo/qc.htm http://www.cs.bu.edu/fac/lnd/expo/qc.htm.
throwwit 12y ago
For a performance reference similar to Moore's law, check out the quantum version (Rose's law): https://2.bp.blogspot.com/-AZFZhBUmwds/UHT2yF39AHI/AAAAAAAAIYE/3UVDDiN5VpI/s640/Roses_Law.jpg https://2.bp.blogspot.com/-AZFZhBUmwds/UHT2yF39AHI/AAAAAAAAI...

michael_nielsen 12y ago

Your first paragraph is quite right. But the second paragraph is wrong: for (non-oracle) problems quantum computers are merely suspected to be faster in principle than conventional classical computers. It's never been proven.

Xcelerate 12y ago
I guess I'm confused then. I thought that quantum algorithms had been proven to be faster than the best known classical algorithms (for instance, Shor's factorization), assuming the correctness and completeness of the postulates of QM. In other words, the order of the algorithm is derivable from the postulates. Is that not the case? I think there's a few people (t'Hooft if I remember correctly?) that believe a quantum computer will never be able to experimentally demonstrate this speed-up because some aspect of quantum mechanics is incomplete/incorrect. Edit: Here's the thread I was thinking of where t'Hooft and Shor discuss this http://physics.stackexchange.com/questions/34217/why-do-people-categorically-dismiss-some-simple-quantum-models http://physics.stackexchange.com/questions/34217/why-do-peop...
- michael_nielsen 12y ago
  Shor's algorithm is exponentially faster than the best existing classical algorithm for factoring. But that doesn't mean there's not an exponentially faster classical algorithm which would be comparable in speed to Shor's algorithm. Some noted experts believe this is possible, and even likely. Richard Lipton believes it, and claims that Peter Sarnak does too: http://rjlipton.wordpress.com/2013/04/27/sex-lies-and-quantum-computers/ http://rjlipton.wordpress.com/2013/04/27/sex-lies-and-quantu... Yes, 't Hooft and others, including Leonid Levin and Oded Goldreich, believe that quantum computers won't function because of quantum mechanics breaking down. See, e.g.: http://www.wisdom.weizmann.ac.il/~oded/on-qc.html http://www.wisdom.weizmann.ac.il/~oded/on-qc.html http://www.cs.bu.edu/fac/lnd/expo/qc.htm http://www.cs.bu.edu/fac/lnd/expo/qc.htm
  - axilmar 12y ago
    Aren't algorithms like Shor's essentially faster than others in their respected categories due to parallelization? I.e. isn't quantum superposition just a form of parallelization? if the quantum step in Shor's algorithm is replaced with a classical step executed in parallel in many cpus, then the speed up would be of the same order of magnitude as when using a quantum step.
    - keeperofdakeys 12y ago
      Not really, if that was the case, quantum computers really would be faster than classical computers. A qubit is basically a normal bit, with probability a that it's in the 0 state, and b that it's in the 1 state, with a^2 + b^2 = 1. If you do some clever maths, you can get these probabilities to cancel out, and give you something that will collapse to the proper state when read. http://en.wikipedia.org/wiki/Shor's_algorithm#Finding_the_period http://en.wikipedia.org/wiki/Shor's_algorithm#Finding_the_pe... Shor's algorithm is still very theoretical though, we need to actually build a quantum computer to run it first.
tzs 12y ago
What about searching an unsorted database? Quantum can do it in O(N^0.5). Hasn't it been proven that classical computers need O(N)?
- michael_nielsen 12y ago
  That's right. The search result, however, assumes the only way of accessing the database is through a black box oracle. That's why I wrote "non-oracle" in my previous comment. It's called an oracle because the internals of the black box are assumed to be unknown. That assumption is necessary in order to prove that classical computers need ~ N operations. If you know something about the internals of the oracle, then it may well be possible to exploit what you know to search faster. The quantum search algorithm is very interesting. However, most people in the field would, I think, agree that a non-oracle separation between quantum and classical would be vastly more interesting. Oracle results feel a little too close to cheating. There is, incidentally, a nice paper showing that for computing total Boolean functions the quantum oracle model can be no more than polynomially faster than a classical model. This means there can be no exponential speedup for such functions, which is a real pity. http://arxiv.org/abs/quant-ph/9802049 http://arxiv.org/abs/quant-ph/9802049

colanderman 12y ago

Calm down dude. "Quantum computer" in the title refers specifically to the D-wave. Headlines leave out specifiers all the time. ex.: "Man bites dog" doesn't mean "all of mankind bit a dog", it means "this man bit a dog".

EpicEng 12y ago
Except no one, ever, would take "dog bites man" as "one dog bit all of mankind". The title is misleading and, at least one person (myself), took it to mean "quantum computing in general". P.S. why did you go with "man bites dog"?
- graedus 12y ago
  It's a saying. http://en.wikipedia.org/wiki/Man_bites_dog_(journalism) http://en.wikipedia.org/wiki/Man_bites_dog_(journalism)
  - EpicEng 12y ago
    Ahhh, I'd never heard that before.
- baddox 12y ago
  I think you misread "quantum computer" as "quantum computers." The headline is very clearly talking about a single specific computer that is marketed as a "quantum computer."
  - EpicEng 12y ago
    Obviously it's not "very clear" as I was not the only one who took at as a more general statement. Just read through this thread.

deleted 12y ago

[deleted]

baddox 12y ago

It's just a slight grammatical ambiguity in the title, worsened by the "headline grammar" and the fact that it's a newspaper with a general audience. The headline is intended to be interpreted as "the performance of a particular computer that is marketed as a quantum computer is no better than the performance of an ordinary PC." But it's pretty easy to quickly read the headline and interpret it as "the performance of ideal quantum computers is no better than the performance of ordinary PCs." > Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases. I'm not sure about this part either. Some smart CS guys apparently think that quantum computing isn't even possible. Leonid Levin (yes, of the Cook-Levin theorem seems to be one of them: http://www.cs.bu.edu/fac/lnd/expo/qc.htm http://www.cs.bu.edu/fac/lnd/expo/qc.htm.

throwwit 12y ago

For a performance reference similar to Moore's law, check out the quantum version (Rose's law): https://2.bp.blogspot.com/-AZFZhBUmwds/UHT2yF39AHI/AAAAAAAAIYE/3UVDDiN5VpI/s640/Roses_Law.jpg https://2.bp.blogspot.com/-AZFZhBUmwds/UHT2yF39AHI/AAAAAAAAI...