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

Question

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):

^{Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set}

^{Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 2): simplifiable and intractable tilings}

---

^Related:

^{Do quantum supremacy experiments repeatedly apply the same random unitary?}

Answer 1

What does "obtaining samples" mean in this context?

The same thing it means in a more classical context. Consider the probability distribution of the possible outcomes of a (possibly biased) coin flip. Sampling from this probability distributions means to flip the coin once and record the result (head or tail). If you sample many times, you can retrieve better and better estimates of the underlying probability distribution, fully characterising it in the limit of infinite samples collected.

In the context of quantum supremacy experiments, the sampling refers to the probability distribution at the output of the circuit/experiment. Given a circuit modelled by a unitary $\mathcal U$, fixing an input state $|\psi_i\rangle$, and fixing a measurement choice (say the computational basis), you get a probability distribution over the possible outputs: $p_{\boldsymbol j}\equiv|\langle \boldsymbol j|\mathcal U|\psi_i\rangle|^2$, where $|\boldsymbol j\rangle\equiv|j_1,...,j_n\rangle$ denotes a possible output state (a possible sequence of ones and zeros).

Sampling from the circuit then means to sample from this $\boldsymbol p$; to repeat the same experiment multiple times and record the outcomes.

re 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?

Sort of. They are not "measuring the output state vector", as that would require to do tomography of the output state. Rather, if the output state $|\psi_o\rangle$ expands in the computational basis as $$|\psi_o\rangle=\sum_{\boldsymbol j}c_{\boldsymbol j}|\boldsymbol j\rangle,$$ what they are doing is observing which of the $|\boldsymbol j\rangle$ comes out of the experiment, and "writing down" the sequence of such observed events.

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$?

Again, as per the above, not quite. They are not calculating $|\Psi_U\rangle$, but rather only sampling from its associated probability distribution. To actually compute the state would require tomography, which would be even harder (indeed, I'm not sure about the specific result underlying this experiment, but in other similar scenarios one can show that not even a quantum computer can reconstruct efficiently the output state). Retrieving the output state is a harder task than just sampling from it.

Is the overarching claim of the paper that a classical computer would not be able to "calculate" the theoretical noise-free "probability distribution" by simple matrix multiplication (in any reasonable time-frame)?

Indeed, these quantum supremacy experiments rely on such classical hardness results. Actually, it is not even that you can prove that classical computers cannot efficiently compute the output probability distribution of these IQP circuits, but rather that they cannot even sample from these probability distributions. You might try to have a look at the references in Appendix VII (page S8) of Neill et al. for the relevant papers and results.

Note that sampling from a distribution is a much easier task than computing it. To understand this, consider the trivial example of sampling from the output distribution of a $50$-qubit circuit which solely consists of Hadamard gates applied at each qubit. In this case, the output probability distribution is the uniform distribution: each output configuration $|\boldsymbol j\rangle$ is equally likely. Sampling from such a thing is trivial: just have your classical computer draw $50$ random bits and you're done. However, computing the probability distribution would require to store $2(2^{50}-1)\sim 2\times 10^{15}$ real numbers, which while still doable, is clearly much harder.

Now imagine what happens in a less trivial example in which there are actual non-trivial entangling gates in the circuit: to compute the output state you will need to perform a number of operations on these giant-dimensional vectors ${}^{(1)}$. On the other hand, the quantum device solves the sampling task naturally: you just look at the output of the device.

As far as I understand, determining the final state vector is simply matrix multiplication that scales as $O(n^3)$ (in this context, $n=2\times\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?

They are. I mean, you say "just $n^3$", but this means to operate with vectors of dimension $\sim(2^{50})^3\sim 2^{150}\sim 10^{45}$. Try to create a list of this dimension with your preferred programming language and see how fast your laptop crashes! They mention in page 5 in the paper how they managed to use a $250 \mathrm{TB}$ device to store up just to $43$ qubits, which I think shows quite well the hardness of the task. Mind you, one can use other data types to store this kind of states, e.g. exploiting the sparseness of the states, and this is why, as mentioned in the caption you transcribed, the number of cycles increase the hardness. At each cycle, the state is spanning larger and larger sections of the Hilbert space, thus becoming less sparse and making it harder to use tricks to simulate the behaviour of the system.

I guess I'm confused about what they really mean by "classical sampling" as compared to "Sycamore sampling"

"Classical sampling" means that you have a program that gives you a sequence of configurations (length-$50$ bitstrings) $\boldsymbol j$ according to the correct probability distribution. "Sycamore sampling" means that they are using their physical device to achieve this, and thus do not need to bother with computing anything, but instead just need to observe the output of their device.

More explicitly, suppose you have a $5$-qubit circuit. Three samples from the output probability distributions could be the following three bitstrings: $$10111, 11111, 00010.$$ Being able to produce these three bitstrings is not the same as being able to produce the set of $2^5-1$ real numbers that are the probabilities of each occurrence.

What you write as "Sycamore sampling", is exactly the same thing. The problem is still that of producing a number of samples such as the above ones. But now you don't need a classical computer to run an algorithm to produce them, using directly the quantum device instead. This will evolve a quantum system in some way, and then you measure the qubits at the end and you find, for each experimental run, a configuration of five bits. You repeat the experiment three times, and you get three samples like the above ones.

---

(1) Note that, for the sake of exposition, I might be giving the impression here that to solve the sampling problem classically one needs to compute and store in memory the full probability distribution. While this is the naive way to do it, there are better ways. The computational complexity results rule out more generally that the sampling is classically hard, and make no reference to actually computing the probability distribution.