China's claim to quantum supremacy - what you should know
Contents
What’s this about China and quantum supremacy?
But what’s quantum supremacy? Why care?
What’s asymptotic speedup, and why is it relevant to quantum computing?
It’s not about quantum vs conventional computers, it’s about exponential vs quadratic complexity
How does the Jiuzhang quantum computer work?
What’s this about China and quantum supremacy?
Last month, on Dec 3rd, 2020, China’s leading quantum research group, based mainly at the University of Science and Technology of China (USTC) and led by Pan Jianwei, claimed to have achieved “quantum supremacy”. They did this by using a 76-qubit light-based prototype quantum computer named Jiuzhang, in homage to an ancient classic math book called Jiŭzhāng Suànshù written by generations of scholars over 2,000 years ago. Pan Jianwei himself is a world leader in QC: the scientific journal Nature named him “Father of Quantum”, and he recently won the ZEISS Research Award (previous recipients have subsequently won the Nobel Prize).
Jiuzhang, claimed Pan’s group, achieved quantum supremacy by taking about 3 minutes to do a specific computational task that would require a staggering 2.5 billion years on China’s fastest supercomputer and the world #3, the Sunway TaihuLight — half the Earth’s age, or 40x longer than the time elapsed since the dinosaurs went extinct.
The particular computational task that Jiuzhang did is called BosonSampling. Very roughly, it involves passing identical non-interacting photons through an array of beam-splitters and measuring where the photons end up. BosonSampling doesn't have any known applications yet, although there are various proposed applications in the academic literature (but nobody knows if these applications actually give quantum computers an edge over conventional computers). Its main value, according to its co-inventor Scott Aaronson, is as a stepping stone guiding research efforts towards “universal quantum computing”.
China isn’t the first to claim quantum supremacy: Google did the year before. Its Sycamore quantum processor took 3 minutes to do a BosonSampling task that Google claims would’ve taken 10,000 years on the world’s fastest (conventional) supercomputer. What Pan’s group at USTC achieved with Jiuzhang differs in four key respects:
Jiuzhang is purportedly 10 billion x faster than Sycamore
Jiuzhang can only do BosonSampling and nothing else, whereas Sycamore is a fully-programmable general-purpose computer that can run any quantum algorithm, making the latter’s capabilities more applicable to real-world tasks
Jiuzhang demonstrated that quantum supremacy is possible via light-based computing (or “photonics”), whereas Sycamore is superconductor-based. This matters because quantum computing as a whole is in an early-enough stage of development that there’s still many different approaches being pursued towards physical implementation, and nobody agrees which is the “best”. (Contrast this with conventional computing, where everyone agrees that the “best” approach to implementation is semiconductor-based.) In particular, superconductor-based QC has gotten a lot of funding and attention, whereas photonics QC has historically been the dark horse. So having two different approaches demonstrate quantum supremacy shows that quantum computing as a whole is rapidly progressing
USTC’s research group could not have cheated, while Google’s group could have (in theory): IBM pointed out that the Sycamore experiment’s “output states” were few enough they could’ve been stored on a big hard drive to generate fake “samples” later, while the Jiuzhang experiment’s output states were so numerous that it would be impossible to do the same
(By the way, conventional computing is also called “classical” computing in the academic literature, to distinguish it from quantum computing. The two terms are used interchangeably.)
But what’s quantum supremacy? Why care?
First I’ll tell you what it doesn’t mean. These misconceptions are often trumpeted across various media outlets; what makes them stick is that they use correct terms and milestones (e.g. “fault-tolerant”), just in wrong ways or irrelevant contexts:
Quantum supremacy is not about “useful quantum computing”
Quantum supremacy is not about “scalable quantum computing”
Quantum supremacy is not about “fault-tolerant quantum computing”
It is absolutely the case that for quantum computing to be “impactful” and “revolutionary” it will have to be useful, by being both scalable and fault-tolerant. But those come after quantum supremacy. Quantum supremacy is a much lower bar (albeit one that’s taken the world’s leading researchers years and millions of dollars to make just partial progress on).
So if quantum supremacy doesn’t mean any of the above, what does it mean? I’ll let Scott Aaronson again do the talking:
It’s the use of a quantum computer to solve some well-defined set of problems that would take orders of magnitude longer to solve with any currently known algorithms running on existing classical computers—and not for incidental reasons, but for reasons of asymptotic quantum complexity.
The emphasis here is on being as sure as possible that the problem really was solved quantumly and really is classically intractable, and ideally achieving the speedup soon (with the noisy, non-universal QCs of the present or very near future).
If the problem is also useful for something, then so much the better, but that’s not at all necessary. The Wright Flyer and the Fermi pile weren’t useful in themselves.
In short: quantum supremacy is about proving that quantum computers can in fact beat conventional computers at some task.
Why does this matter? Because it’s not at all obvious that quantum computers can be better than conventional computers at any task — the predominant view in academia is that they can be for some tasks, but it’s never even been demonstrated until now. (Contrast this to the mainstream media hype around quantum as some sort of magic speedup for any problem, “if only we could get it to work”.)
Two key features worth highlighting for demonstrating quantum supremacy:
The task (or problem) need not be useful; we just want to show, for a start, that quantum computers can beat conventional computers at something. BosonSampling isn’t useful for instance
The task needs to be exploitable specifically by quantum phenomena to yield asymptotic speedup (see Scott’s quote above)
The second point isn’t just relevant to quantum supremacy, but to the potential impact of quantum computing as a whole, so it’s worth belaboring:
What’s asymptotic speedup, and why is it relevant to quantum supremacy?
The second half of this question is more straightforward to answer: not all tasks give quantum computers an edge over conventional computers, so it would be a mistake to use them like so. Only some tasks do. (This means quantum computers will complement, not replace, conventional computers, a little like how GPUs complement but not replace CPUs because the former are much faster at highly-parallelizable tasks but worse at general tasks.)
Which brings us to the first half of this question. This requires a quick detour.
Computational complexity theory is a subfield of computer science that studies, informally put, how “hard” problems are and how “efficient” algorithms to solve those problems are. More precisely, the complexity of an algorithm is the amount of resources (usually “number of steps in algorithm”) needed to run it to solve a problem. The amount of resources is expressed as a function of the problem size. For instance, the usual algorithm for multiplying integers has “quadratic complexity”: multiplying two 1-digit numbers takes only 1 step, but two 2-digit numbers take 2 x 2 = 4 steps and two 100-digit numbers take 100 x 100 = 10,000 steps; here the “problem size” (or “input size”) is the number of digits, and the “complexity” is the number of steps the algorithm needs to do the multiplication.
Quadratic complexity looks bad, but it’s actually pretty good. What’s worse is exponential complexity. Take prime factorization, which matters for cryptography (in particular RSA encryption, one of the most widely-used cryptosystems worldwide). The task sounds simple: factorize an integer into its “constituent” primes. So for instance
21 = 3 x 7
48 = 3 x 16 = 3 x 2 x 2 x 2 x 2
It turns out that this seemingly-simple task is actually fiendishly hard in the computational complexity sense, because all the algorithms we know of for factoring integers into primes have exponential complexity instead of quadratic: factoring a 1-digit number may take (say) 3 steps, but factoring a 10-digit number may take 3 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 3 x (2^10) ≈ 3,000 steps and a 100-digit number may take 3 x (2^100) ≈ 3,000 billion billion billion steps — contrast this with the 10,000 steps above for quadratic complexity!
The point is that there’s not only a huge gap between exponential and quadratic complexity, but also the gap grows bigger as the task gets bigger. And real-world tasks involve arbitrary task sizes. This is why we only care about the “behavior” of the complexity for large task sizes (i.e. on its asymptotic behavior, hence “asymptotic speedup”.)
So, at least in theory, this is why quadratic algorithms are “better” in this sense than exponential algorithms: they give us asymptotic speedup.
(They’re not “the best”: there are many "faster" complexity classes. Most obviously, some tasks e.g. “find any element in this array” have “constant-time” algorithmic solutions — it takes the same number of steps (1) to pick any random element regardless of how big the array is. And there’s log-time algorithms, and linear-time algos, all of which are faster than quadratic-time. But I digress.)
Enter Peter Shor, an applied mathematician at MIT. In 1994 Shor came up with an algorithm that factorizes integers into primes in quadratic time instead of exponential. What Shor did differently from everyone else in his algorithm was use a piece of math that specifically needs quantum phenomena to be implemented physically, so conventional computers can’t run this algorithm, only quantum computers can. (The piece of math in particular is called the quantum Fourier transform, the quantum analogue of the “usual” inverse Fourier transform. Scott Aaronson tries to explain Shor’s algorithm without using math here in case you’re interested.) Shor’s discovery of his explicitly-quantum quadratic-time algorithm, and for such a relevant task too (cryptography!), galvanized quantum computing research: what other tasks have exponential-time classical algorithms but quadratic-time quantum algorithms?
(Not much, really: prime factorization, BosonSampling, sampling the output distribution of random quantum circuits… that’s about it.)
It’s not about quantum vs conventional computers, it’s about exponential vs quadratic complexity
One thing is worth highlighting that most lay journalistic coverage misses and most quantum computing researchers find too obvious to mention: it’s not really about quantum vs classical computers, or quantum vs classical algorithms. It’s about quadratic vs exponential complexity for specific tasks (or some other step down in complexity class, like exponential to polylog). It just so happens that, for the tasks that quantum researchers suspect QC will give speedup (like prime factorization above),
there are quadratic-time quantum algos (e.g. Shor’s algorithm)
the best alternative classical algos are exponential-time
This all changes if researchers discover quadratic-time classical algos: then quantum wouldn’t provide a speedup anymore, because it’s just quadratic vs quadratic. No more asymptotic speedup! Again using prime factorization as an illustrative example, nobody knows if there isn’t a quadratic-time classical algo, and nobody has proven that there isn’t.
Is this just a theoretical concern? No. The most dramatic example of this happened in 2018. The task, informally: recommend movies you might enjoy (e.g. Netflix’s auto-recommender), given your history of favorited movies. The fastest known classical algorithm was exponential-time. The fastest quantum algorithm was polylog-time, by Kerenidis & Prakash (KP). KP’s algo was in fact the flagship application of how quantum computing gives asymptotic speedup to “real-world” machine learning problems. Then along came 18 year old Ewin Tang, who in her undergrad thesis discovered a classical polylog-time algo. Polylog (classical) vs polylog (quantum): no more speedup for quantum! (This was such a big deal, incidentally, that it catapulted Tang into Forbes’ 30 under 30 list.)
Less dramatic but still very relevant: remember how, when Google lay claim to the first instance of quantum supremacy back in 2019 by using its Sycamore processor to do a BosonSampling task in ~3 minutes, it “estimated” that the world’s fastest conventional computer would’ve taken 10,000 years? That supercomputer in particular was the IBM Summit. IBM, apparently irritated, shot back that Summit would’ve only taken at most 2.5 days instead of 10,000 years (“a conservative, worst-case estimate,” they added). This 1.5-million-fold speedup isn’t because IBM’s Summit supercomputer is 1.5 million x faster than Google anticipated, but just because there were better-complexity classical algos Google didn’t consider (among other reasons). The point is that it’s disingenuous to compare your best to a bad benchmark; of course you compare it to the best alternative!
This concern may apply to BosonSampling too. Scott Aaronson and colleagues have evidence against the possibility that there can be a classical algo faster than exponential-time (removing quantum’s asymptotic speedup advantage), but he concedes that “some future breakthrough may change the outlook and remove the case for quantum supremacy”.
How does the Jiuzhang quantum computer work?
To understand how Jiuzhang works, and why it can only do BosonSampling, it’s worth understanding how BosonSampling itself works.
The setup for boson sampling is a little like a bean machine:
You drop balls from the top into the rows of pegs, and they bounce off the pegs and each other until they land in slots at the bottom, forming a distribution:
It’s easy for a conventional computer to simulate the distribution of balls in slots.
BosonSampling replaces balls with photons, pegs with mirrors and prisms, and slots with light detectors. Unlike balls, photons behave in weird quantum ways (in particular, they interfere with each other) which lead to an exponentially-increasing number of possible distributions. This means that simulating the distribution of photons on a conventional computer requires exponential-time algorithms (again with the caveat from the previous section that this will no longer be true if someone is smart enough to figure out a faster classical algo).
Jiuzhang, in contrast, is the BosonSampling setup. This is precisely why it’s both so good at BosonSampling and useless for anything else. But since quantum supremacy is only about showing that there’s some task where quantum computers are unambiguously faster than conventional computers by exploiting quantum phenomena to get asymptotic speedup, Jiuzhang’s achievement definitely “counts”, and so shouldn’t be thought of as “lawyering”.
Not only that, Jiuzhang represents an impressive technical achievement. BosonSampling is incredibly hard to scale up, essentially because photons are very '“fickle”. For the longest time the world’s leading photonics groups were stuck at 5-6 photon setups. Then in 2019 Pan’s group at USTC managed 14 photons. With Jiuzhang they’ve now managed an incredible 76 photons. This puts China at the very forefront of quantum computing research, and photonics as one of the two best candidates (alongside superconductors with Google’s Sycamore) for how quantum computers will eventually be physically implemented.