Quantum supremacy at Google
Oct. 18th, 2019 07:48 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
leblonJust 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.
"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.
