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 reviewed as a proposed test of quantum computational advantage, with emphasis on the gap between exact and approximate classical-sampling hardness. The paper synthesizes complexity theory, verification, experiments, noise, and simulation, concluding that exact-sampling evidence is strong while approximate-sampling evidence remains weaker and technically bounded.

  • Problem

    The field needs evidence that quantum random sampling is classically hard and can support claims of computational advantage despite noise and verification challenges.

  • Method

    The paper reviews complexity-theoretic hardness, verification methods, experimental implementations, noise resilience, and classical simulation strategies for quantum random sampling.

  • Results

    Exact-sampling hardness has very strong complexity-theoretic evidence, whereas approximate-sampling evidence is substantially weaker; current techniques achieve robustness 2^-O(m) for universal random circuits.

  • Takeaways & Limitations

    Quantum random sampling provides a framework for studying quantum advantage across asymptotic complexity, experimental implementation, verification, and finite-size classical simulation.

  • Takeaways & Limitations

    The review identifies unresolved average-case hardness, noise-resilience, verification, and finite-size simulation challenges for establishing practical quantum advantage.

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

Quantum random sampling is presented as a near-term test of quantum computational advantage, addressing both classical simulation hardness and experimental verifiability. The review connects complexity-theoretic evidence with practical implementations, noise analysis, verification, and simulation.

  • Quantum computation can offer presumably exponential speedups for factoring and quantum-system simulation, motivating tests of quantum advantage.
  • Current devices offer roughly 50 to 100 physical qubits but remain far from the error-correctable regime and are difficult to improve and scale.
  • Quantum random sampling asks for a noisy-device task that is asymptotically and practically difficult for classical computers yet admits a simple success test.
  • Factoring is easy to verify but requires roughly 20 million physical qubits for a 2048-bit RSA instance, making it unsuitable as a near-term advantage test.
  • The review surveys quantum random sampling as a test of presumed exponential advantage, covering computational meaning, classical performance, verification methods, noise, experiments, and simulation.

D. Gaussian boson sampling

The review places Gaussian boson sampling within quantum random sampling and relates its practical appeal to experimentally accessible Gaussian states and measurements. It also frames sampling advantage through classical simulation complexity and probability structure.

  • D. Gaussian boson sampling: Gaussian boson sampling uses Gaussian input states, including squeezed or displaced squeezed states, and has an unbounded photon-number sample space.
  • D. Gaussian boson sampling: Gaussian states and measurements are experimentally easier to implement than photon-number states and measurements, enabling recent large-scale experiments.
  • The review defines multiple sampling schemes and develops the computational-complexity background used to analyze their classical intractability.
  • Quantum random sampling schemes are designed to demonstrate quantum advantages both through finite-instance simulation limits and through asymptotic classical complexity.
  • Quantum and classical acceptance probabilities have related counting representations, but their multiplicative-approximation hardness can differ substantially.

D. Approximating GapP

The section explains why approximating signed GapP quantities is harder than approximating ordinary nonnegative counts and connects this distinction to quantum output probabilities. It also situates these results within polynomial-hierarchy-based evidence.

  • D. Approximating GapP: GapP sums differ between two exponentially large counts, so their values can be much smaller and expose nontrivial sign information under relative approximation.
  • D. Approximating GapP: Constant multiplicative approximation of GapP gaps is GapP-hard because relative-error estimates reveal sign information that supports iterative exact-value recovery.
  • D. Approximating GapP: The approximation procedure shifts a GapP function, tests relative-error estimates around successive guesses, and halts after O(n) steps when the normalized gap spacing is used.
  • D. Approximating GapP: Quantum output probabilities inherit GapP-completeness under exponentially small additive error, including error 1/2^(2n).
  • Stockmeyer’s algorithm approximately counts #P accepting paths with an NP oracle, providing a complexity-theoretic basis for distinguishing #P and GapP approximation behavior.
  • The framework relies on the polynomial hierarchy, whose strictness generalizes the presumed separation P ≠ NP and underpins hardness arguments for approximate counting.

2. Stockmeyer’s approximate counting algorithm

