Quantum Supremacy: Some questions on cross-entropy benchmarking

Question

I was skimming through the Google quantum supremacy paper but got stuck on this section:

For a given circuit, we collect the measured bit-strings $\{x_i\}$ and compute the linear XEB fidelity [24-26, 29], which is the mean of the simulated probabilities of the bit strings we measured:

$$\mathcal{F}_{\text{XEB}} = 2^n\langle P(x_i)\rangle - 1 \tag {1}$$

where $n$ is the number of qubits, $P(x_i)$ is the probability of bitstring $x_i$ computed for the ideal quantum circuit, and the average is over observed bitstrings. Intuitively, $\mathcal{F}_\text{XEB}$ is correlated with how often we sample high probability bitstrings. When there are no errors in the quantum circuit, sampling the probability distribution will produce $\mathcal{F}_\text{XEB} = 1$. On the other hand, sampling from the uniform distribution will give $\langle P(x_i)\rangle_i = 1/2^n$ and produce $\mathcal{F}_\text{XEB} = 0$. Values of $\mathcal{F}_{XEB}$ between $0$ and $1$ correspond to the probability that no error has occurred while running the circuit.

Questions:

1. If $\mathcal{F}_{XEB} = 1$ when $x_i$ are sampled from the correct distribution then $\left< P(x_i) \right>_i$ must be $2^{1-n}$ (for any quantum circuit). That seems to restrict the output probability distributions of all quantum circuits to rather high entropy distributions. This is not what I would have expected for any kind of computation. Is this correct?

2. If $P(x_i)$ is the probability of bitstring $x_i$ computed for the ideal quantum circuit, then how can $\left< P(x_i) \right>_i$ equal $1/2^n$ when the bitstrings $x_i$ are sampled from the uniform distribution? This is the result we would see if $P(x_i)$ had been $1/2^n$ for all $x_i$ (i.e. the probability mass function for the uniform distribution), but it is explicitly stated that $P(x_i)$ is the probability of bitstring $x_i$ computed for the ideal quantum circuit. Intuitively it seems to me more reasonable to assume that $\left< P(x_i) \right>_i$ with $x_i$ sampled from the uniform distribution would be much closer to zero, because if $P(x_i)$ concentrates much of its probability mass to a relatively low number of bitstrings (as I would assume computation to do) then $P(x_i) = 0$ for almost all bitstrings from the uniform distribution.

3. How can the value of $\mathcal{F}_{XEB}$ correspond to "the probability that no error has occurred while running the circuit"? This sounds so simple/simplistic to me that it's hard to believe.

UPDATE 2019-10-23: The article Quantum supremacy using a programmable superconducting processor has now been published in Nature, and the Supplementary Information is available there.

Having read section IV (XEB Theory) of the Supplemental Information I'd like to adjust my questions as follows:

1. Subsection C (Two limiting cases) derives this fact from the properties of probability distributions of the Porter-Thomas shape. The derivation looks correct to me. The answer here seems to be that my intuition (that the output distribution would be relatively low entropy) was simply wrong.

2. Subsection C also contains this passage: "[Suppose] bitstrings $q_i$ are sampled from the uniform distribution. In this case $P(q_i) = 1/D$ [where $D = 2^n$] for every i and $F_{XEB} = 0$." I see this as very problematic since the main text of the article makes the claim that "$P(x_i)$ is the probability of bitstring $x_i$ computed for the ideal quantum circuit". How can these two statements be reconciled?

3. Subsection V (Quantifying errors) contains a lengthy discussion of this. I can't say I understand it in full, but I'll give it the benefit of a doubt for now.

