6 ms·

IMO the whole IBM blog is interesting, your quote isn't just a summary. Basically what IBM is claiming is that Google's circuit doesn't do anything useful real

by phh 7y ago

IMO the whole IBM blog is interesting, your quote isn't just a summary. Basically what IBM is claiming is that Google's circuit doesn't do anything useful really, it is just meant to be very complicated to do in traditional computing systems. And even in this idealized position, Google's quantum computer doesn't transform an unsolvable problem into a solvable one. According to IBM, "Quantum Supremacy" means accomplishing something useful to the society, that simply wouldn't be possible to do otherwise. Google's article doesn't show any sign of that, IBM claim.

mtgx 7y ago
All of that is true, but according to IBM's own definition of "quantum advantage" I think Google at least achieved that. All in all, it seems more of a battle of semantics, and the two companies talking past each other. It's kind of how everyone seems to interpret Moore's Law to mean "any progress in computational performance whatsoever" these days, as opposed to the original definition of "transistors doubling in the same space every 18-24 months," and then using that to "prove" that "Moore's Law is still alive." (it's not, and hasn't been for a long time). I think in the end what's important here is that it was proven that a quantum computer can do "something" (yes, even anything at all is a big milestone) significantly faster than a classical system. Because this is what matters in the end that quantum computers can do some tasks significantly faster than classical systems. They don't have to do only tasks that are "impossible" for classical systems to be useful. It's also why we use GPUs, FPGAs, and ASICs for some tasks, instead of just using CPUs for everything. I do agree that it was in Google's interest not to work so hard on optimizing the classical system for the simulation, to make its quantum computer look that much more impressive. But if the quantum computer is still faster, then it doesn't really matter.
- sanxiyn 7y ago
  No, if your standard is "faster", even D-Wave achieved that. Quantum supremacy is about exponential speedup, and in light of IBM's claim, Google's claim of quantum supremacy is very much in doubt.
IanCal 7y ago
> According to IBM, "Quantum Supremacy" means accomplishing something useful to the society, that simply wouldn't be possible to do otherwise. Google's article doesn't show any sign of that, IBM claim. I thought that the whole point was to show that what you'd done definitely wasn't just build a complex classical processor. The usefulness of the calculation is besides the point.
- lisptw102019 7y ago
  Both of you are slightly off. Quantum Supremacy is more about where quantum computers are clearly superior to non-quantum computers to solve a problem.
onetimemanytime 7y ago
Regardless of what they say, Quantum computer solved it in 200 seconds and IBM states that their super-computer solves it in 2.5 days (Google says 10,000 years.) Even if we take IBM's claim at face value, 200 seconds vs 2.5 DAYS is still a lot of improvement, semantics aside. Not to mention that quantum computers have just started
- sanxiyn 7y ago
  No, 2.5 days is irrelevant. This is about proving exponential speedup, but IBM is claiming linear scaling, so it is a serious challenge.
  - mda 7y ago
    What if it is linear but angle is so steep that you require all the sands in the world to achieve parity with a classical computer, does it still count?
    - sanxiyn 7y ago
      Of course. Quantum supremacy is a claim about computational complexity. 200 seconds vs 2.5 days is 1000x slowdown. In practical terms, x^10 is even worse than 1000x (linear), but if quantum computer could be simulated in x^10, that would definitely disprove quantum supremacy.
    - contravariant 7y ago
      Maybe but 1) that's hard to prove and 2) it's hard to achieve unless you're looking at some sub-problem where the quantum and classical algorithm actually do scale differently.
    - drcode 7y ago
      I think in that case you would probably be able to formulate the problem in a different way to show that the angle arises through an exponential process (or more) and that the problem isn't truly linear.
  - mmusson 7y ago
