5
$\begingroup$

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."

$\endgroup$
7
  • 6
    $\begingroup$ That's a nice question. Regarding the book however, I'd be cautious with its claims. $\endgroup$
    – Rammus
    Jun 13, 2023 at 20:52
  • $\begingroup$ @Rammus Thank you and I agree with you. I'm reading it and taking it all with a grain of salt. I've now completed 176 pages and it is actually very little about QC and very much about "what QC could maybe, possibly do in the possible future". It's somewhat of a nice overview of what researchers might use QC for though, so it is interesting in places. $\endgroup$
    – raddevus
    Jun 13, 2023 at 20:57
  • $\begingroup$ @Rammus - I'm reading the article at the link you posted & am amazed and thrilled that the author there mentions a similar (probably hyperbolic) quote about Quantum Supremacy so it's very interesting. Thanks for that link. Very interesting article. $\endgroup$
    – raddevus
    Jun 13, 2023 at 21:02
  • $\begingroup$ are you asking in general why one would "demonstrate quantum supremacy", or how it's done in this specific case? See also quantumcomputing.stackexchange.com/q/4756/55 $\endgroup$
    – glS
    Jun 13, 2023 at 21:48
  • $\begingroup$ @glS I'm not actually asking either of those questions. I'm asking "how you would prove or even get the idea that you have the solution that takes 500 million years to get? How would you know you achieved the correct result?" $\endgroup$
    – raddevus
    Jun 13, 2023 at 22:53

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ that youtube video (mostly) recommends books that actually cover the topics from a technical perspective. I don't think those are really comparable with popular science books. Except possibly for Aaronson's book. $\endgroup$
    – glS
    Jun 13, 2023 at 21:46
  • $\begingroup$ @glS I added a pedagogical book on quantum mechanics. $\endgroup$ Jun 13, 2023 at 21:56
  • 1
    $\begingroup$ @gIS, Lanes posted a followup video on more accessible books on the same channel somewhere. $\endgroup$ Jun 14, 2023 at 3:43
  • $\begingroup$ Here youtube.com/watch?v=rbcNQB7VMtI is her second video. It does end with Sakurai though. $\endgroup$ Jun 15, 2023 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.