So, in summary, my question is now: The main article states that "$P(x_i)$ is the probability of bitstring $x_i$ computed for the ideal quantum circuit". However, Supplementary Information section IV.C seems to argue that if the "qubits are in the maximally mixed state" (i.e. the quantum computer doesn't work) then "the estimator [$F_{XEB}$] yields zero fidelity" since $P(x_i) = 1/2^n$ for every $i$ in this case. But then, in this case, $P(x_i)$ is clearly the probability of sampling bitstring $x_i$ from the non-ideal empirical distribution. Isn't this a contradiction?

As I see it either $F_{XEB}$ is computed such that $P(x_i)$ is the probability of $x_i$ being sampled from the ideal quantum circuit, or it is computed such that $P(x_i)$ is the probability of $x_i$ being sampled from the empirical non-ideal distribution. It can't be both. Which is it?

Answer 1

After some further consideration I think it's quite clear that the only probability mass function evaluated in the computation of $\mathcal{F}_{\text{XEB}}$ is that of the classically computed ideal distribution, denoted $P(x_i)$ in the main paper.

This leads me to the conclusion that the phrasing of the following excerpt from section IV.C of the Supplemental Information (and especially the part underlined in red) is a bit unfortunate/misleading:

Just because the empirically measured bitstrings are coming from the uniform distribution doesn't mean that $P(x_i)$ is suddenly $1/2^n$ for all $i$. $P(x_i)$, as it goes into the calculation of the $\mathcal{F}_{\text{XEB}}$, is still the probability of sampling bitstring $x_i$ from the classically computed ideal distribution. This is in general not $1/2^n$.

The correct reasoning is that the fact that $\langle P(x_i)\rangle_i$ will be $1/2^n$ (and $\mathcal{F}_{\text{XEB}} = 0$) when bitstrings $x_i$ are sampled from the uniform distribution follows from the definitions of expectation and probability mass function:

The definition of expected value is the following sum $$ \langle P(x_i)\rangle_i = \sum_{i=1}^{2^n} P(x_i) p_i $$ where $P(x_i)$ is the probability of bitstring $x_i$ being sampled from the classically computed ideal quantum circuit, $p_i$ is the probability of $x_i$ being sampled from the non-ideal empirical distribution, and the sum runs over all possible bitstrings.

When bitstrings are coming from the uniform distribution $p_i$ will always be $1/2^n$ so can be broken out of the sum: $$ \langle P(x_i)\rangle_i = \frac{1}{2^n} \sum_{i=1}^{2^n} P(x_i) $$ When you sum any probability mass function (of which $P(x_i)$ is one example) over all the possible outcomes you by definition get 1, and thus: $$ \langle P(x_i)\rangle_i = \frac{1}{2^n} $$

Answer 2

That seems to restrict the output probability distributions of all quantum circuits to rather high entropy distributions.

The output of a typical randomly chosen quantum circuit is rather high entropy. That doesn't mean you can't construct circuits that have low entropy outputs (you can), it just means that picking random gates is a bad strategy for achieving that goal.

how can i $P(x_i)$ equal $\frac{1}{2^n}$ when the bitstrings $x_i$ are sampled from the uniform distribution?

How could it equal anything else? The probabilities of the target distribution have to add up to one, and you're picking each element $\frac{1}{2^n}$ of the time. For example, if there was a single element with all the probability, you'd score $0 \times \frac{2^n - 1}{2^n} + \frac{1}{2^n} = \frac{1}{2^n}$. You always score $\frac{1}{2^n}$ on average when picking randomly.

How can the value of $\mathcal{F}_{XEB}$ correspond to "the probability that no error has occurred while running the circuit"?

When the paper says "the probability that no error occurs", what it means is "In the systemwide depolarizing error model, which is a decent approximation to the real physical error model at least for random circuits, the linear xeb score corresponds to the probability of sampling from the correct distribution instead of the uniform distribution.".

Physically, it is obviously not the case that either a single error happens or no error happens. For example, every execution of the circuit is going to have some amount of over-rotation or under-rotation error due to imperfect control. But that's all very complicated. To keep things simple you can model the performance of the system as if your errors were from simpler models, such as each gate have a probability of introducing a Pauli error or such as you either sample from the correct distribution or the uniform distribution.

Simplified models actually do a decent job of predicting system performance, particularly on random circuits. For example, consider the way the fidelity decays as the number of qubits and number of layers are increased. The fidelity decay curve from the paper matches what you would predict if every operation had some fixed probability of introducing a Pauli error.

Answer 3

As an initial matter, I think the Supplementary Information (linked in some other answers on this sight) has a significant amount of discussion on $\mathcal{F}_{XEB}$.

However, as I understand it (misunderstandings are my own):

1. There is indeed a concentration of outputs from a random quantum circuit, away from a state wherein the square of the coefficients of each basis is $1/2^n$. It's clear that sampling from a random quantum circuit will never output a string $x_i$ when the amplitude $\alpha$ of $|x_i\rangle$ is $0$ - that is, if, after application of the quantum circuit, we have $\alpha|x_i\rangle$ and $\alpha=0$, then sampling will never output $x_i$. Instead, sampling from a state so produced leads to the "Porter-Thomas" distribution, about which I don't know much. That is, if you were to sample a string from a state generated from a random quantum circuit, and if you were to, then, calculate the squared amplitude of sampling said string from said quantum circuit, then the expected squared amplitude is $2/2^n$, and not $1/2^n$.

2. I think in the uniform distribution, $P(x_i)=1/2^n$ for all $x_i$, but if we get any string from the random quantum circuit, there's good odds that that string is more likely to be seen from the random quantum circuit than from the uniform distribution. For $i$ that are in the "shadow" of the speckle, you would never sample them. As I understand it, classical simulation does not generate all $2^{53}$ coefficients; instead, classical simulation looks at the string output of the random circuit and asks whether the squared coefficient of that basis is greater than $1/2^{53}$.

3. Upon review, I think that the average fidelity $\mathcal{F}_{XEB}$ of a sample of strings wherein there was at least one randomly-introduced single Pauli-error (bit-flip/phase-shift) is $0$. That is, if we were to sample a string from such a circuit that has a hidden Pauli-error somewhere within, and calculate the probability of obtaining that string with that circuit, the expected probability so calculated would be $1/2^n$. Thus, if we were to say that $\mathcal{F}_{XEB}=0.9$, I believe this means that 90% of the runs of the quantum circuit were totally error-free, while 10% had at least one error.

At one of Martinis' presentations on Google's plans for quantum supremacy, an audience member asked about a quantum sampler beating the uniform distribution; Aaronson commented that generating an output away from the uniform distribution is necessary to establish quantum supremacy, regardless of whether it's sufficient.