PaperlayerView exact revision on arXiv

Source-linked AI summary

Computational advantage of quantum random sampling

Dominik Hangleiter, Jens Eisert

arXiv:2206.04079v4quant-phcond-mat.quant-gascs.CC

TL;DR

Quantum random sampling is proposed as a test of quantum computational advantage, but its finite-size complexity, verification, and noise-related hardness require careful assessment. This review synthesizes the complexity-theoretic foundations, verification methods, experimental implementations, and classical simulations, finding strong evidence for exact-sampling hardness but substantially weaker evidence for approximate sampling.

  • Problem

    How quantum random sampling demonstrates computational advantage, remains classically hard at finite sizes and under noise, and can be verified remains an open research question.

    Source: §I · p. 4, F. Complexity of sampling in the… · p. 36, §VII · p. 58

  • Method

    The paper comprehensively reviews quantum random sampling’s complexity theory, verification methods, experimental implementations, classical simulations, and open challenges.

    Source: §I · p. 4

  • Results

    Exact-sampling hardness has very strong complexity-theoretic evidence, whereas approximate-sampling hardness is supported by substantially weaker evidence; robustness results reach 2−O(m) for universal random circuits.

    Source: §6 · pp. 34–35

  • Takeaways & Limitations

    Quantum random sampling offers a theoretically grounded route for studying quantum–classical computational separation, while approximate sampling and scalable noise resilience remain less established.

    Source: §6 · p. 35, F. Complexity of sampling in the… · p. 36

    No proof currently exists for additive or relative approximate average-case hardness.

    Source: §1 · p. 25

Abstract

from arXiv · show

Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently, first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. In this article, we comprehensively review the theoretical underpinning of quantum random sampling in terms of computational complexity and verifiability, as well as the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation. We discuss in detail open questions in the field and provide perspectives for the road ahead, including potential applications of quantum random sampling.

I. INTRODUCTION … C. Boson sampling

This section introduces quantum random sampling as a near-term test of quantum computational advantage and develops its complexity, verification, implementation, and simulation questions. It also describes Fock boson sampling, including its passive-linear-optical protocol, Fock-space formulation, and output outcomes.

I. INTRODUCTION

  • Quantum random sampling targets a computational analogue of a Bell test by seeking experimentally accessible quantum tasks that are hard to simulate classically and verifiable in practice.Current devices remain noisy and far from error correction, while factoring-based tests require roughly 20 million physical qubits for a 2048-bit RSA number; recent experiments have claimed classically intractable sampling with up to 60 qubits and photonic systems.Source: §I · p. 3

II. QUANTUM RANDOM SAMPLING SCHEMES

  • Quantum random sampling randomly selects a quantum computation and samples its Born-rule output distribution, with evidence for both small-scale classical difficulty and asymptotic intractability.The argument is intended to apply even to certain non-universal computations that may be comparatively easy to implement experimentally.Source: §I · p. 4, §II · p. 5

A. Universal circuit sampling

  • Universal circuit sampling uses a universal gate set to explore the available Hilbert space rapidly and was used in the first experimental demonstration of computational quantum advantage.Its circuits may have fixed or random architectures and can include additional non-random gates.Source: A. Universal circuit sampling · p. 5

B. IQP circuit sampling

  • IQP circuits are commuting circuits diagonal in the Hadamard basis, encompassing diagonal gate families, Ising-Hamiltonian evolutions, X-programs, and cluster-state constructions.They provide restricted random-computation models connected to measurement-based computation and, in some formulations, translation-invariant Hamiltonian implementations.Source: B. IQP circuit sampling · p. 6

C. Boson sampling

  • Boson sampling encodes the computational difficulty of matrix permanents in interference among photons traversing a Haar-random linear-optical network.The scheme injects n photons into the first n of m ∈ poly(n) modes, applies beam splitters and phase shifters, and measures all output modes in the photon-number basis; its physical motivation includes photon bunching observed in the Hong–Ou–Mandel experiment (Hong et al., 1987).Source: C. Boson sampling · p. 6
  • Fock boson sampling applies beam splitters and phase shifters to the input state |1n⟩, then measures in the Fock basis, producing outcomes S_i.This terminology distinguishes the Aaronson and Arkhipov (2013) protocol from its variants.Source: C. Boson sampling · p. 7
  • The possible outcomes are sequences (s_1, . . . , s_m) of non-negative integers whose entries sum to n.Source: C. Boson sampling · p. 7
  • Each outcome S ∈ Φ_m,n corresponds to a Fock state |S⟩, while |1n⟩ is the initial state and ϕ(U) represents the mode transformation in Fock space.Source: C. Boson sampling · p. 7

D. Gaussian boson sampling … 2. Quantum acceptance probabilities

This section situates quantum random sampling within computational complexity theory, comparing classical and quantum acceptance probabilities while surveying Gaussian boson sampling and related schemes. It also addresses the complexity of approximating associated sums, including the role of GapP and #P functions under Cook reductions.

D. Gaussian boson sampling

  • Gaussian boson sampling prepares single- or two-mode squeezed, or displaced squeezed, Gaussian states, producing outcomes over an unbounded-photon-number sample space.Its Gaussian states and measurements are experimentally easier than photon-number states and measurements, enabling recent large-scale experiments (Madsen et al., 2022; Zhong et al., 2021, 2020).Source: D. Gaussian boson sampling · p. 7

E. Further schemes

  • Beyond IQP and boson sampling, proposed random-sampling schemes include Fourier, fermion, magic-state, one-clean-qubit, product-unitary-conjugated Clifford, and distinguishable-particle models.Some proposals target easier certification or greater error tolerance (Fujii, 2016).Source: E. Further schemes · pp. 7–8

III. COMPUTATIONAL COMPLEXITY OF SIMULATING QUANTUM DEVICES

  • Computational complexity theory supplies asymptotic evidence for quantum advantage beyond the current limits of classical simulation algorithms.The review distinguishes concrete advantage, where supercomputers can no longer sample the target distribution, from asymptotic hardness based on the best possible classical algorithms.Source: §III · p. 8

A. Basics of computational complexity theory

  • Complexity theory classifies problems by resource requirements such as runtime and memory, with P covering polynomial-time deterministic computation and NP polynomial-time verification.The relevant separation is commonly framed against the conjecture P ≠ NP, while sampling tasks must also remain realizable and error-resilient on near-term quantum devices.Source: A. Basics of computational complexity… · pp. 8–9

B. Where to look for a quantum-classical separation?

  • Quantum advantage is sought by comparing quantum computation with randomized classical computation through the decision classes BPP and BQP.Quantum computations produce measurement outcomes according to the Born rule, and the distinction in acceptance probabilities provides a lever for separating computational power.Source: B. Where to look for a… · pp. 9–10

1. Classical acceptance probabilities

  • Classical randomized-circuit acceptance probabilities are fractions of accepting random inputs and therefore form a #P-complete counting problem.This contrasts with NP’s existential verification perspective: #P counts accepting inputs rather than merely deciding whether one exists.Source: §1 · p. 10

2. Quantum acceptance probabilities

  • Quantum-circuit acceptance probabilities are normalized squared gaps of #P functions, with signed path contributions capturing quantum interference and cancellation.Classical acceptance counts accepting paths, whereas quantum acceptance amplitudes use values in {+1, −1}; computing such gaps is complete for GapP.Source: §2 · p. 11
  • GapP and #P functions are equivalent under Cook reductions8, making the two classes computationally similar in this sense.Source: §2 · p. 11
  • Multiplicative-error approximation distinguishes GapP from #P despite their equivalence for exact computation.Source: §2 · p. 11
  • The notation means a machine in one class may query an oracle for arbitrary problems in another class at unit time cost.Source: §2 · p. 11

