Number of qubits to achieve quantum supremacy?

Question

Google's Sycamore paper describes achieving quantum supremacy on a $53$-qubit quantum computer. The layout of Sycamore is $n=6\times 9=54$ nearest neighbors, with one qubit nonfunctional. They apply $m=20$ total cycles in their experiment; each cycle is a random single-qubit rotation $\{\sqrt{X},\sqrt{Y},\sqrt{W}\}$ followed by a two-qubit tile of their Sycamore-specific gate, similar to an $\mathrm{iSWAP}$.

However, Alibaba had previously indicated that such size quantum computers are simulatable classically on a supercomputer. See, e.g. Classical Simulation of Intermediate-Size Quantum Circuits by Chen, et al., which states:

...by successfully simulating quantum supremacy circuits of size $9×9×40$, $10×10×35$, $11×11×31$, and $12×12×27$, we give evidence that noisy random circuits with realistic physical parameters may be simulated classically.

Was the random quantum circuit on Sycamore specifically designed to make Alibaba's (or others) approach of classical simulation difficult?

Did Google close a hole in Alibaba's work? Or am I misreading some aspect of the work?

Answer 1

"Was the random quantum circuit on Sycamore specifically designed to make Alibaba's (or others) approach of classical simulation difficult? Did Google close a hole in Alibaba's work?"

No. They had been talking about their quantum supremacy quest at conferences at least as far back as 2016, and had started publishing papers about it as early as 2018, for example here and here and here. The Alibaba paper that you mentioned was from May 2018, so Google's effort from 2016-2018 was not trying to "close a hole" in the May 2018 work.

I have also mentioned in my answer to: How does the recent Chinese quantum supremacy claim compare with Google's? that Google did not really do anything that classical computers couldn't do at the time (people from IBM actually pointed out almost immediately after Google's press releases, that Google assumed that the classical computer only had RAM and no disk, meaning that the classical storage capacity was far smaller than it could have been, even at the time of those announcements). If you take into account the number of petabytes that some classical supercomputers at the time of Google's "supremacy" announcement had, then you would need more than 53 qubits in order to have a quantum state that's too big for classical computers to store with enough accuracy to compete with Google's experiment. Indeed, Titan was active from 2012-2019 and had 40 PB of disk space and Summit, which has been active since 2018 has 250 PB of disk space. The full wavefunction of 54 qubits has 2^54 or about 1.8 x 10^16 elements, which would only take 144 PB of disk space if assuming double-precision arithmetic (8 bytes for each element of the wavefunction vector) and absolutely zero intelligence going into making the classical computation more efficient.

Furthermore, Craig Gidney said here that the classical computer would have been 2^(20*7/4) = 34359738368 faster if Google's hardware used CZ gates instead of their Sycamore-specific gates. Furthermore, Figure 1 of the Alibaba paper that you mentioned, shows that it wasn't hard to simulate a circuit with 144 qubits and get an element of the final 144-qubit wavefunction from that simulation. In that sense, Google did not even "close a hole" in Alibaba's work, it was Alibaba that "opened a hole" in Google's: namely, the fact that you need way more than 53 qubits to achieve quantum supremacy, especially when circuit depths are so short and there's so much noise.

Answer 2

From the paper you refer, it turns out that the possible simulation of quantum circuit is made for certain type of circuits: simplificable ones.

From another post [1] I observed the Google's supremacy was achieved on non-simplificable, so called intractable sequence.

So to answer the question, whether Alibaba's approach was made difficult: yes - definitively that was the case.

Sources:

[1] Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 3): sampling

Edit:

You're right, only my source post and Google's paper speak about simplificable vs. intractable in the sense I was thinking:

Here we show an intractable sequence (repeat ABCDCDAB); we also use different coupler subsets along with a simplifiable sequence (repeat EFGHEFGH, not shown) that can be simulated on a classical computer.

(take from Google's paper, fig.3 figure text.)

Here, the two-qubit gates are applied in a non-simplifiable tiling and sequence for which it is much harder to simulate.

(take from Google's paper, fig.4 figure text.)

Another points I found:

Alibaba calculates only one amplitude of the signal. All amplitudes of 50 qubits would have taken 16 petabytes, but they used only one peta in their whole experiment, so they did not actually simulate all, as Google guys tried.

Google used different algorithms and their classical power ended in 40 qubits size. As I understand this Alibaba guys went here beyond, but needed to compromise the amount of data simulated. Google guys made it through another algorithm to get 'amplitudes of individual bitstrings', only that they stopped, as the amount of expected time went out of their hands.

Situation: Alibaba got one amplitude and Google got an estimate of time for all amplitudes.