afthonos 7y ago
"Quantum Supremacy" is a technical term, not a colloquial one. It refers to showing that there exists a problem that a real, physical quantum computer can solve quickly that a classical computer cannot. Reading the IBM article, they are fully aware of what "quantum supremacy" means in a technical sense, and they are urging the media not to use that term, since it will be misunderstood by the public. Their claim that Google has failed to achieve supremacy rests solely on their claim that they can simulate the circuit far faster (and scale the simulation linearly) using better classical algorithms. That's a strong claim, and I'm interested in seeing what Google responds with. Disclosure: I work at Google, but hahaha, no, I'm not cool enough to work on this.
- sanxiyn 7y ago
  Thank you. I am not sure why people are talking about 2.5 days, since the key claim is "linearly scaling". If simulation is linearly scaling in this regime, the entire proof is indeed questionable.
  - mazesc 7y ago
    IBMs response seems strong regarding "linear scaling", but could they give a complexity-theoretic argument rather than an empirical one?
    - sanxiyn 7y ago
      I think IBM didn't elaborate because it is kind of obvious if you are into this, and if you are not, linearly scaling graph from 10 to 30 is more than good enough. But since we have niche audience here, let's elaborate. Quantum supremacy is O(n) claim. Then what is n? The answer is that there are two parameters, not one. In Google paper, n is number of qubits and m is circuit depth. n is well known to be difficult to increase. m is not easy either, because if your qubit isn't stable enough, you can't run deep circuit. What Google did is to run n=53 and m=20. Then, why do you need n=53 and m=20? After all, you could see whether it's exponential by, say, trying n and m from 10 to 15, it doesn't need to take days and years. The answer is that there is time-space tradeoff available and if your n is constant, exp(n) space (but still constant space, since n is constant) poly(m) time algorithm is available, and if your m is constant, exp(m) space (but still constant space, since m is constant) poly(n) time algorithm is available. So if you want to show exponential speedup, you need to be able to exclude these algorithms by increasing n or m enough such that exp(n) or exp(m) space is not realizable. Google chose n=53 such that exp(n) is not realizable, and ran scaling experiment on m. This is what they mean whey they say in the paper "Up to 43 qubits, we use a Schrödinger algorithm, which simulates the evolution of the full quantum state... Above this size, there is not enough random access memory (RAM) to store the quantum state". Now what IBM is saying is becoming clear. There is not enough RAM, but there is enough disk, so exp(n) where n=53 is realizable, and simulation runs linear in m. It's not a new algorithm, it's exactly the same algorithm Google ran up to n=43. So 43 qubits clearly can't demonstrate quantum supremacy. For the same reason, 53 qubits can't either.
clSTophEjUdRanu 7y ago
It's not about doing useful work it's about finding an actual workload that cannot be solved faster classically.
hos234 7y ago
Will just point out it's 25 years since Deep Blue and 10 since Watson/Jeopardy. And boy were lot of claims made back then. Good ol'IBM has yet to deliver anything.
ridewinter 7y ago
One way of viewing Google's achievement is as a result that cannot be explained without invoking parallel universes. That's pretty amazing. I posted an article explaining more: https://news.ycombinator.com/item?id=21337739 https://news.ycombinator.com/item?id=21337739

by phh 7y ago

mtgx 7y ago

All of that is true, but according to IBM's own definition of "quantum advantage" I think Google at least achieved that. All in all, it seems more of a battle of semantics, and the two companies talking past each other. It's kind of how everyone seems to interpret Moore's Law to mean "any progress in computational performance whatsoever" these days, as opposed to the original definition of "transistors doubling in the same space every 18-24 months," and then using that to "prove" that "Moore's Law is still alive." (it's not, and hasn't been for a long time). I think in the end what's important here is that it was proven that a quantum computer can do "something" (yes, even anything at all is a big milestone) significantly faster than a classical system. Because this is what matters in the end that quantum computers can do some tasks significantly faster than classical systems. They don't have to do only tasks that are "impossible" for classical systems to be useful. It's also why we use GPUs, FPGAs, and ASICs for some tasks, instead of just using CPUs for everything. I do agree that it was in Google's interest not to work so hard on optimizing the classical system for the simulation, to make its quantum computer look that much more impressive. But if the quantum computer is still faster, then it doesn't really matter.

sanxiyn 7y ago
No, if your standard is "faster", even D-Wave achieved that. Quantum supremacy is about exponential speedup, and in light of IBM's claim, Google's claim of quantum supremacy is very much in doubt.

IanCal 7y ago

> According to IBM, "Quantum Supremacy" means accomplishing something useful to the society, that simply wouldn't be possible to do otherwise. Google's article doesn't show any sign of that, IBM claim. I thought that the whole point was to show that what you'd done definitely wasn't just build a complex classical processor. The usefulness of the calculation is besides the point.

lisptw102019 7y ago
Both of you are slightly off. Quantum Supremacy is more about where quantum computers are clearly superior to non-quantum computers to solve a problem.

onetimemanytime 7y ago