D. Approximating GapP · E. Approximating #P: Stockmeyer’s algorithm · 1. The polynomial hierarchy

The section distinguishes the approximability of GapP and #P, showing that relative-error information makes GapP approximation computationally hard while Stockmeyer’s algorithm enables small-multiplicative-error approximation for #P with an NP oracle. It then introduces the polynomial hierarchy as the complexity-theoretic framework underlying these results and quantum-supremacy claims.

D. Approximating GapP

  • Approximating a GapP function within any constant multiplicative error is GapP-hard because relative-error estimates reveal its sign and can recover its exact value to arbitrary relative accuracy.The proof uses shifted gaps, sign comparisons, and binary search.Source: D. Approximating GapP · p. 12
  • Squared output amplitudes evade the direct nonnegative-acceptance-probability obstacle because multiplicative approximations preserve zeros and normalized #P values have discrete spacing, yielding GapP-hardness for approximating |ngap(f)|².A shifted-function construction and iterative contraction estimate ngap(f) in O(n) steps when the relative error is below 1/2.Source: D. Approximating GapP · pp. 12–13
  • Approximating normalized quantum-circuit output probabilities is GapP-complete up to exponentially small additive error 1/2^{2n}.This follows by mapping GapP gaps to output amplitudes and applying Lemma 8 to their squared absolute values.Source: D. Approximating GapP · p. 13

E. Approximating #P: Stockmeyer’s algorithm

  • Because #P sums are nonnegative, importance sampling and related randomized schemes can approximate some #P-complete quantities, whereas GapP’s sign cancellations obstruct analogous relative-error sampling methods.The contrast motivates treating GapP and #P as fundamentally different approximation regimes.Source: E. Approximating #P: Stockmeyer’s… · p. 13
  • Stockmeyer’s algorithm approximately counts accepting paths of #P functions to small multiplicative error using an NP oracle, establishing a general approximation result that supports classical–quantum sampling separations.The algorithm lies in the third level of the polynomial hierarchy, which is more powerful than NP but less powerful than #P.Source: E. Approximating #P: Stockmeyer’s… · p. 13

1. The polynomial hierarchy

  • The polynomial hierarchy generalizes the P-versus-NP distinction through alternating existential and universal quantifiers, with PH defined as the union of its levels Σ_i.Each level adds an NP-oracle characterization, and the hierarchy is conjectured not to collapse.Source: §1 · p. 13

2. Stockmeyer’s approximate counting algorithm … 2. Fock boson sampling

The section develops Stockmeyer-based links between sampling and output-probability approximation, establishing conditional complexity separations and applying them to quantum models whose probabilities encode GapP-hard quantities such as permanents and Hafnians.

2. Stockmeyer’s approximate counting algorithm

  • Stockmeyer’s algorithm approximates exponentially large sums to inverse-polynomial multiplicative error within the third level of the polynomial hierarchy.Because BPP^NP ⊂ Σ3, approximate counting lies in Σ3, whereas exact #P computation encompasses the polynomial hierarchy by Toda’s theorem.Source: §2 · p. 14
  • Quantum acceptance probabilities require GapP-hard relative-error approximation, while classical nonnegative sums are approximable in Σ3, yielding a conditional exponential separation for sampling tasks.Neither approximation is expected to be efficiently realizable in BPP or BQP, but the complexity gap amplifies runtime differences between classical and quantum algorithms.Source: §2 · p. 14

A. Sampling versus approximating outcome probabilities

  • Stockmeyer connects sampling to probability approximation by estimating every output probability of a derandomizable sampler within a 1 − 1/poly(|y|)-multiplicative factor.The sampler is deterministic given an instance y and uniformly random input r, allowing its output probability to be represented as an acceptance probability.Source: A. Sampling versus approximating… · p. 15

B. Strongly simulating quantum computations

  • Output probabilities of universal quantum circuit families are GapP-hard to approximate when postselection promotes the model to postBQP, because postBQP = PP and P^#P ⊃ PH.Fujii and Morimae show that, when postA = postBQP, multiplicative approximation with error 1/2 < c < 1 can decide PP and GapP problems.Source: B. Strongly simulating quantum… · p. 15

1. IQP circuits

  • IQP circuits satisfy postIQP = postBQP, and their output amplitudes reduce to Ising partition functions or gaps of degree-3 Boolean polynomials.These restricted representations retain GapP-hardness under relative-error approximation, including the 1/4 + o(1) hardness of relevant partition-function quantities.Source: §1 · pp. 15–16

2. Fock boson sampling

  • Fock boson-sampling output probabilities are squared permanents of submatrices of the interferometer unitary, and approximating Perm(X)^2 remains GapP-hard for c ∈ [1/poly(n), 1].For collision-free outcomes, the relevant matrix is obtained by selecting rows and columns according to the output and input occupations.Source: §2 · p. 16, Figure 3 · p. 16
  • Gaussian boson-sampling probabilities are expressed through Hafnians of covariance-derived matrices, with repeated rows and columns determined by detected photon occupations.For product single-mode squeezed inputs, the covariance matrix and resulting probability expressions simplify, including uniform squeezing on selected modes.Source: §2 · pp. 16–17
  • Approximating Hafnians is at least as hard as approximating permanents and is therefore GapP-hard in the worst case.The permanent appears as a special case of the Hafnian, establishing the reduction in approximation hardness.Source: §2 · p. 17

C. Hardness argument … b. Showing TVD robustness.

The section argues that efficient classical sampling would collapse the polynomial hierarchy when circuit output probabilities are GapP-hard to approximate, extending this result from exact and multiplicative-error sampling toward realistic total-variation robustness. It motivates TVD as a natural error measure for classical and noisy quantum algorithms while identifying the increasing difficulty of proving hardness under additive errors.

C. Hardness argument

  • GapP-hard output-probability approximation combined with Stockmeyer counting implies that efficient exact sampling would collapse the polynomial hierarchy to its third level Σ3.The argument assumes the generalized P̸ = NP conjecture, under which the polynomial hierarchy is infinite, thereby ruling out efficient sampling.Source: C. Hardness argument · p. 17, §1 · p. 17

1. Exact sampling and worst-case hardness

  • Exact sampling hardness requires constant-relative-error hardness of output probabilities, but only worst-case hardness is needed because a single hard instance suffices.Thus, probabilities need not be hard to approximate for every circuit instance.Source: §1 · p. 18

2. Multiplicative-error sampling hardness

  • Multiplicative-error sampling remains hard when the sampler’s distribution is multiplicatively close to the ideal one, provided the resulting error cd preserves GapP-hardness.Stockmeyer’s algorithm combines the sampler’s error with its own approximation error, yielding an overall multiplicative error cd.Source: §2 · p. 18

3. From multiplicative to additive errors

  • Constant multiplicative-error sampling is as computationally demanding as exact sampling because it must control exponentially many probabilities, including values arbitrarily close to zero.This precision requirement may be possible for fault-tolerant quantum devices with system-size-scaled ultra-high precision but appears impractical.Source: §3 · p. 18
  • Total-variation distance is introduced as a natural statistical measure of distinguishability and a more plausible approximation notion than multiplicative error.It captures additive inaccuracies arising from finite-precision classical computation and algorithmic imperfections, although individual probability precision must still scale with system size.Source: §3 · p. 18, a. Why the total-variation distance? · p. 18

a. Why the total-variation distance?

  • For noisy quantum devices, state errors induce additive distribution errors, while trace distance upper-bounds TVD; however, constant local gate errors make the distance grow linearly with circuit size.TVD therefore requires local errors to decrease as circuits grow.Source: a. Why the total-variation distance? · p. 19
  • TVD also supports average-case hardness arguments for random circuits and is more compatible with the proof technique than KL divergence.The smallest meaningful nontrivial target is constant-TVD sampling, requiring component errors on the order of 1/m, though that scaling remains demanding.Source: a. Why the total-variation distance? · p. 19