Stockmeyer’s approximate counting algorithm connects sampling to probability estimation within the third level of the polynomial hierarchy. This connection underpins hardness results for quantum sampling, where quantum output probabilities are GapP-hard to approximate.

  • Stockmeyer’s 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.
  • Quantum–classical complexity: Quantum acceptance probabilities are GapP-hard to approximate up to relative error, unlike classical probabilities expressed as sums of nonnegative terms.The distinction arises from negative signs in quantum amplitudes and nonnegative classical summands.
  • Sampling connection: Sampling can be linked to probability approximation by representing a sampler as a Boolean function and applying Stockmeyer’s algorithm to its output events.The resulting estimate achieves a 1 − 1/poly(|y|)-multiplicative approximation.
  • Hardness consequences: If a circuit family’s output probabilities are GapP-hard to approximate, efficient sampling for that family would imply that the polynomial hierarchy collapses to Σ3.This follows because Stockmeyer’s algorithm would provide the required probability approximations in the third level.
  • Boson sampling: For boson sampling, output probabilities involve permanents, while Gaussian boson sampling uses Hafnians; approximating the relevant permanent quantities is GapP-hard.The Hafnian is therefore at least as hard to approximate as the permanent in the worst case.

C. Hardness argument

The hardness argument reduces efficient classical sampling to approximate probability computation via Stockmeyer’s algorithm. It rules out efficient exact or sufficiently accurate multiplicative-error sampling under the conjecture that the polynomial hierarchy does not collapse, while motivating total-variation distance for realistic errors.

  • Exact sampling: Efficient exact sampling would enable third-level polynomial-hierarchy approximations to GapP-hard output probabilities, collapsing the hierarchy to Σ3.Theorem 15 formalizes this implication for circuit families whose probabilities are GapP-hard to approximate.
  • Exact sampling: The exact-sampling proof requires constant-relative-error hardness of output probabilities but only worst-case hardness, since one hard instance suffices.Exact computability hardness alone is insufficient for the argument.
  • Multiplicative-error sampling: Multiplicative-error sampling remains hard when the sampler’s error combines with Stockmeyer’s approximation to a GapP-hard relative-error approximation.If the product error cd remains within the hard regime, efficient sampling implies polynomial-hierarchy collapse.
  • From multiplicative to additive errors: Constant multiplicative accuracy is impractical because it must resolve exponentially many probabilities, including values arbitrarily close to zero.The paper notes that such accuracy may require fault tolerance and ultra-high precision scaling with system size.
  • Why the total-variation distance?: Total-variation distance offers a more plausible robustness measure because classical finite precision and noisy quantum devices naturally induce additive distributional errors.The paper identifies constant TVD as a nontrivial target requiring component errors on the order of 1/m, although that scaling remains demanding.
  • Why the total-variation distance?: Trace distance and total-variation distance do not model physically realistic local errors well, because constant gate errors can make distance grow linearly with circuit size.Without additional normalization, the distance can quickly approach a trivial value.

3. Approximating

Approximate sampling hardness requires average-case hardness of output-probability approximation and a hiding property, linking efficient classical sampling to a polynomial-hierarchy collapse. The framework uses Stockmeyer’s algorithm and applies to random circuit and boson-sampling families.

  • 3. Approximating: Approximate sampling hardness requires approximate average-case hardness of output probabilities and the hiding property, beyond the assumptions used for exact sampling hardness.These properties support hardness against constant additive errors in total-variation distance.
  • 3. Approximating: The hiding property holds naturally for many random circuit families because Haar measure is invariant under arbitrary unitary transformations, including Pauli-X.This invariance supports hiding the selected output instance within the random-circuit ensemble.
  • 3. Approximating: The approximate-sampling proof combines a sampler’s output with Markov’s inequality and hiding to obtain probability estimates that are accurate on a 1 −δ fraction of instances.The resulting estimate has exponentially small additive and inverse-polynomial multiplicative error components.
  • 3. Approximating: An efficient classical sampler for random circuit outputs would enable Stockmeyer’s algorithm to approximate GapP-hard probabilities in the third level of the polynomial hierarchy.Under the stated assumption, this implies that the polynomial hierarchy collapses.
  • 3. Approximating: In boson sampling, hiding follows when collision-free submatrices of Haar-random unitaries are approximately Gaussian, with collision-free postselection requiring m ∈Ω(n^2) and stronger Gaussian approximation requiring m ∈Ω(n^5 log(n)^2).The resulting submatrix distribution is approximately Gaussian regardless of the selected collision-free outcome.
  • 3. Approximating: A bespoke Gaussian boson-sampling construction can encode an arbitrary matrix’s permanent by programming the squeezing values and bipartite unitaries.Choosing the singular-value-decomposition components allows the encoded matrix to be Gaussian and satisfy the hiding property by definition.

