How many measurements are required to resolve data with a given fidelity?

Question

From Google's quantum supremacy paper

Having found the error rates of the individual gates and readout, we can model the fidelity of a quantum circuit as the product of the probabilities of error-free opera- tion of all gates and measurements. Our largest random quantum circuits have 53 qubits, 1113 single-qubit gates, 430 two-qubit gates, and a measurement on each qubit, for which we predict a total fidelity of 0.2%. This fidelity should be resolvable with a few million measurements, since the uncertainty on $F_{XEB}$ is $1/\sqrt{N_s}$ where $N_s$ is the number of samples. Our model assumes that entangling larger and larger systems does not introduce additional error sources beyond the errors we measure at the single- and two-qubit level — in the next section we will see how well this hypothesis holds.

Somehow they arrive at the "few million" measurements number from a fidelity of 0.2%. Is there a formula that allows them to calculate this?

Answer 1

I haven't read the paper thoroughly, so I'm entirely sure this is accurate, but here's a possibility:

Estimating the fidelity in this context (unitary evolution on pure states and projective measurements) amounts to computing a squared overlap $|\langle\psi|\phi\rangle|^2$ between pure states. In practice, one of them will be a measurement outcome, so estimating the fidelity amounts to estimating the probability of some specific measurement outcome.

The random variable associated to any outcome follows a binomial distribution (because you can either find or not find that outcome, with some probability). To estimate the associated probability you use the frequency: number of times you observe the outcome divided by total number of measurements. The variance associated to this estimator is $p(1-p)/N$ with $N$ the number of outcomes and $p$ the probability of getting the outcome at each shot. This $p$ is the fidelity to estimate, hence $p\simeq 2\times10^{-3}$.

It's not explicitly stated in the extract what "resolve the fidelity" means exactly, but let's assume we're satisfied with a 1% estimation error on it. That means we want the standard deviation in the order $\sigma\simeq 10^{-2} p$. Putting these together, we are looking for $N$ such that $$\sigma=\sqrt{\frac{p(1-p)}{N}} \implies N \simeq \frac{p(1-p)}{\sigma^2}\simeq \frac{p}{\sigma^2}\simeq \frac{1}{10^{-4} p}\simeq 5 \times 10^6,$$ which is compatible with the "a few millions" estimate.

---

Just to add a little bit of generality and precision to this: given any random variable $X$ (or more precisely, a sequence of IID random variables $X_1,...,X_N$), if you want to estimate its expectation value via the standard mean, $\overline X_N\equiv\frac{1}{N}\sum_{i=1}^N X_i$, the variance of this estimator will be $$\operatorname{Var}(\overline X_N)\equiv \mathbb{E}[(\overline X_N-\mathbb{E} X)^2]=\frac{\operatorname{Var}(X)}{N}.$$ To get an estimate on the expected errors, the simplest bound is given by Chebyshev: $$\operatorname{Prob}(|\overline X_N-\mathbb{E} X|\ge \epsilon) \le \frac{\operatorname{Var}(\overline X_N)}{\epsilon^2} = \frac{\operatorname{Var}(X)}{N \epsilon^2}.$$ It follows that if you want this error probability to be smaller than some $\delta$, you need $$N \ge \frac{\operatorname{Var}(X)}{\epsilon^2}\frac{1}{\delta}.$$ The $1/\delta$ scaling can also actually be improved to a much better $\log(2/\delta)$ scaling in cases where $X$ is bounded or sub-Gaussian (and you can thus use Hoeffding's inequality or other improved tail bounds).