b. Showing TVD robustness

  • Proving TVD robustness requires hardness for every distribution within an ϵ-neighborhood of the target, but this becomes impossible as ϵ approaches 1 because the uniform distribution is easy to sample.Unlike multiplicative constraints, additive error permits flexible redistribution of a total error budget across probabilities, increasing the proof burden.Source: b. Showing TVD robustness · pp. 19–20

3. Approximating … c. Hiding in boson sampling.

This section examines the conditions underlying additive-error sampling hardness, including average-case hardness, anticoncentration, and hiding, across random circuits and boson-sampling distributions. It also discusses a Gaussian boson-sampling construction encoding arbitrary matrix permanents and the remaining challenge of establishing approximate average-case hardness.

3. Approximating

  • Approximation hardness must hold for a large fraction of circuit instances and reasonably large probabilities, formalized through average-case complexity and anticoncentration rather than isolated hard outcomes.Inverse-polynomial additive errors are insufficient for GapP hardness; relative or exponentially small additive errors are needed for the polynomial-hierarchy argument.Source: §3 · p. 20

4. Additive-error sampling hardness

  • Additive-error robustness follows by combining total-variation control of the sampling distribution with Markov’s inequality and hiding to obtain accurate probability estimates on most instances.The proof starts from an efficient derandomizable sampler and uses Stockmeyer approximate counting within the third level Σ3 of the polynomial hierarchy.Source: §4 · pp. 20–21, Figure 5 · p. 21, a. Hiding problem instances · p. 22

a. Hiding problem instances

  • The hiding property randomizes which outcome is queried by appending uniformly random X gates while preserving the circuit-family distribution, preventing a sampler from concentrating its error on a known outcome.For universal Haar-random circuits, hiding follows from Haar-measure invariance under arbitrary unitaries, and the resulting Stockmeyer estimate has the stated bound on a (1−δ) fraction of instances.Source: a. Hiding problem instances · pp. 21–22

b. Approximate average-case hardness

  • Efficient classical sampling within constant total-variation error would collapse the polynomial hierarchy when output probabilities are approximately average-case hard and the circuit family has the hiding property.The argument uses Stockmeyer’s algorithm to approximate GapP-hard probabilities in the third level of the polynomial hierarchy.Source: b. Approximate average-case hardness · pp. 22–23, Figure 6 · p. 23

c. Hiding in boson sampling

  • In collision-free boson sampling, hiding is supported when m ∈Ω(n^2) enables constant-weight postselection and m ∈Ω(n^5 log(n)^2) makes Haar-unitary submatrices approximately complex Gaussian.Aaronson and Arkhipov (2013) use the resulting approximately unstructured submatrices to hide Gauss-random instances; analogous Gaussian-boson-sampling hiding is proven in two regimes, with numerical evidence in the intermediate regime.Source: c. Hiding in boson sampling · pp. 23–24

c. Hiding in boson sampling.

  • A bespoke bipartite Gaussian boson-sampling scheme encodes the permanent of an arbitrary matrix without requiring m ∈ Ω(poly(n)).The construction uses 2m modes, two-mode squeezed inputs, a bipartite transformation U ⊗ V, and Fock-basis measurements; choosing r, U, and V via a singular-value decomposition programs an arbitrary matrix satisfying the hiding property by definition.Source: c. Hiding in boson sampling · p. 24
  • Proving approximate average-case hardness remains the central open theoretical problem in quantum random sampling.The passage distinguishes this problem from the construction of hiding instances and notes that substantial work has instead assembled evidence for approximate average-case hardness.Source: c. Hiding in boson sampling · p. 24
  • The following section reviews evidence bearing on the truth of approximate average-case hardness.Source: c. Hiding in boson sampling · p. 24

D. Approximate average-case hardness … b. Anticoncentration via computing the collision probability.

The section reduces a complicated sampling error bound to additive or relative average-case hardness, then studies anticoncentration through second moments and collision probabilities. It presents design-based and statistical-mechanics routes, while noting that approximate average-case hardness remains unproved and anticoncentration is not sufficient for sampling hardness.

1. Reduction to additive or multiplicative average-case hardness

  • The error bound reduces to exponentially small additive error when p0(C) < α/2n and to relative error when p0(C) > α/2n.The corresponding bounds are (2ϵ/δ + α + o(1))/2n for additive error and 2ϵ/(αδ) + o(1) for relative error.Source: §1 · p. 24
  • The reduction yields additive average-case hardness O(2−n) on any γ fraction or relative-error hardness 1/4 on any γ(1 −γ/2) fraction, conditional on anticoncentration.For the relative-error case, α = 1/c, ϵ = γ(α)/4, and δ = γ(α)/2 give a (c/2+o(1))-relative approximation with probability at least γ(1−γ/2).Source: §1 · p. 25
  • Approximate average-case hardness remains unproved, but it is more plausible for GapP functions because differences of exponentially large #P counts can be much smaller than either count.For #P functions, multiplicative errors can remain exponentially large, making approximate average-case hardness less expected; for GapP functions, cancellation supports the conjecture.Source: §1 · p. 25
  • Anticoncentration supports additive hardness by preventing almost all probabilities from being inverse-exponentially small, but it is neither necessary for sampling hardness nor sufficient by itself.For Fock boson sampling, second moments give anticoncentration probability 1/(n + 1), while anticoncentration remains elusive for some boson-sampling protocols.Source: §1 · p. 25, c. Further proofs of anticoncentration · p. 28

a. Anticoncentration

  • Anticoncentration bounds the probability of unusually small outputs through second moments, with the normalized second moment 2n E[p0(C)2] identified as the average collision probability.Bounding this collision probability as O(2−n) suffices to establish anticoncentration.Source: §1 · p. 25
  • Relative ϵ-approximate 2-designs anticoncentrate, and universal random-circuit families can approach this property through unitary designs.Lemma 19 establishes anticoncentration for 2-designs; Brandão et al. (2016) prove approximate unitary designs for linear-chain random circuits using O(poly(k) · n(n + log(1/ϵ))) gates.Source: a. Anticoncentration · p. 26

b. Anticoncentration via computing the collision probability.

  • 5n log(n)/6 gates are necessary and sufficient up to subleading corrections for exponentially small collision probability under arbitrary connectivity, while nearest-neighbor circuits anticoncentrate at logarithmic depth.The nearest-neighbor result is tight up to an O(n log(n)) circuit-size lower bound for arbitrary geometries.Source: b. Anticoncentration via computing the… · p. 27
  • Haar-random two-qubit circuits map their second-moment calculation to a statistical-mechanics partition function over local permutation spins, enabling collision-probability bounds by domain-wall counting.For k = 2, the plaquette model permits simple domain-wall counting arguments; IQP circuits similarly allow direct collision-probability calculations from Ising partition functions.Source: b. Anticoncentration via computing the… · pp. 27–28, c. Further proofs of anticoncentration · p. 28

c. Further proofs of anticoncentration. … b. Distributions over infinite fields: the case of F = C.

The section develops average-case hardness through random self-reducibility and polynomial interpolation, while showing that anticoncentration and infinite-field finite-precision issues remain major obstacles. Error-correction improves finite-field success requirements, but complex-valued distributions require approximate interpolation methods that cannot use exact decoding.

c. Further proofs of anticoncentration.

  • Tao and Vu’s Bernoulli permanent bound does not reach the inverse-polynomial failure probability needed for anticoncentration, and higher-moment approaches have not yet resolved the problem.Nezami (2021) characterizes Gaussian-permanent moments but concludes that a closed formula for all moments may be necessary; Gaussian boson sampling is more elusive because of the COE distribution.Source: c. Further proofs of anticoncentration · p. 28