D. Approximate average-case hardness

Approximate average-case hardness connects the sampler’s mixed error bound to either exponentially small additive or constant relative error through anticoncentration. The review explains the statistical conditions supporting this reduction and emphasizes that the key hardness conjecture remains unproved.

  • D. Approximate average-case hardness: Anticoncentration reduces the mixed error bound to either exponentially small additive error or constant relative error, depending on the output probability’s scale.This reduction uses Markov’s inequality for additive control and the anticoncentration property for relative-error control.
  • D. Approximate average-case hardness: With independent failure probabilities, the additive bound holds on a (1 −δ)(1 −α) fraction of inputs, while the relative bound holds on at least γ(α)(1 −δ) of instances.The two bounds arise by combining concentration or anticoncentration with the sampling-hardness estimate.
  • D. Approximate average-case hardness: The reduction yields additive approximate average-case hardness up to O(2−n) on any γ fraction and relative approximate average-case hardness up to relative error 1/4 on any γ(1 −γ/2) fraction.These are the two sufficient hardness conditions stated for completing the approximate-sampling argument.
  • D. Approximate average-case hardness: Approximate average-case hardness remains unproved for both additive and relative errors, although GapP-function structure makes the conjecture plausible.GapP values are differences of exponentially large #P counts, often producing smaller typical values where multiplicative hardness may remain meaningful.
  • D. Approximate average-case hardness: Anticoncentration is not necessary for sampling hardness, whereas approximate average-case hardness is sufficient for approximate sampling hardness within this proof strategy.The review treats anticoncentration as a proof aid and source of evidence rather than a general requirement.
  • D. Approximate average-case hardness: Anticoncentration can be certified through second moments: bounding the average collision probability 2n E[p0(C)^2] as O(2−n) is sufficient.The normalized second moment is the average collision probability of the output distribution.
  • D. Approximate average-case hardness: Anticoncentration has been proven for logarithmic-depth nearest-neighbor random circuits in one dimension with uniformly random two-qubit gates.The proof bounds the average collision probability using a mapping to a statistical-mechanics model.

c. Further proofs of anticoncentration.

Further proofs extend average-case hardness arguments through random self-reducibility, decoding, and polynomial interpolation, while revealing limitations from finite precision and anticoncentration. These methods progressively reduce success-probability requirements but remain constrained by unresolved approximate average-case hardness.

  • Further proofs of anticoncentration: Anticoncentration is necessary for additive average-case hardness reductions, but proving the underlying approximate average-case hardness conjecture remains unresolved.The dependence of average-case complexity on the input distribution motivates random self-reducibility methods, while the central conjecture remains open.
  • Random self-reducibility: Random self-reducibility uses polynomial structure to reduce arbitrary permanent instances to random instances along an interpolation path.For E(t), the permanent becomes a degree-n polynomial q(t), allowing recovery of q(0) from evaluations at random points.
  • Random self-reducibility: n + 1 correct evaluations suffice to interpolate a degree-n permanent polynomial and recover the hard instance with probability at least 2/3 − 1/3n.The construction queries distinct nonzero points and uses a union bound to obtain enough correct pairs.
  • Improving the success probability: 1/2 + 1/poly(n) correctness is sufficient after improved decoding and interpolation paths, strengthening the original average-case hardness requirement.Earlier decoding succeeds at 3/4 + 1/poly(n), while Gemmell and Sudan improve this to 1/2 + 1/poly(n).
  • Improving the success probability: List-decoding replaces unique decoding by producing a bounded list of compatible polynomials, enabling hardness results for much smaller fractions of correct points.The cited results establish average-case hardness over sufficiently large finite fields even for an inverse-polynomial fraction of correct points.
  • Distributions over infinite fields: the case of F = C: Finite-precision evaluations prevent direct use of Berlekamp–Welch, requiring stable interpolation and extrapolation bounds instead.Numerical evaluation introduces errors on the order of 2^-poly(n), whereas Berlekamp–Welch requires exact point evaluations.

