# Number of qubits to achieve quantum supremacy?

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?

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:

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.

• What is the (your?) definition of "simplificable" circuits? What makes a circuit "simplificable" vs. "intractable?" The Google paper mentions that ABCDCDAB is intractable while EFGHEFGH is simplifiable. Did Alibaba show, for example, how to classically simulate EFGHEFGH but not ABCDCDAB? Sep 29, 2019 at 18:11
• Re: "Alibaba got one amplitude and Google got an estimate of time for all amplitudes" - I'm not sure if that's entirely correct? For example, it is my understanding that the "Schrodinger algorithm" calculates the amplitude of each basis; the "Feynman algorithm" calculates the amplitude of a given basis. The "Schrodinger-Feynman algorithm" is a hybrid of the two. (?) I think it's more about the pattern of gates applied - Alibaba was able to simplify their gates and I think Google designed their gates to maximize entanglement (??) Oct 23, 2019 at 12:00