Regardless of what they say, Quantum computer solved it in 200 seconds and IBM states that their super-computer solves it in 2.5 days (Google says 10,000 years.) Even if we take IBM's claim at face value, 200 seconds vs 2.5 DAYS is still a lot of improvement, semantics aside. Not to mention that quantum computers have just started

sanxiyn 7y ago
No, 2.5 days is irrelevant. This is about proving exponential speedup, but IBM is claiming linear scaling, so it is a serious challenge.
- mda 7y ago
  What if it is linear but angle is so steep that you require all the sands in the world to achieve parity with a classical computer, does it still count?
  - sanxiyn 7y ago
    Of course. Quantum supremacy is a claim about computational complexity. 200 seconds vs 2.5 days is 1000x slowdown. In practical terms, x^10 is even worse than 1000x (linear), but if quantum computer could be simulated in x^10, that would definitely disprove quantum supremacy.
  - contravariant 7y ago
    Maybe but 1) that's hard to prove and 2) it's hard to achieve unless you're looking at some sub-problem where the quantum and classical algorithm actually do scale differently.
  - drcode 7y ago
    I think in that case you would probably be able to formulate the problem in a different way to show that the angle arises through an exponential process (or more) and that the problem isn't truly linear.
- mmusson 7y ago

afthonos 7y ago

"Quantum Supremacy" is a technical term, not a colloquial one. It refers to showing that there exists a problem that a real, physical quantum computer can solve quickly that a classical computer cannot. Reading the IBM article, they are fully aware of what "quantum supremacy" means in a technical sense, and they are urging the media not to use that term, since it will be misunderstood by the public. Their claim that Google has failed to achieve supremacy rests solely on their claim that they can simulate the circuit far faster (and scale the simulation linearly) using better classical algorithms. That's a strong claim, and I'm interested in seeing what Google responds with. Disclosure: I work at Google, but hahaha, no, I'm not cool enough to work on this.

sanxiyn 7y ago
Thank you. I am not sure why people are talking about 2.5 days, since the key claim is "linearly scaling". If simulation is linearly scaling in this regime, the entire proof is indeed questionable.
- mazesc 7y ago
  IBMs response seems strong regarding "linear scaling", but could they give a complexity-theoretic argument rather than an empirical one?
  - sanxiyn 7y ago
    I think IBM didn't elaborate because it is kind of obvious if you are into this, and if you are not, linearly scaling graph from 10 to 30 is more than good enough. But since we have niche audience here, let's elaborate. Quantum supremacy is O(n) claim. Then what is n? The answer is that there are two parameters, not one. In Google paper, n is number of qubits and m is circuit depth. n is well known to be difficult to increase. m is not easy either, because if your qubit isn't stable enough, you can't run deep circuit. What Google did is to run n=53 and m=20. Then, why do you need n=53 and m=20? After all, you could see whether it's exponential by, say, trying n and m from 10 to 15, it doesn't need to take days and years. The answer is that there is time-space tradeoff available and if your n is constant, exp(n) space (but still constant space, since n is constant) poly(m) time algorithm is available, and if your m is constant, exp(m) space (but still constant space, since m is constant) poly(n) time algorithm is available. So if you want to show exponential speedup, you need to be able to exclude these algorithms by increasing n or m enough such that exp(n) or exp(m) space is not realizable. Google chose n=53 such that exp(n) is not realizable, and ran scaling experiment on m. This is what they mean whey they say in the paper "Up to 43 qubits, we use a Schrödinger algorithm, which simulates the evolution of the full quantum state... Above this size, there is not enough random access memory (RAM) to store the quantum state". Now what IBM is saying is becoming clear. There is not enough RAM, but there is enough disk, so exp(n) where n=53 is realizable, and simulation runs linear in m. It's not a new algorithm, it's exactly the same algorithm Google ran up to n=43. So 43 qubits clearly can't demonstrate quantum supremacy. For the same reason, 53 qubits can't either.

clSTophEjUdRanu 7y ago

It's not about doing useful work it's about finding an actual workload that cannot be solved faster classically.

hos234 7y ago

Will just point out it's 25 years since Deep Blue and 10 since Watson/Jeopardy. And boy were lot of claims made back then. Good ol'IBM has yet to deliver anything.

ridewinter 7y ago

One way of viewing Google's achievement is as a result that cannot be explained without invoking parallel universes. That's pretty amazing. I posted an article explaining more: https://news.ycombinator.com/item?id=21337739 https://news.ycombinator.com/item?id=21337739