Source-linked AI summary
Sample complexity of device-independently certified "quantum supremacy"
Dominik Hangleiter, Martin Kliesch, Jens Eisert, Christian Gogolin
TL;DR
Quantum sampling experiments need to certify that a device produces the intended distribution, not merely propose a classically hard sampling task. This paper analyzes classical, non-interactive certification and shows that flatness associated with approximate-sampling hardness can make it require exponentially many samples.
Problem
A key challenge in quantum-sampling demonstrations is certifying that a device samples close to its target distribution using a feasible number of device uses.
Source: §I · p. 1Method
The paper studies identity testing with classical samples and a full target-distribution description, and connects certification bounds to the flatness of randomly generated output distributions.
Source: §I · pp. 2–3Results
For the proposed sampling families, certification from classical samples and the target description is not sample-efficient; exponentially flat targets require exponentially many samples.
Source: §I · p. 3Takeaways & Limitations
The result rules out efficient classical, non-interactive, device-independent certification for these tasks and motivates alternative certification schemes or hardness results for more peaked distributions.
Source: §I · p. 3For boson sampling, the bound is exponentially likely for ν > 3, while for ν > 2 it holds only with polynomially high probability and misses a small set of instances.
Source: B. “Quantum supremacy” distributions… · p. 8
Abstract
from arXiv · showhide
Results on the hardness of approximate sampling are seen as important stepping stones towards a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, 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 non-interactive 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.
I. INTRODUCTION
Quantum sampling experiments need to establish both approximate hardness and that the device actually samples near its target. This introduction shows that the flatness associated with approximate-sampling hardness makes classical, non-interactive certification sample-inefficient, and surveys possible alternatives.
I. INTRODUCTION
- The proposed boson, universal random-circuit, IQP, and post-selected-universal 2-design sampling tasks cannot be efficiently certified from classical samples and the target distribution description.The lower bounds also cannot be circumvented by increasing the certifier’s classical computational power.Source: §I · pp. 1–2
- The proof uses second-moment bounds: they yield anti-concentration used in approximate-hardness arguments and also obstruct sample-efficient certification.The hardness connection requires average-case hardness of relative-error probability approximation to lift results to additive errors.Source: §I · p. 2, Figure 2 · p. 2
- For exponentially flat distributions, certification requires exponentially many samples; if the truncated distribution has polynomial support, sample-efficient certification is possible.The sample-complexity bounds depend on the truncated distribution after removing its largest entry and a tail of weight at most ε.Source: §I · pp. 2–3
- With high probability over the random unitary, the output distributions in the considered schemes are exponentially flat, linking their instance generation to the certification lower bounds.The paper identifies boson sampling, IQP, and random universal circuit sampling among the schemes considered.Source: §I · p. 3
- Alternative certification routes trade simplicity for assumptions or resources, including interaction, device assumptions, quantum capabilities, or trusted measurements.Cross-entropy and coarse-grained methods can be sample-efficient, but the cited discussion notes computational costs or limits against adversarial distributions.Source: §I · p. 3
- Flatness, rather than computational hardness alone, can prevent certification: even a uniform distribution on an exponentially large sample space is not sample-efficiently certifiable.The paper also notes a possible middle ground: reasonably, but not exponentially, flat distributions may be both classically intractable and efficiently certifiable.Source: §I · pp. 3–4
II. SETUP AND DEFINITIONS
The paper formalizes certification as testing whether samples from an unknown distribution are close to a specified target. The test is device-independent and receives the full target description, while the analysis focuses on sample complexity rather than computational cost.
II. SETUP AND DEFINITIONS
- A certification test receives a target distribution and i.i.d. samples from an unknown distribution, then accepts or rejects whether the sampler is sufficiently close to the target.The test’s completeness and soundness conditions apply to distributions over the sample space.Source: §II · p. 4
- A sample-efficient certification test uses O(poly(n, 1/ϵ)) samples, and sample-complexity lower bounds also lower-bound the time needed to read those samples.The setup uses standard asymptotic notation, [j] = {1, …, j}, base-2 logarithms, and ℓp norms.Source: §II · pp. 4–5
- Device-independent certification uses only classical samples and the target’s classical description, without assumptions about the sampler’s internal operation.The certifier may depend on all details of the target distribution and is allowed unlimited computational power.Source: §II · p. 5
- Certification here is identity testing against a fixed target, distinguishing it from state discrimination between two specified distributions.It must reject distributions at least ϵ-far in ℓ1 distance; this is needed because approximate-sampling hardness covers only distributions near the ideal target.Source: §II · p. 5
III. NO CERTIFICATION OF FLAT DISTRIBUTIONS
The section applies optimal fixed-target certification bounds to show how distributional flatness and support size constrain the required samples. It also extends the lower-bound reasoning to post-selected parts of a distribution, with a weight condition for a non-trivial bound.
III. NO CERTIFICATION OF FLAT DISTRIBUTIONS
- The sample complexity of optimal fixed-target certification is governed by an ℓ2/3 quasi-norm, which the paper bounds using min-entropy and support size.The section builds on Valiant and Valiant’s sample-optimal certification result.Source: §III · p. 5
- When H∞(P) = log(κ|En|), the required certification samples scale at least as the square root of the sample-space size.This is the stated implication for distributions whose min-entropy is essentially the logarithm of |En|.Source: §III · p. 5
- Distributions supported on polynomially many outcomes can be ϵ-certified from polynomially many samples.The paper derives this sufficient-sample conclusion from its support-size bound.Source: §III · p. 5
- A post-selected subspace yields a non-trivial certification lower bound only when its probability weight exceeds 2ϵ.The lower-bound argument applies to certifying the full distribution using a post-selected distribution on a subset of outcomes.Source: §III · p. 6
IV. “QUANTUM SUPREMACY” DISTRIBUTIONS CANNOT BE CERTIFIED
The paper applies fixed-target certification bounds to prominent quantum-sampling schemes and connects their certification difficulty to properties used in approximate-sampling hardness proofs. Its argument focuses on anti-concentration and second moments, while distinguishing anti-concentration alone from high min-entropy.
IV. “QUANTUM SUPREMACY” DISTRIBUTIONS CANNOT BE CERTIFIED
- Prominent sampling schemes, including boson sampling, cannot be certified from polynomially many classical samples and a description of the target distribution alone.Approximate-sampling hardness up to additive ℓ1 error also relies on anti-concentration.Source: §IV · p. 6
- The schemes are modeled by applying a randomly chosen unitary to a reference state and measuring the resulting state in the computational basis.Each output probability is PU(S) = |⟨S|U|S0⟩|2.Source: §IV · p. 6
- Anti-concentration concerns the random-unitary-induced output probabilities: for a fixed outcome, its probability is not too often much smaller than the uniform probability.The section notes that known anti-concentration proofs generally use Paley–Zygmund and second-moment bounds, with a stated exception.Source: §IV · p. 7
- Anti-concentration alone need not give high min-entropy for individual output distributions, since a scheme can retain anti-concentration while having min-entropy at most log(2).The paper gives a construction that halves all probabilities and adds their combined weight to one outcome.Source: §IV · p. 7
A. Second moments bound the min-entropy
The section uses second-moment bounds to establish high-probability min-entropy bounds for output distributions. This links exponentially small second moments to exponential certification sample lower bounds, while noting that anti-concentration by itself does not ensure high min-entropy.
A. Second moments bound the min-entropy
- Exponentially small second moments imply that, with high probability, the output distribution cannot be certified from polynomially many samples.The paper states that this same distributional property underlies approximate-sampling hardness up to additive total-variation error.Source: A. Second moments bound the min-entropy · p. 7
- A second-moment bound yields a high-probability lower bound on output min-entropy for random unitaries.The proof first bounds typical Rényi-2 entropy, then uses equivalence among Rényi entropies of order greater than one; the argument also applies to more general distribution families without scaling in n.Source: A. Second moments bound the min-entropy · p. 7
- Anti-concentration alone does not guarantee high min-entropy for most fixed unitaries, because it allows a few large probabilities.In prominent cases discussed here, anti-concentration derives from Rényi-2 entropy bounds.Source: A. Second moments bound the min-entropy · p. 7
B. “Quantum supremacy” distributions are flat
Boson sampling, IQP circuits, and universal random circuits have exponentially flat output distributions, leading to exponential lower bounds on the samples needed for certification. The boson-sampling bound depends on conditions used in its approximate-sampling hardness argument.
B. “Quantum supremacy” distributions are flat
- Certification of boson sampling, IQP circuits, and random universal circuits requires exponentially many samples in n under the stated conditions.The bounds are stated for boson sampling and the qubit-based schemes; the section connects these bounds to the schemes’ min-entropy.Source: B. “Quantum supremacy” distributions… · pp. 7–8
- For boson sampling, the lower bound assumes m ∈ Θ(n^ν) and conditions used to prove approximate-sampling hardness.The treatment states that its bound holds with exponentially high probability for ν > 3, but only with polynomially high probability for ν > 2, where it misses a small set of instances.Source: B. “Quantum supremacy” distributions… · p. 8
- The random-qubit-scheme result also applies to circuit families forming relative ˜ε-approximate spherical 2-designs, including several proposed supremacy families.The listed examples include Clifford circuits with magic-state inputs, diagonal unitaries, and conjugated Clifford circuits.Source: B. “Quantum supremacy” distributions… · p. 8
V. DETAILS ON RANDOM SAMPLING SCHEMES AND PROOFS OF THEOREMS 6 AND 7
This section presents details on the sampling schemes and proofs of Theorems 6 and 7.
V. DETAILS ON RANDOM SAMPLING SCHEMES AND PROOFS OF THEOREMS 6 AND 7
- The section describes details of distributions arising from boson sampling, IQP circuits, and universal random circuits, and presents proofs of the previously mentioned theorems.Source: §V · p. 8
A. IQP circuits
The section describes IQP circuits as uniformly random commuting-gate circuits, then relates their output-probability moments to a min-entropy bound.
A. IQP circuits
- An IQP instance is drawn uniformly from a family of commuting-gate circuits on n qubits, with gate angles chosen from a set A.The sample space is {0, 1}^n.Source: A. IQP circuits · p. 8
- Each complete-graph edge receives a weighted XX rotation, and each vertex receives a weighted X rotation.The weights are entries of W and come from A.Source: A. IQP circuits · p. 8
- A second-moment bound for IQP output probabilities implies a min-entropy bound holding with probability at least 1 − δ over the random circuit choice.The second-moment bound is attributed to Bremner et al. [16, Appendix F].Source: A. IQP circuits · p. 8
B. Universal random circuits and spherical 2-designs
The section connects random universal circuits and spherical 2-designs to bounds on output-distribution moments and min-entropy.
B. Universal random circuits and spherical 2-designs
- A random universal circuit is drawn from a depth-N family using randomly selected one- or two-qubit gates and target qubits.The section also notes a more specific prescription used by Boixo et al. [15].Source: B. Universal random circuits and… · p. 8
- Local random universal circuits form a relative ˜ε-approximate unitary 2-design at depth O(n^2) + O(n log 1/˜ε).The passage identifies this as provably true for the circuits investigated by Brandão, Harrow, and Horodecki [48].Source: B. Universal random circuits and… · p. 9
- For families whose output states form relative ˜ε-approximate spherical 2-designs, the second-moment bound yields a min-entropy bound with probability at least 1 − δ.The general family condition and the probability statement are given in adjacent passages.Source: B. Universal random circuits and… · p. 9
C. Boson sampling
Boson sampling is hard to certify efficiently from classical samples under the paper’s stated assumptions. The proof uses bounds on collision-free outcomes and output probabilities, with limitations depending on the scaling and post-selection weight.
C. Boson sampling
- The boson-sampling hardness argument relates output probabilities to permanents of Gaussian matrices, and requires a sufficiently fast scaling of m with n.The cited hardness result [14] requires m ∈ Ω(n^5 log(n)^2), while faster-than-quadratic scaling is necessary for its proof strategy.Source: C. Boson sampling · pp. 9–10
- Under the stated Lemma 8 assumption, the boson-sampling lower bounds rule out ε-certification with fewer than s_min samples in the theorem’s specified regimes.The results cover the full output distribution for ν > 3; for 2 < ν ≤ 3, the stated limitation concerns instances with very small collision-free weight.Source: C. Boson sampling · pp. 10–11
- For 2 < ν ≤ 3, the results leave open sample-efficient certification when collision-free outcomes have very small probability weight.The stated example is 1/poly(n) ≤ P_bs,U(Φ*_{m,n}) ≤ 2ε; the full-distribution bound removes this dependence only for ν > 3.Source: C. Boson sampling · pp. 10–11
- The proof combines a lower bound on collision-free-subspace weight with a min-entropy bound for the post-selected distribution.The collision-free weight is at least 1 − ζ with probability at least 1 − 2n^2/(mζ); the resulting bounds hold with probability at least 1 − δ − 2n^2/(ζm).Source: C. Boson sampling · pp. 10–11
- The second-moment bound used in Aaronson and Arkhipov’s hardness argument [14] also prohibits sample-efficient boson-sampling certification.The proof relies on that bound to establish high min-entropy for the post-selected distribution.Source: C. Boson sampling · pp. 10–11
VI. CONCLUSION
The conclusion states that high-min-entropy distributions cannot be certified with polynomially many samples, even with unlimited computation and a full target description. The appendix supplies details and proofs for earlier statements.
VI. CONCLUSION
- Distributions with high min-entropy cannot be certified from polynomially many samples, even when the certifier has unlimited computation and the full target description.The conclusion connects this obstruction to the second moments used in approximate-sampling hardness proofs.Source: §VI · p. 11
- The authors point to interaction, additional complexity-theoretic assumptions, assumptions about the sampling device, or limited quantum capacity as directions for certification schemes.These are presented as alternatives for more elaborate certification, not as evaluated solutions.Source: §VI · p. 11
APPENDIX
- The appendix restates earlier results and provides details and proofs to make the work self-contained.It includes proofs concerning min-entropy bounds and boson sampling.Source: APPENDIX · p. 12
Appendix A: Proofs for bounding the min-entropy
The appendices develop supporting probability and min-entropy bounds for boson sampling. They use entropy arguments and comparisons with Gaussian measures to control output probabilities.
Appendix A: Proofs for bounding the min-entropy
- Appendix A gives an alternative proof of Lemma 5 and establishes equivalence among the stated Rényi entropies.The alternative proof uses a union bound and Markov’s inequality.Source: Appendix A · p. 12
Appendix B: Probability weight of the collision-free subspace
- The paper recapitulates Aaronson and Arkhipov’s [14] bound on the probability weight of the collision-free subspace, presented as Lemma 10 citing Theorem 13.4 of [14].Source: Appendix B · p. 12