c. Robustness to finite-precision errors.

Finite-precision robustness is established through polynomial interpolation and extrapolation, but current guarantees remain weaker than those needed for approximate average-case hardness. The main barriers are instability under perturbed interpolation points, noise sensitivity, and limitations of some circuit architectures.

  • Interpolation-based robustness: Paturi’s stable extrapolation lemma and Rakhmanov’s stable interpolation theorem bound errors between evaluation points and when extrapolating to the target probability.Applied to p(t) = q(t) − q′(t), they control errors arising from values known only approximately.
  • Interpolation-based robustness: 2^-O(m log m) robustness is achieved on a 1 − 1/O(m) fraction of instances using Lagrange-polynomial interpolation.This improves the earlier 2^-O(m^2) robustness obtained from the same general strategy.
  • Scope of reductions: The unitary-group worst-to-average-case reduction requires continuous gate distributions and therefore does not apply to discrete gate sets or some architectures.A recursive reduction for a discrete IQP family provides one step toward an exact average-case hardness reduction.
  • Remaining gap: 2^-O(m) robustness for universal random circuits and 2^-O(n) for IQP circuits still falls short of the O(2^-n) robustness required for the approximate average-case hardness conjecture.The gap is reduced to constants in the exponent for some circuit families, but the conjectured threshold is not reached.
  • Noise and interpolation barriers: Random self-reducibility cannot generally deliver additive robustness near 2^-n because polynomial interpolation is linear in the coefficients and additive errors.This motivates restricted polynomial classes, while noisy error-detectable probabilities remain hard only up to technique-dependent error scales.
  • Remaining gap: Krovi’s results match the 2^-O(m) and 2^-O(n) robustness scalings, while Fock boson sampling reaches e^−(c+4)n log n−O(n), within constant factors in the exponent of the required bound.These bounds are described as essentially optimal for the interpolation technique up to logarithmic factors, with the boson-sampling result closer to the conjectured threshold.
  • Noise and interpolation barriers: High-noise random circuits may converge toward uniform probabilities as 2^-n−O(d), potentially lowering the barrier, but some architectures still admit efficient strong and weak simulation on large instance fractions.The latter observation shows that worst-case classical hardness need not imply approximate average-case hardness for every architecture.
  • Scope of reductions: Approximate sampling hardness has substantially weaker evidence than exact sampling hardness because it relies on an approximate average-case hardness conjecture.Failure of that conjecture would not produce meaningful consequences in complexity theory, although proving it may remain possible.

E. Fine-grained results

Fine-grained complexity results seek quantitative runtime lower bounds for classical simulation, extending asymptotic hardness arguments to finite experiments and noisy settings.

  • Motivation: Fine-grained results address the absence of quantitative runtime lower bounds in standard complexity-theoretic sampling-hardness arguments.They aim to show that finite experiments exceed reasonable classical computational resources, not merely that efficient simulation is asymptotically unlikely.
  • Fine-grained reductions: Fine-grained hardness arguments reduce IQP simulation to poly3-NONBALANCED, which asks whether a degree-3 Boolean polynomial has nonzero gap.The reduction connects output probabilities of IQP circuits to a decision problem involving the imbalance between zero and one outputs.
  • Conditional bounds: Under poly3-NSETH(a), the assumed classical sampling algorithm must satisfy t(n) ≥ 2^(an−1), with the best known limit a < 0.9965.The lower bound depends on the conjectured nondeterministic hardness of poly3-NONBALANCED.
  • Finite-size estimates: For IQP circuits, approximately 200 qubits and 10^6 gates are estimated to require at least a century on state-of-the-art supercomputers.This estimate concerns a classical-simulation algorithm for IQP circuit sampling.
  • Noise: Noise complicates hardness because constant local gate errors can make total-variation distance exponentially close to one, motivating analyses of alternative noisy distributions.White-noise and circuit-noise results identify regimes where approximate sampling may retain or lose hardness.

1. Heavy-outcome generation