3. Average-case hardness: An overview

  • Average-case hardness remains elusive because it depends strongly on the instance distribution, and quantum random sampling still lacks an additive- or relative-error hardness proof.Random self-reducibility provides a worst-to-average-case route, but the central quantum-sampling hardness conjecture remains open.Source: §3 · pp. 28–29

4. Random self-reducibility of the permanent

  • An algorithm correct on at least 1 − 1/3n of uniformly random finite-field instances can solve arbitrary permanent instances via degree-n polynomial interpolation.The construction makes E(t) uniformly random for nonzero t, queries n+1 points, and reconstructs q(0) = Perm(A).Source: §4 · p. 29

a. Improving the success probability.

  • Correctness requirements fall to 1/2 + 1/poly(n) using Reed-Solomon error correction and interpolation, while list decoding reaches inverse-polynomial fractions over sufficiently large finite fields.Berlekamp-Welch tolerates an error rate arbitrarily close to one half, and Gemmell and Sudan’s interpolation path yields the 1/2 + 1/poly(n) threshold.Source: a. Improving the success probability · pp. 29–30

b. Distributions over infinite fields: the case of F = C.

  • For complex-valued instances, no uniform measure exists and finite-precision evaluations introduce errors of order 2^-poly(n), complicating both randomization and exact interpolation.Small interpolation parameters keep the induced distribution close in total variation, but numerical values cannot be treated as exact field elements.Source: b. Distributions over infinite fields:… · pp. 30–31
  • Stable interpolation and extrapolation recover the complex-field argument despite finite precision, but they cannot use Berlekamp-Welch because its error-correction guarantee requires exact evaluations.Interpolation points are chosen in a small interval around zero so their distributions remain close to the original Gaussian distribution.Source: Figure 7 · p. 30, c. Robustness to finite-precision errors · p. 31, b. Distributions over infinite fields:… · p. 31

c. Robustness to finite-precision errors. · 5. Average-case hardness of quantum output probabilities · 6. Discussion

Stable interpolation and extrapolation control finite-precision errors, while several interpolation strategies establish increasingly strong but still insufficient average-case hardness results for quantum output probabilities. Exact-sampling hardness has stronger complexity-theoretic support than approximate-sampling hardness, which remains limited by robustness, circuit-depth, and fault-tolerance barriers.

c. Robustness to finite-precision errors.

  • Stable interpolation and extrapolation bound finite-precision errors by applying Rakhmanov’s theorem between evaluation points and Paturi’s lemma when extrapolating, tolerating input errors of 2^-O(n^c).The same argument applies to Gaussian boson sampling because squared Hafnians are degree-4n polynomials in the Gaussian matrix entries.Source: c. Robustness to finite-precision errors · p. 31

5. Average-case hardness of quantum output probabilities

  • Local Taylor truncation enables worst-to-average-case reasoning only for approximate values associated with non-unitary truncated circuits, although the truncated and non-truncated additive-hardness conjectures are equivalent.Bouland et al. (2022) improve the tolerated failure fraction to 3/4+1/poly(n) using an NP-oracle interpolation procedure while retaining 2^-O(m log m) error scaling.Source: §5 · pp. 32–33
  • Cayley-function interpolation remains within the unitary group, with total-variation distance O(mϵ) at t = 1 − ϵ and robustness 2^-O(m^2), improved to 2^-O(m log m) on a 1 − 1/O(m) fraction of instances.The 2^-O(m^2) bound holds on a 1 − 1/poly(n) fraction of instances; the improved bound uses Lagrange polynomials.Source: §5 · p. 33
  • Global Taylor truncation yields degree-O(m/log m) polynomials with robustness 2^-O(m) for Haar-random 2-qubit circuits and 2^-O(n) for IQP circuits, while interpolation-point choices can raise success probability to a constant without an NP oracle.Krovi (2022) reduces the gap to the required 2^-n robustness to constants in the exponent.Source: §5 · p. 33
  • Worst-to-average-case reductions require continuous unitary subgroups and therefore do not directly apply to discrete gate sets, although a specialized exact reduction exists for a restricted IQP family but not for output probabilities.Dalzell et al. (2020, Thm. 6) use sign information in gaps of degree-3 Boolean polynomials, which output probabilities discard.Source: §5 · p. 34

6. Discussion

  • Polynomial interpolation faces a fundamental robustness barrier because small errors at nearby points can become exponentially larger at the target, while low-depth random circuits can be efficiently simulable on average and postselected fault tolerance protects only a 2^-Ω(n) fraction of probabilities.These limitations imply that any approximate-hardness technique must depend on circuit depth, and postselection conflicts with average-case hardness.Source: §6 · pp. 34–35
  • Universal random circuits achieve robustness 2^-O(m) and IQP circuits 2^-O(n), while Fock boson sampling reaches e^-(c+4)n log n-O(n), within constant factors in the exponent of the required e^-n log n scaling.Krovi (2022) removed logarithmic factors from earlier universal-circuit bounds, and the Fock boson-sampling result applies for m = O(n^c) modes.Source: §6 · p. 34
  • Exact quantum random sampling has strong hardness evidence from conjectured polynomial-hierarchy non-collapse, whereas approximate-sampling hardness relies on a weaker conjecture whose failure would have limited complexity-theoretic consequences.The approximate average-case hardness conjecture may nevertheless be provable despite significant remaining hurdles.Source: §6 · p. 35

E. Fine-grained results … B. Sample-efficient classical verification via cross-entropy benchmarking

The paper develops fine-grained runtime lower bounds for classical simulation, analyzes noise robustness and fault-tolerant sampling, and reviews verification methods from infeasible sample testing to cross-entropy benchmarking. These results clarify when quantum random sampling can remain classically difficult and how its implementations can be assessed.

E. Fine-grained results

  • The conjecture yields a classical sampling-time lower bound t(n) ≥ 2an−1, with best-known a < 0.9965; IQP sampling on roughly 200 qubits and 10^6 gates could require at least a century classically.Source: E. Fine-grained results · p. 36
  • Monotone simulators have an explicit lower bound of ˜O(2^(n−3)) runtime, while the exponential-time hypothesis yields a 2^(n−o(n)) lower bound for strong circuit simulation.The monotone framework captures most tensor-network methods but excludes simulators exploiting specific gate values, such as T-gate counts.Source: E. Fine-grained results · p. 36

F. Complexity of sampling in the presence of noise

  • Constant local errors remain compatible with sampling hardness, but scalable constant-total-variation accuracy is difficult because local gate errors must decrease inversely with circuit size.The analysis distinguishes direct noisy-distribution complexity from fault-tolerant encodings designed to tolerate constant local errors.Source: F. Complexity of sampling in the… · p. 36

1. Noisy output distributions

  • For anticoncentrated random circuits, sampling the white-noise distribution with inverse-polynomial fidelity is as hard as sampling the ideal distribution, while the required local error rate remains Θ(1/n).The result applies to circuits of size O(n log(n)), the minimal size required for anticoncentration in this analysis.Source: §1 · p. 37

2. Fault-tolerant random sampling

  • Fault-tolerant random sampling remains worst-case hard below the encoding threshold because postselecting no-error syndromes recovers the ideal distribution whenever the postselection probability is nonzero.Measurement-based encodings can also support efficient verification, although the plausibility of the required average-case hardness assumption is unclear.Source: §2 · p. 37

V. VERIFICATION

  • Verification is necessary but difficult because accurate sampling implementations and their output probabilities cannot be efficiently simulated, motivating inefficient, efficient, state-access, and interactive protocols.The verification setting may vary by interaction, available samples, and whether direct access to the output state is permitted.Source: §V · pp. 37–38

