[afthonos]

Thanks for the detailed response; I am not a physicist, so I didn’t catch the sleight of hand in the linear scaling claim. The timing of the “rebuttal” is almost certainly intentional, and possible because of the accidental pre-publication last month. I hope the rebuttal is indeed specious, because it’s an exciting advance; I’m sure time will tell.

[tagrun]

It's pretty easy and requires no physics, actually.

Here's a simple, extended version.

A quantum gate is, mathematically speaking, a matrix. For a given physical system, of fixed number of qubits, obtaining that matrix on a classical computer takes (on average) a fixed amount of time, let's say T seconds. A quantum "circuit" is a sequence of quantum gates, applied consecutively in time, and you simply multiply them all to get their overall effect.

So if your circuit is made of 10 gates, the total CPU time is 10T, plus the time for 10-1 matrix multiplications. If it is 20 gates, then it is 20T plus time for 20-1 matrix multiplications.

Since multiplying two matrices of the same dimension also takes a fixed amount, on average, the simulation time grows linearly with circuit depth.

The quantum supremacy is related to how T grows as you increase the number of qubits, n (which is exponential, it's a 2^n by 2^n matrix).