Heavy-outcome generation tests whether samples concentrate on outcomes that are more probable than the ideal distribution’s median. It is sample-efficient and intuitively connected to total-variation distance, but its hardness and fidelity implications are limited.

  • Definition: Heavy-outcome generation asks for distinct output strings, with at least two-thirds having ideal probabilities above the median.The HOG task is equivalent to achieving a nonzero HOG-fidelity score.
  • Definition: Heavy outcomes are bit strings whose ideal probabilities exceed the median, and HOG fidelity measures the target distribution’s probability bias toward them.The median can be estimated efficiently, while ideal probabilities for sampled strings are compared against it.
  • Sample efficiency: HOG fidelity can be estimated from samples with probability-comparison error O(1/k) and exponentially small failure probability.This follows from estimating the median and evaluating ideal probabilities for the sampled outcomes.
  • Limitations: A distribution supported only on heavy outcomes achieves HOG fidelity 1/ln 2 > 1 while remaining at least (1−ln 2)/2 away in total variation.Thus, high HOG fidelity does not by itself certify closeness to the ideal distribution.
  • Computational hardness: HOG is conjectured computationally intractable for random circuits through QUATH, but the review says the complexity-theoretic evidence for both conjectures is extremely weak.The reduction concerns deciding whether a circuit output probability exceeds the median.
  • Binned outcome generation: Binned outcome generation refines HOG by grouping samples according to ideal probabilities and estimating total-variation distance.With m bins it converges to ||Q−PC||TV as m grows, and identity testing uses O(k/ε^2) samples for k bins and error ε.
  • Cross-entropy measures: Cross-entropy measures capture correlations between noisy and ideal distributions, but their sample efficiency degrades when the measure is exponentially small.The required estimation error must then also scale inversely exponentially.

3. Linear cross-entropy benchmarking (XEB) fidelity

Linear cross-entropy benchmarking uses ideal output probabilities to evaluate random-circuit implementations and can serve as both randomized benchmarking and single-instance verification. Its interpretation depends on typicality and noise assumptions.

  • Definition: XEB fidelity chooses the identity function, rescaled as fXEB(x)=2^n x−1, within the cross-entropy framework.This produces the standard linear cross-entropy benchmarking measure.
  • Uses: XEB fidelity has two uses: average fidelity over random gate sequences and verification of individual quantum-random-sampling circuits.The first is a randomized-benchmarking protocol, while the second relies on typicality arguments.
  • Interpretation: For large random circuits, XEB fidelity is an intrinsically average-case measure whose single-instance interpretation depends on circuit typicality.A single circuit can be assessed because it is expected to be representative of the random family.
  • Noise benchmarking: XEB fidelity estimates depolarization fidelity by relating circuit-averaged XEB to the noisy output state under an uncorrelated-noise assumption.An exponential fit across circuit depths can estimate the per-cycle depolarization parameter.
  • Estimator behavior: Average fidelity decays as e^(−λd) up to first-order corrections for depth d≪2^n, and unbiased XEB has variance O(1/ℓ+λ^2(EF)^2).Here λ is the total error and ℓ is the number of samples per circuit.
  • Estimator comparisons: Maximum-likelihood and unbiased XEB estimators have lower bias or variance than the linear XEB estimator, while linear XEB converges to maximum likelihood when depolarization fidelity is small.The small-fidelity regime is specified by εd≪1.
  • Concentration: For large qubit counts, fidelity concentrates around its expectation over random circuits, supporting circuit-averaged XEB interpretations.The concentration follows from typical fluctuations under Haar-random circuits.

d. Hardness of achieving a nontrivial XEB fidelity.

The review presents XEB fidelity as both a computationally hard benchmark and a proxy for quantum fidelity, but shows that adversarial classical simulators can exploit differences between these quantities. This motivates alternative verification measures such as cross-entropy difference and direct state-level verification.

  • XEB fidelity serves both as a potentially intractable task for random quantum circuits and as a proxy for quantum fidelity.
  • In adversarial settings, XEB fidelity can overestimate quantum fidelity, allowing classical simulators to obtain high scores without reproducing the intended quantum performance.
  • XEB and quantum fidelity scale differently when independent systems are combined: fidelity multiplies, whereas total XEB fidelity generally increases.
  • Linear XEB can require exponentially many samples for statistical significance because its quantum score scales inversely exponentially.
  • Cross-entropy difference remains a potential benchmark because the spoofing strategies developed for linear XEB presumably do not apply to it.
  • Fidelity witnesses offer state-level verification using restricted measurements, but their fidelity bounds typically become loose when preparations are not very close to the target.

2. Fidelity estimation