A. Hardness of verification from classical samples

  • Quantum random sampling typically requires Ω(2^(n/4+O(δ))) samples for certification with probability 1−δ, because its output distributions are exponentially flat.Uniform-distribution testing requires O(|Ω|) samples, and the optimal identity test is impractical because its constants are too large.Source: A. Hardness of verification from… · p. 38

B. Sample-efficient classical verification via cross-entropy benchmarking

  • Cross-entropy measures estimate similarity between noisy and ideal distributions using heavy outcomes, but exponential sample efficiency is lost for exponentially small scores and computing ideal probabilities is inefficient.These tests therefore weaken full total-variation verification to obtain sample efficiency, with Porter–Thomas behavior motivating their analysis for random circuits.Source: B. Sample-efficient classical… · pp. 38–39

1. Heavy-outcome generation … 2. Cross-entropy difference

The section develops HOG and its fine-grained variants as benchmarks for correlated quantum sampling, then examines cross-entropy difference as a distributional measure with useful interpolation and conditional total-variation guarantees. It also emphasizes computational and statistical limitations, including weak hardness evidence and failure under some noise models.

1. Heavy-outcome generation

  • HOG requires at least 2/3 of distinct output strings to have probabilities above the circuit distribution’s median, and nonzero HOG fidelity is equivalent to solving this task.The task is introduced by Aaronson and Chen (2017).Source: §1 · p. 39
  • For Porter–Thomas probabilities, ideal sampling gives FHOG(PC, PC) = 1, while high HOG fidelity generally indicates closeness to the target in total variation only for specified mixture models.HOG fidelity can also be maximized by distributions far from PC, so it does not generally quantify total-variation distance.Source: §1 · p. 40

a. Computational hardness of HOG

  • HOG hardness follows from the conjectured classical intractability of deciding whether |⟨0|C|0⟩|2 exceeds med[PC], but the evidence for QUATH and HOG intractability remains extremely weak.Aaronson and Chen (2017) reduce HOG to QUATH, whereas efficient quantum sampling solves HOG with failure probability exp(−Ω(k)) under sufficient heavy-outcome weight.Source: a. Computational hardness of HOG · p. 40

b. Fine-graining HOG: Binned outcome generation

2. Cross-entropy difference

  • Cross-entropy difference measures correlations between Q and PC and distinguishes the uniform distribution from ideal sampling, attaining 1 for uniform Q and 0 for Q = PC.Under the Porter–Thomas assumption, this produces linear interpolation for distributions Qλ and extends to noise uncorrelated with PC.Source: §2 · pp. 41–42
  • If H(Q) ≥ H(PC) and dCE(Q, PC) ≤ ε, cross-entropy difference bounds total-variation distance, but the entropy condition requires exponentially many samples to verify.Bouland et al. (2019) also construct distributions that score well on cross-entropy difference while remaining far from PC.Source: §2 · p. 42
  • Cross-entropy difference can be estimated from iid. samples using Hoeffding’s inequality under Porter–Thomas probabilities, with accuracy controlled by the sample count and failure probability.The analysis relies on concentration of the logarithms of ideal probabilities for sufficiently random, large circuits.Source: §2 · p. 42

3. Linear cross-entropy benchmarking (XEB) fidelity … c. Single-instance verification.

XEB fidelity unifies randomized benchmarking with single-instance verification of quantum random sampling, while its interpretation depends on typicality and assumptions about noise. The section also develops its sampling complexity, benchmarking estimators, and the computational hardness of achieving very small XEB scores.

3. Linear cross-entropy benchmarking (XEB) fidelity

  • XEB fidelity unifies averaged randomized benchmarking with single-instance verification of quantum random sampling through a typicality argument based on Levy’s lemma.It uses f_XEB(x) = 2^n x − 1 up to rescaling and shifting, and applies both to few-qubit gates and large random circuits.Source: §3 · p. 42
  • XEB is intrinsically an average-case measure, so single-instance verification is justified only when random circuit instances are typical.For circuit families forming a spherical 2-design, the average XEB fidelity provides a meaningful quantum-advantage measure between ideal and uniform output distributions.Source: §3 · pp. 42–43

a. Sample complexity of estimating the XEB fidelity.

  • O(1) variance remains possible when only third circuit moments are close to Haar-random and the noise is gate-independent, supporting efficient estimation of average XEB fidelity.The section distinguishes estimation from many samples for Haar-random unitaries and estimation across many random circuits with many samples per circuit.Source: a. Sample complexity of estimating the… · p. 43

b. Benchmarking via XEB fidelity

  • XEB benchmarking estimates the per-cycle depolarization fidelity pc by fitting the circuit-averaged XEB fidelity across increasing circuit depths.The procedure treats XEB fidelity as a proxy for average quantum-state fidelity and extracts pc from an exponential fit, requiring noise sufficiently uncorrelated with the circuit.Source: b. Benchmarking via XEB fidelity · p. 43
  • e^−λd ≤ E F_d ≤ e^−λd(1 + Kλ) for d ≪ 2^n, showing exponential average-fidelity decay for layered non-Clifford circuits with Pauli noise.Liu et al. (2021c) establish this bound up to first order in λ, where λ is the total error.Source: b. Benchmarking via XEB fidelity · p. 44
  • The unbiased XEB estimator agrees well with fidelity across correlated noise models, with variance O(1/ℓ + λ^2(EF)^2), while the maximum-likelihood estimator has lower bias and variance than linear XEB.The linear XEB estimator converges to the maximum-likelihood estimator when the depolarization fidelity satisfies ϵ_d ≪ 1.Source: b. Benchmarking via XEB fidelity · p. 44

c. Single-instance verification.

  • For large n, Levy’s lemma predicts O(1/2^n) fluctuations, so fidelity concentrates around its random-circuit expectation and XEB estimates single-instance fidelity up to that deviation.This conclusion requires the noise component to be uncorrelated with the ideal circuit output; validating that assumption is central to the theoretical and experimental analyses of Arute et al. (2019).Source: c. Single-instance verification · p. 44
  • Achieving an exponentially small XEB score b/2^n for constant b > 1 is expected to be computationally hard because XHOG refines HOG and reduces to XQUATH.XHOG requires outcomes to be produced according to their actual probabilities, paralleling the HOG-to-QUATH hardness argument of Aaronson and Chen (2017).Source: d. Hardness of achieving a nontrivial… · p. 44

d. Hardness of achieving a nontrivial XEB fidelity. … c. Fidelity witnesses for quantum optical states.

XEB fidelity is both computationally hard to achieve nontrivially and a proxy for quantum fidelity, but adversarial spoofing exposes limitations that motivate efficient state-level verification. Fidelity witnesses enable restricted-measurement verification across computational, weighted-graph, and optical states, although their bounds can become loose.

d. Hardness of achieving a nontrivial XEB fidelity.

e. Spoofing the linear XEB fidelity.

  • XEB can overestimate quantum fidelity in adversarial settings, whereas under homogeneous independent noise agreement requires nϵf(c) ≪1 and fails for strong noise (Gao et al., 2021).Its distinct scaling for composed systems, sensitivity to correlated errors, and amplifiable distribution correlations enable spoofing; cross-entropy difference remains a potential alternative.Source: e. Spoofing the linear XEB fidelity · pp. 45–46
  • Gao et al. (2021) achieve XEB fidelity 1.85 · 10^-4 in 0.6s on one GPU versus Google’s 2.24 · 10^-3, refuting XQUATH for 1D sublinear-depth circuits.Their subsystem-product approximation removes inter-subsystem entangling gates; the score scales as e^-O(d), while a variant matches XQUATH’s probability-estimation statement.Source: e. Spoofing the linear XEB fidelity · p. 45

