Saying that it evokes "white supremecy" is kind of a pathetic move.
Not as pathetic as "We at IBM are concerned of".
IBM casts doubt on Google's claims of quantum supremacy
121–130 of 149 posts
Re: IBM casts doubt on Google's claims of quantum supremacy
#122Earlier quoted context omitted.
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.
No, the bound is not on the performance of the sorting algorithm, but rather on the minimum number of comparisons required
I would argue that "number of comparisons" is just the popular performance metric.
Of course in reality we care about execution time, and in order to go from "we need O(n * log(n)) comparisons" to "we need O(n * log(n)) time" you need additional assumptions, like "memory access takes O(1) time, and the speed of one comparison is independent of the total amount of data". But for any reasonable set of assumptions an algorithm that uses O(n * log(n)) comparisons takes at least O(n * log(n)) time (probably more since memory access isn't really O(1), it's just common to pretend that it is).
Re: IBM casts doubt on Google's claims of quantum supremacy
#123Following the quantum supremacy controversy is very frustrating. It gets constantly framed as a decisive step that changes everything, which is wrong. But then there's also an opposite and equally wrong reaction that any challenges to the claim prove that quantum computing doesn't work at all. The reality is that quantum computing technology has been improving at the same steady pace for decades, and quantum supremac…
Quantum supremacy is a big deal. It is a goddamn experimental evidence against Extended Church-Turing Thesis. If you never believed ECT (for example, all physicists seem to think ECT is obviously false) it may not matter to you, but it still is a serious claim. Yes, Google probably can achieve quantum supremacy by slapping a few more qubits. But a few more qubits were, in fact, not slapped yet. So quantum supremacy i…
How does quantum computation conflict with the ECT? I think Aaronson had talked about this but I don't remember his position on this.
Re: IBM casts doubt on Google's claims of quantum supremacy
#124There are three threads. The others are:
Google's post https://news.ycombinator.com/item?id=21332768
Scott Aaronson's post https://news.ycombinator.com/item?id=21335907
Re: IBM casts doubt on Google's claims of quantum supremacy
#125Earlier quoted context omitted.
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.
>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. You can have a faster classical algorithm if it's distributed across n threads for a size n array. For each index i in an array arr, spawn a thread that counts the number of values in arr that are less than arr[i] (an O(n) linear scan), call this x, then do ou…
This is an apples to orange comparison. Time complexities are with respect to some computational model. When not specified one typically assumes it's with respect to a deterministic turing machine or something a lot like it. Te model you are describing allows for unbounded parallel execution.
Re: IBM casts doubt on Google's claims of quantum supremacy
#126Earlier quoted context omitted.
Quantum supremacy is a big deal. It is a goddamn experimental evidence against Extended Church-Turing Thesis. If you never believed ECT (for example, all physicists seem to think ECT is obviously false) it may not matter to you, but it still is a serious claim. Yes, Google probably can achieve quantum supremacy by slapping a few more qubits. But a few more qubits were, in fact, not slapped yet. So quantum supremacy i…
How does quantum computation conflict with the ECT? I think Aaronson had talked about this but I don't remember his position on this.
The original Church Turing thesis concerns itself with computability and quantum computers do not violate it.
The Extended version goes on to say a probabilistic TM can efficiently simulate all realistic models of computation. Quantum computers very likely violate the efficiency claim and this supremacy result is strong evidence in support.
Re: IBM casts doubt on Google's claims of quantum supremacy
#127Judging entirely by my experience with IBM- put up or shut up. Every interaction I've had with IBM the last few years has been shit. It's to the point that all of my confidence in the entire organization is gone, regain my confidence. Put up or shut up IBM.
Re: IBM casts doubt on Google's claims of quantum supremacy
#128Earlier quoted context omitted.
Could you elaborate? You can search for the solution to any computational problem for which there is a binary function f(n) mapping candidates n to {0,1}, depending on whether it's a solution. Here, f is the "oracle", but it's only playing the role of representing the problem you're trying to solve, and I believe an f exists for all problems in NP. If your set of solutions has N candidates, this requires only O(sqrt(…
But is there actually a proof that these are improvements over all possible classical algorithms or are they just improvements over the best currently known classical algorithms?
That's what my last two sentences address.
Re: IBM casts doubt on Google's claims of quantum supremacy
#129Part of this controversy is reminiscent of the Higgs Boson "God particle" nonsense, where an unscientific catchphrase created by scientists got picked put by the media and a misinterpretation overshadowed the real scientific issue.
Re: IBM casts doubt on Google's claims of quantum supremacy
#130Following the quantum supremacy controversy is very frustrating. It gets constantly framed as a decisive step that changes everything, which is wrong. But then there's also an opposite and equally wrong reaction that any challenges to the claim prove that quantum computing doesn't work at all. The reality is that quantum computing technology has been improving at the same steady pace for decades, and quantum supremac…
> Just by adding a few more qubits
IBM's algorithm scales approximately linearly in the number of qubits. So, you'd need more than a few more qubits...