Fidelity estimation provides direct information about the quality of quantum state preparations through several protocols, with trade-offs between sample complexity, measurement settings, and computational efficiency. The review discusses direct, stabilizer-based, and shadow-based approaches, alongside their applicability limits.

  • Direct fidelity estimation can estimate fidelity to pure target states with a constant number of samples in suitable settings.
  • The protocol samples observables according to probabilities pλ, measures them on the prepared state, and averages outcomes to estimate fidelity with O(1/ϵ2) samples for error ϵ.
  • For stabilizer states, fidelity estimation is efficiently applicable to architectures locally equivalent to stabilizer-state preparations, including measurement-based computation.
  • Direct fidelity estimation reduces quantum sample complexity from O(n3) to O(1) but increases measurement-setting complexity from O(1) to O(1/ϵ2).
  • Shadow fidelity estimation also has constant sample complexity but is computationally inefficient for non-Clifford target states.
  • Verification methods trade classical efficiency and experimental demands: classical protocols may require exponential computation, while quantum tools require trusted measurements in different local bases.

E. Further approaches to the verification of quantum samplers

The review surveys verification and implementation strategies for quantum samplers, emphasizing practical tests, hardware benchmarking, and extrapolated classical costs. Experiments have advanced in superconducting and photonic platforms, while source quality and verification assumptions remain important boundaries.

  • Most surveyed verification protocols assume independently and identically distributed state preparations, although de Finetti arguments can address non-iid. settings.
  • Quantum random sampling is experimentally attractive because it avoids interactive feedback and can use relatively small circuits without full quantum error correction.
  • Arute et al.'s elided and patch methods were supported by comparisons with full simulations on simplifiable circuits and by agreement with an error model.
  • FXEB(Q, PC) ≈ (2.24 ± 0.21) × 10−3 for 53-qubit, depth-20 circuits, exceeding 10−3 with 5σ significance.
  • For 53 qubits and depth 20, the experiment was estimated at about 200 s for one million samples, versus 10 000 years classically on a million cores.
  • Follow-up superconducting experiments reported XEB fidelities of 0.0662% and 0.0758%, while Zhu et al. estimated roughly four orders of magnitude more resources than the earlier task.
  • Large-scale photonic implementations reached n = 113 detected photon events in circuits with m = 144 optical modes, while single-photon-source limitations remain a key scaling constraint.

C. Further implementations of quantum random sampling

Further implementations broaden quantum random sampling beyond standard superconducting and photonic gate-based schemes, while classical simulation methods continue to approach existing experimental demonstrations. Comparisons depend strongly on the simulation target, error metric, and noise model.

  • Alternative implementations: Measurement-based quantum random sampling reduces device control by fixing entangling gates and randomizing only one layer of Z rotations.Its trade-off is greater spatial demand: approximately 2,500–10,000 qubits may be needed for circuits comparable to Arute et al. (2019).
  • Alternative implementations: Quantum random sampling can also be induced through physical interaction mechanisms, including quantum walks of non-interacting massive bosons.These schemes aim to lessen the burden of explicitly implementing random circuits in gate-based hardware.
  • Verification and comparison: Simulation difficulty depends on whether the goal is exact sampling, low-TVD approximation, realistic-noise simulation, or matching a benchmark score by other means.The appropriate classical comparison therefore changes with the task definition.
  • Classical simulation: Fidelity 0.5% simulations reached depth-40 7×7 circuits in 2.44 hours and depth-24 11×11 circuits in 0.28 hours on a fast supercomputer.The method recycles an initial tensor contraction to obtain contractions for nearby bit strings.
  • Verification and comparison: Classical algorithms exploiting weaknesses in linear XEB can achieve scores comparable to noisy quantum devices, with one laptop method reaching only one order of magnitude below Arute et al. (2019).This illustrates why benchmark scores do not necessarily establish direct sampling intractability.
  • Classical simulation: Modern supercomputers can just keep track of existing universal circuit-sampling experiments, but all discussed methods fail for the slightly larger implementation by Zhu et al. (2022).Fair comparison remains difficult because experimental samples and classical spoofing strategies are validated only by incomplete methods such as cross-entropy benchmarking.
  • Classical simulation: Depth-3 two-dimensional brickwork circuits can be strongly and efficiently weakly simulated within constant total-variation error.Napp et al. (2022) provide both numerical and analytical evidence for this shallow-circuit regime.