C. Efficient quantum verification

  • Quantum verification exploits access to the prepared state to potentially verify total-variation distance efficiently using restricted, locally characterizable capacities such as single-qubit measurements.These assumptions are experimentally justified because single-qubit fidelities typically exceed entangling-gate fidelities and can be characterized with tomography or device-independent tools.Source: C. Efficient quantum verification · p. 46
  • Fidelity witnesses lower-bound target-state fidelity through a measured observable, certifying high fidelity on one side of a hyperplane while providing no positive conclusion on the other.They trade information against measurement complexity and assumptions, and fidelity bounds total-variation distance via the Fuchs-van de Graaf inequality.Source: C. Efficient quantum verification · p. 46, Figure 10 · p. 47

a. Fidelity witnessing

  • Measurement-based quantum-random-sampling states can be verified with trusted single-qubit measurements because stabilizer states are gapped ground states of local commuting Hamiltonians.The construction uses a parent-Hamiltonian witness with stabilizer gap 2; arbitrary computations can be embedded using the Feynman-Kitaev history-state construction.Source: a. Fidelity witnessing · p. 47

b. Fidelity witnesses for weighted graph states.

  • Weighted graph-state and optical protocols extend fidelity witnessing: arbitrary weighted IQP graph states admit efficient estimation, while boson-sampling witnesses use heterodyne outcomes to classically invert linear-optical evolution (Chabaud et al. (2021b)).The weighted-graph-state protocols were developed by Hayashi and Takeuchi (2019); Morimae et al. (2019); and Zhu and Hayashi (2019).Source: b. Fidelity witnesses for weighted… · pp. 47–48, c. Fidelity witnesses for quantum… · p. 48

c. Fidelity witnesses for quantum optical states.

  • Optical fidelity witnesses reduce verification to single-mode fidelities and tolerate noise, but estimating W = 1 −Pk wi requires O(k^3/ϵ^2) samples and can become loose away from the target.Gaussian-state witnesses use efficiently transformed number operators measured through homodyne observables; direct fidelity estimation is therefore motivated for more detailed information.Source: c. Fidelity witnesses for quantum… · p. 48

2. Fidelity estimation … 2. Cryptographic tests

The section reviews fidelity estimation, efficient classical verification, state-discrimination tests, and cryptographic tests for quantum sampling. These approaches trade sample efficiency, computational efficiency, experimental assumptions, distributional information, and cryptographic assumptions in different ways.

2. Fidelity estimation

  • Direct fidelity estimation achieves constant quantum sample complexity, estimating fidelity with error ϵ using O(1/ϵ^2) samples.It samples weighted normal operators and measures them on the prepared state; efficient implementation requires efficiently sampleable, typically local product observables.Source: §2 · pp. 48–49
  • Direct fidelity estimation applies efficiently to states locally equivalent to stabilizer states, including measurement-based architectures, but not universal random circuits (Hangleiter, 2021).Its quantum sample complexity drops from O(n^3) to O(1), while measurement-setting complexity rises from O(1) to O(1/ϵ^2); Pauli-restricted verification can scale exponentially with non-Clifford gates (Leone et al., 2022).Source: §2 · p. 49

D. Efficient classical verification

  • Efficient classical verification methods use assumptions other than experimental trust or provide less information than full distribution certification.The broader verification landscape contrasts sample-efficient but exponentially costly classical methods with fully efficient quantum tools that require trusted measurements and multiple local bases.Source: D. Efficient classical verification · p. 49

1. State discrimination

  • State discrimination tests compare experimental samples against uniform, noisy, classically simulable, or thermal alternatives rather than certifying the full target distribution.Boson-sampling tests include row-norm estimators, Bayesian likelihood ratios, and low-order marginal probabilities; state discrimination remains especially persuasive because XEB fidelity may not be meaningful (Aaronson and Arkhipov, 2014; Zhong et al., 2021, 2020).Source: §1 · pp. 49–50
  • For universal random circuits, efficient state discrimination would imply sample-efficient total-variation verification in a multi-round scheme, providing evidence against such tests (Stilck França and Garcia-Patron, 2022).This conclusion follows from the difficulty expected for HOG-like discrimination against uniform distributions.Source: §1 · p. 50

2. Cryptographic tests

  • Cryptographic tests can separate quantum from classical strategies through a hidden bias, but their guarantees depend on unproven security and hardness assumptions.Shepherd and Bremner’s protocol does not certify the target output distribution; it certifies only that the device can perform a task presumed classically infeasible under assumptions.Source: §2 · p. 51
  • cos^2(π/8) ≈0.854 is the quantum bias versus 3/4 for the stated classical strategy in the Shepherd–Bremner construction (2009).The construction uses quadratic residue codes, conjectures that recovering the obfuscated generator is NP-complete, and does not establish that 3/4 is optimal.Source: §2 · p. 51
  • An empirically observed O(n^3)-runtime classical strategy extracts the secret vector with probability arbitrarily close to one, undermining the original Shepherd–Bremner test (Kahanamoku-Meyer, 2019).Related trapdoor claw-free-function protocols exploit quantum superposition and have been simplified and reduced in depth, although sampling verification can still have unfeasible overhead.Source: §2 · pp. 51–52

E. Further approaches to the verification of quantum samplers … B. Photonic implementations

This section surveys experimental implementations of quantum random sampling, focusing on advances in superconducting and photonic platforms alongside the challenges and methods of verification. It also covers developments in Gaussian boson sampling, scalable optical components, and statistical approaches to assessing experimental outputs.

E. Further approaches to the verification of quantum samplers

  • Most verification protocols assume iid. state preparations, but de-Finetti arguments extend verification to non-iid. preparations, including graph and bosonic states.Weaker alternatives build trust through structured computations or efficiently computable correlations, while blind verified computation uses trap qubits and accurate single-qubit preparation.Source: E. Further approaches to the… · p. 52

A. Universal circuit sampling with superconducting circuits

3. Verifying the sampling task

  • Linear XEB benchmarks component performance and typical large-scale states without computing every outcome, while verification circuits show patch, elided, and full simulations yield roughly the same XEB fidelity.The XEB fidelity is not a rigorous certificate; supporting tests found Porter–Thomas-distributed probabilities and rejected uniform sampling, while proxy methods reduce otherwise intractable probability calculations.Source: a. Benchmarking of single-qubit gates · p. 53, §3 · pp. 54–55
  • (2.24 ± 0.21) × 10^-3 XEB fidelity was obtained for 53 qubits at depth 20, exceeding 10^-3 with 5σ significance; classical sampling was estimated at 10 000 years versus 200 s quantumly.Patch and elided simulations remained close to the error model, while verification required millions of years; these claims have since been challenged by improved classical simulations.Source: §3 · pp. 54–55, Figure 11 · p. 55

4. Follow-up work

  • Wu et al. (2021) achieved 0.0662% XEB fidelity, while Zhu et al. (2022) reached 0.0758% for 60-qubit, 22-cycle circuits and (3.66 ± 0.345) · 10^-4 for 60-qubit, 24-cycle circuits.Zhu et al. (2022) also achieved 2.26% average readout fidelity and estimated roughly four orders of magnitude more resources than Arute et al. (2019).Source: §4 · pp. 55–56

