1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.