Sample Complexity of Device-Independently Certified “Quantum Supremacy”

Results on the hardness of approximate sampling are seen as important stepping stones toward a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, instantaneous quantum polynomial time (IQP) circuit sampling, and universal random circuit sampling. A key challenge for any such demonstration is to certify the correct implementation. For all these examples, and in fact for all sufficiently flat distributions, we show that any noninteractive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. Our proofs rely on the same property that is a central ingredient for the approximate hardness results, namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments.

Figure 1

We consider the problem of certifying probability distributions of the form $P_U(S)=|⟨S|U|S_0⟩{|}^2$ with an input state $|S_0⟩={|0⟩}^{\otimes n}$ and a unitary $U\sim {\mu }_n$ drawn from some measure ${\mu }_n$. Given $\epsilon >0$ and access to an arbitrary-precision description of the target distribution $P_U$, the test ${\mathcal{T}}_n$ treats the sampler as a black box and receives a sequence $S=(S_i{)}_{i=1}^s\sim Q^s$ of $s$ samples from an unknown distribution $Q$. Given $S$ the test is asked to output “Accept” if $Q=P_U$ and “Reject” if $\parallel Q-P_U{\parallel }_1>\epsilon$ with high probability.

Figure 2

A high level overview of the approximate sampling “quantum supremacy” proofs of Refs. [14, 15, 16, 18, 19, 20, 46] using Stockmeyer’s algorithm [23]. Invoking a worst-case hardness result for the calculation of the output probabilities of some circuit family, Stockmeyer’s algorithm can be used to prove the hardness of exact sampling. The key properties of the output probabilties that allow proving hardness of approximate sampling are that computing these probabilities is even hard on average and that the distribution anticoncentrates. We show that the same property that is essential to arrive at a hardness result for approximate sampling via anticoncentration also makes it hard to certify from classical samples and a complete description of the target distribution, even with unbounded computational power.

Figure 3

The vector $P_{-\epsilon }^{-\max }$ is obtained from $P$ by removing the largest element $p_0$ of $P$ as well as the smallest probabilities that accumulate to a total weight bounded by $\epsilon$.

Figure 4

Hardness and certification in terms of the flatness of $P_{-\epsilon }^{-\max }$ for the example of IQP circuits [16, 24] on $n$ qubits as obtained from the present result and the classical simulation algorithm of Schwarz and Van den Nest [54]. There, it is shown that a certain natural family of quantum circuits (including IQP circuits) can be efficiently simulated on a classical computer if the output distribution is essentially concentrated on a polynomial number of outcomes only. In this case, i.e., for $\parallel P_{-\epsilon }^{-\max }{\parallel }_0\lesssim \mathsf{\text{poly}}(n)$, the output distribution is also sample-efficiently certifiable as the bounds (2) and (3) show. Their classical simulation algorithm breaks down if the distribution is essentially spread out over more than polynomially many outcomes, and we even have a rigorous hardness argument by Bremner et al. [16] for exponentially flat distributions. Conversely, the number of samples required for certification becomes prohibitively large if the distribution is exponentially spread out, as measured by the ${\ell }_{2/3}$ norm (1). Nevertheless, as we illustrate here, there could be “room in the middle” where, for reasonably but not exponentially flat distributions, one may hope to find tasks that are both classically intractable and sample-efficiently certifiable in a device-independent fashion.