B. Photonic implementations

  • Photonic boson sampling advanced from small integrated experiments limited by multiphoton emission and distinguishability to Wang et al. (2019)’s 20-photon, 60-mode Fock sampler.Improved solid-state sources and ultralow-loss circuits enabled this scaling, while postselection and classically computable outcome probabilities constrained earlier experiments.Source: B. Photonic implementations · p. 56
  • n = 113 photon events were detected across m = 144 optical modes using programmable input phases and a high-brightness, scalable quantum light source.The source uses stimulated emission of squeezed photons to achieve near-unity purity and high efficiency.Source: B. Photonic implementations · p. 57
  • Zhong et al. (2021) used low-order mode marginals and Bayesian likelihood-ratio, or cross-entropy-ratio, estimators to distinguish the experiment from distinguishable-photon and thermal-state distributions.Quantum-measurement tests can verify sampler functioning in principle, and observed threshold-detector click-number distributions agreed with theory when some decoherence effects were included.Source: B. Photonic implementations · p. 57
  • Madsen et al. (2022) implemented time-multiplexed Gaussian boson sampling with m = 216 squeezed inputs, three-dimensional connectivity, photon-number-resolving detectors, and an average of 125 detected photons.Lower-depth transformations reduce loss and enable larger systems, while numerical evidence indicates that low-depth, high-dimensional transformations remain practically hard to simulate; the experiment used TVD, cross-entropy, Bayesian, and cumulant benchmarks across photon-number regimes.Source: B. Photonic implementations · p. 57
  • Thekkadath et al. (2022) implemented a 15-mode displaced-input Gaussian boson-sampling variant, while Clements et al. (2018) demonstrated an imperfect-optics boson-sampling approach to approximating vibronic spectroscopy.Input-state displacements shift squeezed states in phase space and are useful for anticipated Gaussian-boson-sampling applications.Source: B. Photonic implementations · p. 57

C. Further implementations of quantum random sampling … b. Hybrid algorithms.

This section surveys alternative quantum-random-sampling platforms and methods for their classical simulation, including measurement-based verification, tensor-network approaches, and hybrid methods. It examines how simulation success depends on task definitions, circuit structure, contraction strategies, approximation fidelity, and explicit reproducibility criteria.

C. Further implementations of quantum random sampling

  • Measurement-based sampling reduces device control through fixed entangling gates and one layer of random Z rotations, while recycling trades circuit depth for available qubits.Its single-qubit measurements can efficiently witness quantum fidelity, avoiding important caveats of XEB fidelity; comparable hard circuits may require 2 500–10 000 qubits without recycling.Source: C. Further implementations of quantum… · p. 58

VII. CLASSICALLY SIMULATING QUANTUM RANDOM SAMPLING SCHEMES

  • Finite-size quantum advantage depends on the exact classical task: exact simulation, total-variation approximation, noisy-experiment reproduction, or matching a benchmark such as XEB fidelity.Classical algorithms may exploit benchmark weaknesses or available time and memory to outperform noisy quantum devices.Source: §VII · p. 58

A. Sampling versus computing output probabilities

  • Strong simulation computes amplitudes, whereas weak simulation samples distributions; Schrödinger methods use ∼2^n space and ∼m2^n time, while Feynman methods trade space for path-summing time.Sampling methods include ancestral, rejection, and Markov-chain Monte Carlo techniques, with ancestral sampling requiring exponentially many marginal sums in general.Source: A. Sampling versus computing output… · p. 59

B. Simulating universal circuit sampling

  • Universal-circuit simulations are benchmarked by approximate-state fidelity or classical-sample XEB fidelity, but producing millions of samples is costly because amplitude estimation dominates.The number of amplitudes needed for sampling typically scales linearly with the number of samples, whereas computing one amplitude can remain feasible.Source: B. Simulating universal circuit sampling · p. 60

1. Using tensor networks to simulate quantum circuits

  • Tensor-network contraction cost is governed roughly by graph treewidth; although higher-dimensional circuits lack generally efficient linear contractions, practical contraction schemes can outperform worst-case scaling.For Porter–Thomas outputs, frugal rejection sampling makes average probability evaluations independent of n while introducing TVD error 2 exp(−c/(1−e^−c)); c=10 gives ∼10^−4.Source: §1 · p. 60

a. State-vector simulation.

  • Random-circuit simulation is difficult because high entanglement makes tensor-network truncation inaccurate; nevertheless, CZ circuits allowed a single probability at depth 26 on 10×10 qubits in 9 minutes.A depth-40 7×7 circuit required 31 minutes and 92.51 TB memory, while 54-qubit CZ-state simulations reached experimental-scale fidelities on a laptop in a few hours.Source: a. State-vector simulation · p. 61

b. Hybrid algorithms.

  • Hybrid slicing balances memory and runtime by splitting circuits, but iSWAP*-like gates are harder than CZ: their decomposition rank four implies roughly quadratic additional effort across partitions.Markov et al. (2018) estimate amplitudes by summing a fidelity fraction of equal-weight paths, producing M correlated samples at the cost of f·M noiseless amplitudes.Source: b. Hybrid algorithms · p. 62
  • At 0.5% fidelity, recycling tensor contractions simulated depth-40 7×7 CZ circuits in 2.44 h and depth-24 11×11 circuits in 0.28 h.Villalonga et al. (2019) reuse an initial contraction to obtain contractions for nearby bit strings, enabling faster sampling.Source: b. Hybrid algorithms · p. 62
  • Pan and Zhang (2022) obtained 2^21 correlated bit strings with exact probabilities, while postselecting the 2^16 largest yielded an XEB score of 0.736.The big-head method contracts a large network head once and combines it with smaller tail contractions; Liu et al. (2021d) reduced runtime to a few minutes on a supercomputer.Source: b. Hybrid algorithms · pp. 62–63
  • Liu et al. (2021b) produced one perfect depth-20 sample in 276 seconds, whereas one million samples at 0.2% XEB fidelity would require 2000 perfect samples after uniform dilution.Their approach leaves 6 rather than 21 tensor-network legs open, but the resulting perfect samples are costly to generate.Source: b. Hybrid algorithms · p. 63
  • 220 independent samples at approximately 0.37% XEB fidelity were generated in about 15 hours on 512 GPUs, and they passed the validation tests used by Arute et al. (2019).Pan et al. (2022) removed 8 tensor-network edges to reduce complexity, producing batches of correlated probabilities from which independent samples were obtained.Source: b. Hybrid algorithms · p. 63
  • Kalachev et al. (2021b) spoofed linear XEB at 0.47% in four hours on one GPU, while estimating that 0.2% fidelity sampling would require 15 months on one GPU.Their slicing procedure targets a chosen fidelity by maximizing partially summed-slice norms and reduces sampling overhead by a factor of 2.Source: b. Hybrid algorithms · p. 63
  • High XEB scores do not establish correct sampling: Gao et al. (2021) reached within one order of magnitude of Arute et al. (2019) on a laptop despite presumably exponentially small quantum fidelity.The discussion distinguishes benchmark spoofing from independent, high-entropy samples drawn from a high-fidelity quantum state.Source: b. Hybrid algorithms · pp. 63–64
  • Napp et al. (2022) supplied numerical and analytical evidence that depth-3 universal circuits on a 400 × 400 brickwork architecture are strongly and efficiently weakly simulable within constant total-variation error.Their evidence combines tensor-network simulations with a mapping to alternating random unitaries and weak measurements.Source: d. Efficient algorithms · p. 64

d. Efficient algorithms. … 2. Simulating the sampling task

This section surveys classical simulation methods for quantum random sampling, including stabilizer-, Fourier-, permanent-, Hafnian-, marginal-, and correlation-based approaches. It examines how noise and circuit structure affect simulability, highlighting efficient algorithms for noisy boson sampling and the unresolved intermediate regime.

d. Efficient algorithms.

  • Classical algorithms can track existing experimental universal circuit-sampling schemes, although stabilizer-decomposition methods remain impractical because complexity grows exponentially with stabilizer rank χ.Clifford circuits are efficiently simulable, while non-Clifford circuits are represented as linear combinations of Clifford circuits.Source: e. Alternative simulation schemes · p. 64

