Is 200 seconds not faster than 2.5 days?? I don't see the argument here
It is difference between with this quantum chip we can brake encryption that would take 100000 years in 30 minutes or it would take us 50 years.
IBM casts doubt on Google's claims of quantum supremacy
51–60 of 149 posts
Re: IBM casts doubt on Google's claims of quantum supremacy
#52Earlier quoted context omitted.
There are many problems where the best known quantum algorithm is asymptotically better than the best known classical algorithm but, as far as I've heard, nobody has ever found a case where the best quantum algorithm can be proved to be better than the best classical algorithm. So there's always going to be a danger of this happening no matter what problem you attack.
Isn't quantum factoring proven to be exponentially faster than the best known classical one? The only question is we don't know if there is a better classical factoring algorithm. Wikipedia: > On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which wor…
As far as I'm aware there actually is no proof that there is no polynomial time factoring algorithm. Complexity theory contains a lot of cargo cult belief with little solid proofs unfortunately. One reason is of course that it is a very hard field of mathematics. See https://www.math.ias.edu/avi/book for a recent survey.
Re: IBM casts doubt on Google's claims of quantum supremacy
#53Quote 1: "The Google group reiterates its claim that, in 200 seconds...."
Quote 2: " ...by tweaking the way Summit approaches the task, it can do it far faster: in 2.5 days."
Well, it's still 200 seconds vs 2.5 days, so I'd say the claim kinda stands. I know I would definitely buy the computer with 200 seconds vs the one with 2.5 days.
Re: IBM casts doubt on Google's claims of quantum supremacy
#54Is 200 seconds not faster than 2.5 days?? I don't see the argument here
The quantum circuit based simulation actually has much worse accuracy. A classical computer can simulate the class of circuits they are proposing with linear increasing runtime (as opposed to exponential as Google claims) and _much_ higher accuracy according to IBM.
Re: IBM casts doubt on Google's claims of quantum supremacy
#55Earlier quoted context omitted.
There are many problems where the best known quantum algorithm is asymptotically better than the best known classical algorithm but, as far as I've heard, nobody has ever found a case where the best quantum algorithm can be proved to be better than the best classical algorithm. So there's always going to be a danger of this happening no matter what problem you attack.
Isn't quantum factoring proven to be exponentially faster than the best known classical one? The only question is we don't know if there is a better classical factoring algorithm. Wikipedia: > On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which wor…
Yes, for factoring integers the best known quantum algorithm is better than the best known classical algorithm. The catch is that we don't know if a better classical algorithm exists but just wasn't discovered yet.
Compare this for example to sorting. We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist.
Re: IBM casts doubt on Google's claims of quantum supremacy
#56Earlier quoted context omitted.
2.5 _days_, not years. A still fuzzy and arbitrary but imo somewhat elegant cutoff would let feasibility be set by the market and technological development, in the sense of something not being worth throwing compute at _now_ because the timescale of work is slow enough that future classical efficiencies will progress (much) quicker.
For market forces to be meaningful, the calculation would need to provide value to someone. At the moment the desired output is simply "a distribution which is hard to simulate classically," so assessment in terms of market value would be very premature.
But that goes for any raw benchmarking, it’s busywork by design.
Re: IBM casts doubt on Google's claims of quantum supremacy
#57Is 200 seconds not faster than 2.5 days?? I don't see the argument here
Supremacy does not mean simply faster. That is already proven. It means impossible to do on a classical computer.
I'm sure you mean infeasible. "Impossible" goes back to a problem's decidability. If a problem is undecidable, there's no way you're going to find its solution by switching computational models; classical computers can do anything a quantum computer can do, just "slower".
Re: IBM casts doubt on Google's claims of quantum supremacy
#58Earlier quoted context omitted.
Isn't quantum factoring proven to be exponentially faster than the best known classical one? The only question is we don't know if there is a better classical factoring algorithm. Wikipedia: > On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which wor…
As far as I'm aware there actually is no proof that there is no polynomial time factoring algorithm. Complexity theory contains a lot of cargo cult belief with little solid proofs unfortunately. One reason is of course that it is a very hard field of mathematics. See https://www.math.ias.edu/avi/book for a recent survey.
But parent was stating something very different, that today quantum factoring is only asymptotically better that classical one, when that is clearly not the case.
Re: IBM casts doubt on Google's claims of quantum supremacy
#59Quote 1: "The Google group reiterates its claim that, in 200 seconds...." Quote 2: " ...by tweaking the way Summit approaches the task, it can do it far faster: in 2.5 days." Well, it's still 200 seconds vs 2.5 days, so I'd say the claim kinda stands. I know I would definitely buy the computer with 200 seconds vs the one with 2.5 days.
Quantum supremacy is more about quantum computers being able to do something that classical computers could never do (1). I think that's the heart of the controversy. I'm quite sure Quantum has already proved faster for certain use cases already (2)
1. https://twitter.com/NatureNews/status/1186969282632134656?re... 2. https://arxiv.org/abs/1904.05803
Re: IBM casts doubt on Google's claims of quantum supremacy
#60Quote 1: "The Google group reiterates its claim that, in 200 seconds...." Quote 2: " ...by tweaking the way Summit approaches the task, it can do it far faster: in 2.5 days." Well, it's still 200 seconds vs 2.5 days, so I'd say the claim kinda stands. I know I would definitely buy the computer with 200 seconds vs the one with 2.5 days.
Nobody is denying that the quantum system performs the task faster. The question is whether it performs a task that can't feasibly be performed by a classical system. That is what the researchers are specifically referring to when they say "quantum supremacy."
2.5 days is feasible. 10,000 years is not feasible.