d. Efficient algorithms.

Efficient classical algorithms exploit circuit structure, noise, and alternative representations to simulate quantum random sampling in important regimes. These methods can be powerful, but their efficiency and applicability remain restricted by circuit depth, noise assumptions, detector models, and approximation guarantees.

  • State decompositions: Stabilizer decomposition expresses non-Clifford circuits as linear combinations of Clifford circuits, but its complexity grows exponentially with stabilizer rank χ.Because non-Clifford gates typically grow much faster than qubits, this approach is currently not practically useful.
  • Universal circuits: Modern supercomputers can just keep track of existing experimental universal circuit-sampling schemes using sophisticated classical algorithms.The conclusion concerns current experiments rather than arbitrary larger circuits.
  • Noise-assisted simulation: Local Pauli noise can drive IQP and universal-circuit output distributions toward regimes where classical simulation is feasible.For IQP circuits, classical coding can also protect against depolarizing noise and approximate the ideal distribution arbitrarily closely.
  • Noise-assisted simulation: Constant local depolarizing noise can make noisy universal random circuits efficiently simulable up to inverse-polynomial total-variation error when the output distribution anticoncentrates.The cited result applies after every gate and requires at least logarithmic depth for anticoncentration.
  • Boson sampling: For nonnegative matrices, the permanent can be approximated to multiplicative error ϵ in time poly(n, 1/ϵ), showing regimes where sampling need not be intractable.These results identify structured instances that evade worst-case #P-hardness conclusions.
  • Boson sampling: When m = n, Clifford and Clifford’s exact boson-sampling algorithm runs in approximately O(n^1.69n) average-case time.The algorithm uses ancestral or marginal sampling and improves substantially on naïve worst-case complexity.
  • Boson sampling: A supercomputer with approximately 100,000 cores simulated 60 modes and up to 80 photons using photon-number-resolving detectors with a mean time of 3 seconds per sample.At low photon density, simulating number-resolving detectors and reducing collisions can outperform direct Torontonian computation.
  • Boson sampling: Noise-based approximations can match correlations for the Zhong et al. (2020) experiment but not for the more recent Zhong et al. (2021) experiment.This demonstrates that spoofing performance can vary substantially across experimental implementations.

VIII. PERSPECTIVES

Quantum random sampling has mature theoretical foundations and experimental demonstrations near classical intractability, but verification, noise robustness, and useful applications remain open. The field’s next steps require improving both quantum devices and classical algorithms while clarifying practical advantage.

  • Current status: The field has thoroughly explored quantum random sampling’s theoretical foundations while identifying important and extremely difficult open questions.The review covers both theoretical and practical aspects of the subject.
  • Noise robustness: Large circuits can accumulate enough global error to make classical simulation trivial, motivating detailed study of noise and output-distribution transitions.Complementary approaches by Dalzell et al. (2021) and Deshpande et al. (2021) study these regimes.
  • Verification: XEB-based verification yields rigorous total-variation bounds only under specific noise conditions, such as entropy-increasing noise for logarithmic XEB fidelity.Estimating the noisy distribution’s entropy remains part of the verification challenge.
  • Verification: Fully efficient verification of classically intractable sampling without directly checking total-variation distance remains an open problem.Cryptographic secret-hiding approaches have been proposed but remain vulnerable to classical attacks or depart from the intended setting.
  • Error correction: Robust sampling hardness requires errors to be heralded, because maintaining hardness depends on knowing how coherent errors changed the circuit.Quantum error correction can provide robustness for universal computations but requires continuous syndrome measurement and active correction.
  • Error correction: Nonadaptive error-correction schemes may preserve sampling hardness under specific error models, but robustness can be lost when the outcome-probability distribution changes.The relevant average-case hardness conjecture may no longer apply to the altered distribution.
  • Potential applications: Gaussian boson sampling maps graph substructure to output likelihood: subgraphs with more perfect matchings are more likely to be sampled.Postselected collision-free probabilities are proportional to squared Hafnians of adjacency submatrices.
  • Road ahead: Quantum random sampling experiments provide guidance for developing quantum technologies, but the leap from demonstrations to practically useful quantum advantage remains enormous.The review describes these efforts as a first milestone toward useful quantum computers.
Loading 2206.04079v4…