How do researchers know / prove they've achieved quantum supremacy?

Question

I'm currently reading the book Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything by Michio Kaku, and I came upon the following sentence:

Soon after Google made its claim of achieving quantum supremacy, the Chinese announced that they broke an even larger barrier, performing a calculation in 200 seconds that would take a digital computer half a billion years. (my emphasis)

How would it be possible to prove that something of that scale is correct or valid?

Other claims of quantum supremacy have been on the order of a classical computer taking 1,000 years and even that seems difficult to prove.

What evidence do researchers provide that Quantum Advantage has occurred?

I'm just trying to understand this more clearly.

Update: Also mentioned in Wikipedia article: Quantum Supremacy.

Although in this it says the classical computer would take 2.5 billion years.

"In December 2020, a group based in the University of Science and Technology of China (USTC) led by Jian-Wei Pan reached quantum supremacy by implementing gaussian boson sampling on 76 photons with their photonic quantum computer Jiuzhang. The paper states that to generate the number of samples the quantum computer generates in 200 seconds, a classical supercomputer would require 2.5 billion years of computation."

Answer 1

I'm currently reading the book Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything by Michio Kaku

Oh, I'm sorry to hear that. That book is completely misinformed about quantum computing. You have my condolences for having bought it.

Soon after Google made its claim of achieving quantum supremacy, the Chinese announced that they broke an even larger barrier, performing a calculation in 200 seconds that would take a digital computer half a billion years. (my emphasis)

How would it be possible to prove that something of that scale is correct or valid?

You extrapolate. You show that, for the cases that you can solve, the cost of solving the problem scales in a particular way. For example, fit the solve time for cases that you can solve to an exponential and see that it scales exponentially while also having good underlying reasons for why it would scale exponentially. Then extrapolate that exponential fit out to the problem sizes that you can't solve.

The main issue is accounting for later better simulation methods. In cryptography there's a saying: "attacks only get better". What takes a million years using today's attacks might only take hours using next year's attacks, and it's essentially impossible to predict what kinds of attacks dedicated researchers will come up with. And you can't know how those attacks will scale; they don't exist yet! One thing that does seem to hold true is that it's better to think of difficulty in terms of factors of 2, rather than the raw numbers, because attacks tend to compound multiplicatively. A million years sounds like a lot... but you can also describe it as only 30 factors of 2 of security away from a day; not that many.

In fact, over the past 3 years, the classical attacks on this problem have improved and they have eaten those factors of 2. The 2019 experiment can now be simulated without too much difficulty. This year there was a much larger quantum experiment that's again intractable to simulate using known methods. So now we wait and see if the attacks continue to improve. Eventually the quantum computers should win, unless BQP=P, but at the moment the race is still on.

Answer 2

First of all, that book is basically a really bad book.

Hence, waste no more time and read something else. (EDIT: as pedagogical introduction to quantum mechanics, I strongly suggest to read Helgoland, by Carlo Rovelli)

Supremacy and advantage refer to different concepts, despite the fact that sometimes people use them interchangeably.

Supremacy: given any problem sample proved to be intractable in the classical framework; if researchers manage to solve it, with quantum computation, supremacy is achieved. To claim quantum supremacy the subject sample can either be of practical interest or just a proof-of-concept.

Advantage: researchers could fairly claim a quantum advantage once they find a quantum algorithm for a problem of practical interest, solving it (experimentally) much faster than any classical approach.

To know more details, you will find plenty of answers (1,2) within this community.

In case in the future these two definitions would converge into one, it would be better to leave behind the word "supremacy" and keep referring to "advantage" only.