3. Analysis of noise

  • Constant noise enables efficient classical simulation in several regimes, including logarithmic-depth random circuits, eliminating a prospective anticoncentration-based quantum-advantage sweet spot.Aharonov et al. (2022) efficiently simulate anticoncentrated noisy universal circuits to inverse-polynomial total-variation distance, while constant-depth-independent Pauli-noise results support uniform sampling when depth is ω(log n).Source: §3 · p. 65
  • Noise can also be classically mitigated for IQP circuits, but extending coding-based protection beyond IQP remains unclear.Bremner et al. (2017) encode a smaller IQP circuit into a larger one whose noisy samples approach the ideal distribution arbitrarily closely.Source: §3 · p. 65

1. Computing probabilities: permanents and Hafnians

  • Permanent and Hafnian re-expressions reduce boson-sampling probability computation to O(n2^n) and O(n^3 2^(n/2)) time, with further gains from sparsity, bandwidth, and special matrix structure.These methods enable permanent computation for matrices up to 54 × 54, while special cases admit multiplicative-error or quasi-polynomial approximations.Source: §1 · p. 66

2. Simulating the sampling task

  • Fock boson-sampling simulation reaches average runtime approximately O(n^1.69n) when m = n, indicating that roughly 40 photons may be needed to exceed current classical capabilities.Clifford and Clifford’s exact algorithm uses ancestral or marginal sampling, with runtime dominated by a final full-matrix permanent.Source: §2 · p. 67
  • Gaussian boson-sampling implementations simulated m = 60 modes with up to 80 photons in 3 seconds per sample and generated a 92-photon event in m = 100 modes in 82 minutes.The same supercomputer simulated m = 100 modes with up to 60 click events in 8.4 seconds per sample.Source: §2 · p. 68
  • For noisy boson sampling, constant local noise is heuristically classically simulable, inverse-photon-number noise may retain ideal complexity, and the intermediate regime remains open.Shchesnovich (2019) gives inverse-polynomial total-variation error at polynomial cost for constant-strength noise, while noise of O(1/n) is presumed as hard as ideal sampling.Source: §2 · p. 69
  • Oh et al. (2023) provide a provable approximate sampler for noisy Fock boson sampling with quasi-polynomial runtime n^O(log n,log(1/ϵ),log(1/δ)) per sample at constant noise, for 1−δ of Haar-random unitaries.The algorithm uses low-degree polynomial decompositions to compute marginals within total-variation distance ϵ, assuming m ∈ω(n^5).Source: §2 · p. 69
  • A polynomial-time guarantee requires the total noise rate to scale as 1−x^γ with γ=Ω(log n), because constant per-gate noise accumulates with circuit size.Earlier approaches also lack efficiency proofs because they do not bound the corresponding Markov chain’s mixing time.Source: §2 · p. 69
  • Noise suppresses higher-order interference exponentially, motivating efficient low-order classical simulations, but Shchesnovich (2022, 2021) shows their outputs can be efficiently distinguished from noisy boson sampling.Higher-order correlations remain significant, consistent with experimental data from Zhong et al. (2021).Source: §2 · p. 69
  • Because noise makes imperfect-device simulation less demanding, demonstrating an unambiguous quantum advantage with quantum random sampling becomes more challenging.Source: §2 · p. 69

VIII. PERSPECTIVES … D. Concluding thoughts

This section surveys open challenges and future directions for quantum random sampling, spanning complexity, noise and error resilience, verification, extensions, and applications. It concludes by considering its potential for estimating physically motivated quantities and its broader role in advancing useful, fault-tolerant quantum computing.

1. Understanding random quantum circuits better

  • Approximate average-case hardness remains the central complexity-theoretic open question, requiring new proof ideas beyond polynomial interpolation because current methods cannot reach the needed robustness O(2^-n).The conjecture currently rests on the absence of efficient classical simulation algorithms and the apparent lack of exploitable structure in random instances.Source: §1 · p. 70
  • Noise must be optimized against circuit depth and system size because fixed experimental errors can make short circuits classically simulable or large circuits too noisy to retain computational difficulty.Achieving constant global error requires gate errors to scale inversely with 1/(m+2n), while experimentally relevant errors are typically size-independent.Source: §1 · p. 70

2. Verification beyond XEB

  • XEB does not yet provide a fully understood certificate of global-distribution accuracy, while sample-efficient verification beyond XEB remains an open problem because estimating target probabilities can be exponentially costly.Logarithmic XEB yields rigorous total-variation bounds only under entropy-increasing noise, and efficient alternatives involving cryptographic or public verification remain unsettled.Source: §2 · pp. 70–71

1. Improving error resilience

  • Making sampling hardness robust to constant local errors is a major challenge because error correction requires elaborate syndrome measurements, while unheralded or altered errors can change the distribution underlying the hardness conjecture.Error detection and post-hoc correction are suggested as possible routes, but nonadaptive correction can lose robustness when it changes the relevant output distribution.Source: §1 · pp. 71–72

2. Relation to analogue quantum simulation

  • Analog quantum simulators offer many accurately controlled degrees of freedom, motivating complexity-theoretic separations for physically natural tasks such as correlation-function or energy-measurement sampling.Existing proposals provide weaker consequences such as BPP = BQP rather than evidence for BPP̸ = BQP, although they may target tasks more useful than sampling alone.Source: §2 · p. 72

C. Towards applications of quantum random sampling

  • Potential applications divide between exploiting high-min-entropy quantum randomness and programming structured output distributions to solve computational tasks.The first category includes certified randomness, while the second uses programmable samplers as algorithmic subroutines.Source: C. Towards applications of quantum… · p. 72

1. Exploiting randomness

  • Quantum random sampling could generate certified random bits: Bassirian et al. (2021) show in a black-box model that no BQP or PH algorithm solves LLQSV, supporting certification through an XEB-like test under an unstructured-random-function assumption.The evidence includes an average-case linear min-entropy bound for quantum algorithms that pass the test.Source: §1 · p. 73

2. Exploiting structure

b. Estimating physical quantities using Gaussian boson samplers.

  • Gaussian boson samplers have been proposed for estimating Franck–Condon factors, molecular vibronic spectra, and molecular docking configurations, with experiments and benchmarks addressing practical feasibility (Jnane et al., 2021; Banchi et al., 2020a; Quesada, 2019; Clements et al., 2018; Wang et al., 2020).These proposals connect vibronic quantities to graph perfect matchings and include non-Condon scattering, truncation-error analysis, and experimental-imperfection benchmarks.Source: b. Estimating physical quantities… · p. 74
  • Problem-specific Gaussian-boson-sampling instances may admit efficient classical algorithms, so quantum speedup must be assessed against the best classical method rather than assumed from complexity-theoretic arguments (Oh et al., 2022a,b; Roga and Takeoka, 2020).Support detection can reduce to polynomial-time Ising optimization under suitable conditions, while positive P-representation methods yield exact zero-temperature Fourier components.Source: b. Estimating physical quantities… · pp. 74–75

D. Concluding thoughts

  • Quantum random sampling offers conceptually simple schemes with relatively small experimental requirements for testing whether naturally feasible computations exceed efficient classical Turing-machine descriptions.The review frames this as a foundational challenge to the extended Church–Turing thesis and calls for further experimental realization and verification.Source: D. Concluding thoughts · p. 75
  • Quantum-random-sampling experiments provide a first milestone toward large-scale quantum computation and fault tolerance by advancing experimental control and informing practically motivated algorithms.Examples include vibronic-spectrum experiments, variational schemes, statistical-physics simulations, and a superconducting layout designed for surface-code compatibility (Somhorst et al., 2022).Source: D. Concluding thoughts · p. 75
  • Theoretical follow-up targets more practical advantages through optimization and variational algorithms, while the noise tolerance required for advantage without error correction remains open (Farhi et al., 2014; Zhou et al., 2020a; McClean et al., 2016; Stilck França and García-Patrón, 2021).These efforts are presented as stepping stones toward useful quantum computers and the next major hurdle in the field.Source: D. Concluding thoughts · p. 75

Related papers

Loading 2206.04079v4…