Quantum supremacy at Google

[leblon]

Just went to the Simons symposium in New York. I would not say the talks were terribly interesting, but I did hear a couple of amusing things. Scott Aaronson, in particular, gave a talk. Among other things he explained what the hype about Google supposedly achieving "quantum supremacy" is all about. It turns out a detailed paper will appear next week, in the journal "Nature". Scott apparently has been working closely with the Google quantum computing group and gave us a preview.

"Quantum supremacy" is when a quantum computer can solve problems which a classical computer is not able to solve within a reasonable time. Now, this of course assumes that we know the best possible classical algorithm for this sort of problems, or that we can put a lower bound on the time that a classical algorithm would take. This is almost never the case. What Google was trying to do is to beat the best known classical algorithm for a particular class of problems.There are some theoretical reasons to believe that no classical algorithm can do much better than the currently known one, but no proof of this. 

What is the problem that they are solving? I did not understand. You can try reading this paper by Aaronson and Chen which explains the relevant class of problems (it is called SampBPP). Something about sampling a specified probability distribution. 

Anyway, the Google team says that their quantum computer can solve within reasonable time some problem from this class which a classical computer would take 10,000 years to solve. The quantum computer has only 53 qubits (actually, 54, but one qubit was not working).

I cannot say I am impressed, but  maybe this is because I did not understand what problem they were solving. 

Comments

[alexanderr]

this is not very intuitive. I mean, log(2^53)/log(10)=15.9 so a 10 petaflop class classical machine should be doing this kind of thing roughly every second. 10,000 years is like 3*10^11 seconds. where these extra 11 orders of magnitude are coming from? and 10 petaflop is not the biggest machine out there, number one is like 200 petaflops

[type2b.livejournal.com]

There is a blog post in Aaronson's blog that you've perhaps seen: https://www.scottaaronson.com/blog/?p=4317
To me it seemed like a good explanation of the problem and why one should care.

[leblon]

OK, thanks, I have not seen it.