In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
FIG 3. Control operations for the quantum supremacy circuits. a, Example quantum circuit instance used in our experiment. Every cycle includes a layer each of single- and two-qubit gates. The single-qubit gates are chosen randomly from $\{\sqrt X, \sqrt Y, \sqrt W\}$. The sequence of two-qubit gates are chosen according to a tiling pattern, coupling each qubit sequentially to its four nearest-neighbor qubits. The couplers are divided into four subsets (ABCD), each of which is executed simultaneously across the entire array corresponding to shaded colors. 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. b, Waveform of control signals for single- and two-qubit gates.
They also show some plots in FIG 4, apparently proving their claim of quantum supremacy.
FIG. 4. Demonstrating quantum supremacy. a, Verification of benchmarking methods. $\mathcal{F}_\mathrm{XEB}$ values for patch, elided, and full verification circuits are calculated from measured bitstrings and the corresponding probabilities predicted by classical simulation. Here, the two-qubit gates are applied in a simplifiable tiling and sequence such that the full circuits can be simulated out to $n = 53, m = 14$ in a reasonable amount of time. Each data point is an average over 10 distinct quantum circuit instances that differ in their single-qubit gates (for $n = 39, 42, 43$ only 2 instances were simulated). For each $n$, each instance is sampled with $N$s between $0.5 M$ and $2.5 M$. The black line shows predicted $\mathcal{F}_\mathrm{XEB}$ based on single- and two-qubit gate and measurement errors. The close correspondence between all four curves, despite their vast differences in complexity, justifies the use of elided circuits to estimate fidelity in the supremacy regime. b, Estimating $\mathcal{F}_\mathrm{XEB}$ in the quantum supremacy regime. Here, the two-qubit gates are applied in a non-simplifiable tiling and sequence for which it is much harder to simulate. For the largest elided data ($n = 53$, $m = 20$, total $N_s = 30 M$), we find an average $\mathcal{F}_\mathrm{XEB} > 0.1\%$ with $5\sigma$ confidence, where $\sigma$ includes both systematic and statistical uncertainties. The corresponding full circuit data, not simulated but archived, is expected to show similarly significant fidelity. For $m = 20$, obtaining $1M$ samples on the quantum processor takes 200 seconds, while an equal fidelity classical sampling would take 10,000 years on $1M$ cores, and verifying the fidelity would take millions of years.
Question:
In FIG 4 caption there's this sentence: "For $m = 20$, obtaining 1M samples on the quantum processor takes 200 seconds, while an equal fidelity classical sampling would take 10,000 years on 1M cores, and verifying the fidelity would take millions of years". What does "obtaining samples" mean in this context? Are they saying that in 200 seconds their quantum processor executed the circuit 1M times (as in 1M "shots") and they consequently measured the output state vector 1M times? Or something else?
More importantly, I don't really understand the overall claim in the paper. Is the paper (FIG 4 caption) saying that for some random unitary $U$ (over 53 qubits and 20 cycles), a classical computer would take 10,000 years to calculate the resultant state vector $|\Psi_U\rangle$? As far as I understand, determining the final state vector is simply matrix multiplication that scales as $\mathcal O(n^3)$ (in this context, $n=2^{\text{total number of qubits}}$) in general (or lesser, depending on the algorithm used). Is it claiming that a classical computer would take 10,000 years to perform that matrix multiplication, and so using a quantum computer would be more efficient in this case?
Prequel(s):
Related:
Do quantum supremacy experiments repeatedly apply the same random unitary?