PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling

Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolas Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, Dominik Hangleiter, Bill Fefferman, Ish Dhand

arXiv:2102.12474v3quant-ph

TL;DR

GBS faces unresolved classical-hardness questions and experimental tradeoffs involving programmability and loss. The authors strengthen its hardness evidence and propose programmable high-dimensional GBS, designed to avoid known feasible finite-size simulation regimes.

Abstract

from arXiv · show

Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a new QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.

INTRODUCTION

The introduction frames GBS as a promising photonic route to quantum computational advantage, but identifies experimental and theoretical gaps. The paper strengthens hardness evidence and proposes high-dimensional GBS as a programmable, low-loss architecture, alongside finite-size benchmarking and a recap of GBS.

INTRODUCTION

  • Current GBS implementations may lack programmability or have high loss, while rigorous complexity evidence and concrete finite-size simulation costs remain comparatively limited.The paper presents these gaps against photonics’ room-temperature operation, fast gates, and scalability potential.Source: INTRODUCTION · pp. 1–2

Hardness of approximate GBS

  • GBS hardness evidence is strengthened through hiding and average-case probability-hardness results, bringing its evidence in line with other QCA proposals up to a random-matrix conjecture.The paper also extends average-case hardness of output probabilities to a high-loss regime.Source: INTRODUCTION · p. 2, Hardness of approximate GBS · p. 2

INTRODUCTION

  • The paper proposes programmable high-dimensional GBS with low overall loss and argues it is hard for known classical algorithms, addressing an experimental programmability–loss tradeoff.Finite-size benchmarking estimates the cost of simulation and indicates classically intractable instances can be built with few optical components.Source: INTRODUCTION · p. 2

Recap: Gaussian boson sampling

  • GBS samples photon-number statistics after Gaussian-state preparation, linear-optical interference, and photon-number-resolving detection.The recap describes squeezed-vacuum inputs and an M-mode interferometer with beam-splitters and phase shifters.Source: Recap: Gaussian boson sampling · p. 3

Recap: Approximate sampling hardness of boson sampling

Approximate-sampling hardness arguments connect efficient sampling to hard probability-estimation tasks, but the required average-case robustness remains an open issue. For GBS, the paper formulates hiding as a random-matrix conjecture and provides analytical and numerical evidence across regimes.

Recap: Approximate sampling hardness of boson sampling

  • Approximate average-case hardness at the required inverse-exponentially small error remains unknown, despite exact average-case and robust worst-case hardness evidence.This gap matters because approximate sampling permits a constant total-variation error distributed across outcomes.Source: Recap: Approximate sampling hardness… · pp. 3–4

Hiding for arbitrarily many squeezers in GBS

  • GBS hiding is formulated by comparing Haar-unitary submatrices with symmetric products of Gaussian matrices, with evidence that they are indistinguishable when N ≤ K ≤ M.The argument relies on a plausible random-matrix conjecture; the cited formulation assumes collision-free outcomes.Source: Hiding for arbitrarily many squeezers… · p. 4
  • The conjecture’s hiding property makes same-size submatrices indistinguishable, helping spread the approximate-sampling error budget roughly evenly across outcomes.The GBS matrix is a symmetric Gaussian matrix hidden in a larger symmetric unitary matrix.Source: Hiding for arbitrarily many squeezers… · p. 5
  • Hiding has provable support in the sparse regime, analytical evidence when K is a constant fraction of M under a photon-number condition, and numerical evidence in the intermediate regime.The paper also notes that it does not expect the conjecture to hold for sufficiently large N relative to M.Source: Hiding for arbitrarily many squeezers… · p. 5

Average-case hardness of computing GBS probabilities

The paper develops average-case hardness evidence for computing GBS output probabilities, using reductions and a hiding conjecture to connect the task to Gaussian Hafnians. Its conclusions strengthen approximate-sampling hardness evidence, while retaining an open conjecture and a distinction between probability computation and feasible device tasks.

Average-case hardness of computing GBS probabilities

  • Assuming Conjectures 1 and 2, output probabilities are #P-hard to compute to exponentially small additive error with probability at least 3/4.The argument links GBS probability estimation to squared Hafnians of Gaussian matrices.Source: Average-case hardness of computing GBS… · p. 5
  • ϵ ≤ O(exp[−6N log N −Ω(N)]) makes the squared-Hafnians-of-Gaussians problem #P-hard under PH reductions for any constant δ > 3/4.The result establishes a weaker robustness level than the open approximate average-case hardness conjecture requires.Source: Average-case hardness of computing GBS… · p. 6
  • A worst-to-average-case reduction uses the low-degree polynomial structure of |Haf(XXT)|2 to extend worst-case hardness to average-case probability computation.The reduction uses polynomial interpolation.Source: Average-case hardness of computing GBS… · p. 6
  • Together with hiding evidence, the results strengthen approximate GBS sampling-hardness evidence to a level comparable with leading QCA proposals, up to a plausible random-matrix conjecture.The paper cautions that computing output probabilities is not a task feasible for a realistic quantum device; it indicates an exponentially small quantum signal.Source: Average-case hardness of computing GBS… · p. 6

Hardness of computation of output probabilities for noisy

The paper extends average-case hardness of GBS output-probability computation to local, stochastic, error-detectable noise. For optical loss, its proof uses postselection and error detection, with hardness established only below a noise threshold.

Hardness of computation of output probabilities for noisy

  • A noise threshold η∗ yields #P-hardness under PH reductions for noisy GBS probability estimation when δ > 3/4, η ≤ η∗, and ϵ ≤ 2−poly.The result applies to a sufficiently large polynomial and the stated local-noise setting.Source: Hardness of computation of output… · p. 6
  • Optical loss meets the proof’s conditions because it is a convex combination of loss channels and can be detected and corrected using linear optics and high-threshold photodetection.Postselecting on an error-free outcome gives noiseless universal gates for postselected quantum computation.Source: Hardness of computation of output… · p. 7
  • The worst-to-average-case step applies when local noise preserves the polynomial structure of the output probability.That preserved structure permits reuse of the earlier proof techniques.Source: Hardness of computation of output… · p. 7
  • The result concerns computation of output probabilities, not a feasible task for realistic quantum devices, and indicates an exponentially small quantum signal under noise.The paper considers local, stochastic noise that is error-detectable using linear optics.Source: Hardness of computation of output… · pp. 6–7

The complexity of noisy and approximate GBS

The discussion establishes hardness results for noisy GBS while noting that approximate-sampling hardness remains unproven in some realistic noise regimes. It motivates high-dimensional GBS as a programmable architecture that balances loss, connectivity, and classical simulability.

The complexity of noisy and approximate GBS

  • Noisy GBS is classically hard to exactly sample in the idealized loss-only, known-loss setting; average-case hardness of approximating output probabilities advances the case for approximate-sampling hardness.The authors stress that this result depends on the noise model accurately capturing the device.Source: The complexity of noisy and… · p. 7
  • Existing proof techniques do not establish approximate-sampling hardness across noisy GBS regimes, and some regimes are known to be classically efficient.With noise beyond loss, noisy probabilities may become too close to an easy distribution for the cited techniques to establish hardness.Source: The complexity of noisy and… · p. 7

High-dimensional GBS and evidence for hardness

  • Arbitrary programmable interferometers require deep circuits whose loss grows exponentially with mode count, while shallow local 1D circuits are efficiently simulable.The proposed response is shallow depth with long-range interactions, which can retain substantial entanglement while reducing noise buildup.Source: High-dimensional GBS and evidence for… · p. 8

A programmable architecture for high-dimensional GBS

  • Optical delay lines of lengths {1, a, a^2, …, a^(D−1)} implement nearest-neighbor interactions on a D-dimensional lattice, with C passes giving C interaction cycles.In a linear circuit diagram, these interactions reach as far as a^(D−1) modes.Source: A programmable architecture for… · p. 9
  • For fixed C, copied delay loops yield sub-exponential loss scaling with mode count, whereas a recirculation loop yields exponential scaling.Estimated transmission exceeds 0.70 for (a = 15, D = 2, C = 2) and 0.74 for (a = 6, D = 3, C = 1).Source: A programmable architecture for… · p. 9
  • Tensor-network contractions and Hafnian-based methods are identified as tools for assessing the classical simulation cost of high-dimensional GBS.For tensor networks, output probability amplitudes are obtained by contracting measurement-outcome vectors with the final-state network.Source: A programmable architecture for… · p. 10

high-dimensional GBS

The authors prove average-case hardness for noisy high-dimensional GBS with a constant number of cycles. Their gate-wise interpolation preserves the restricted-depth setting needed for the reduction.

high-dimensional GBS

  • Gate-wise interpolation supports the average-case reduction because ordinary matrix interpolation need not preserve the architecture's restricted depth.The worst-case hardness argument also applies at limited depth when noise is local and error-detectable.Source: high-dimensional GBS · p. 10
  • For constant-cycle noisy high-dimensional GBS, estimating output probabilities is #P-hard under PH reductions when η ≤ η* and ϵ ≤ 2^-poly.The theorem applies for any constant δ > 3/4.Source: high-dimensional GBS · pp. 10–11

QCA frontier for high-dimensional GBS

The paper combines finite-size benchmarking with asymptotic hardness evidence to assess high-dimensional GBS as a route toward programmable-photonic QCA. Its proposed setup is estimated to outperform the USTC experiment in transmission and reach 216 modes, while several questions about sampling hardness and verification remain open.

QCA frontier for high-dimensional GBS

  • High-dimensional GBS experiments feasible with current optical technology are beyond the biggest supercomputers under the benchmarked simulation algorithms.The comparison uses Hafnian-based and tensor-network algorithms; the authors benchmark a constrained adversary matching a noisy model distribution, which may not be verified against the actual experiment.Source: QCA frontier for high-dimensional GBS · p. 11

DISCUSSION

  • The work pairs asymptotic hardness evidence with benchmarking of known algorithms, providing complementary evidence that a reasonably sized setup would outperform classical supercomputers at this task.The discussion also states that theoretical questions remain outstanding.Source: DISCUSSION · pp. 11–12
  • The hiding property remains an open question for high-dimensional GBS and noisy setups, while proving anti-concentration for boson sampling or GBS also remains unresolved.The authors propose computing second moments that characterize collision probability and may relate to anti-concentration and sample verifiability.Source: DISCUSSION · p. 11
  • Whether the heavy-output generation ratio test used in the USTC experiment can be efficiently spoofed by classical adversaries remains open.The authors identify verification of a non-trivial quantum signal as an important task in demonstrating QCA.Source: DISCUSSION · pp. 11–12
  • A classical algorithm for high-dimensional boson sampling in certain regimes is not applicable to the proposed architecture, and extending it is open.The cited algorithm is described in Ref..Source: DISCUSSION · p. 12
  • Hardness results for output probabilities under photon loss do not address other possible noise sources, including mode mismatch, multiple Schmidt modes, phase drift, and detector dark counts.The authors identify these as natural subjects for further investigation.Source: DISCUSSION · p. 12
  • Around 40% transmission is estimated for a programmable setup with 216 total modes and mean detected photon number 80.The authors describe this as enabling the largest QCA demonstration yet; the estimate assumes reasonable component-loss values.Source: DISCUSSION · p. 12

Computational task: Sampling from lossy GBS with finite

The section benchmarks classical simulation under assumptions chosen to favor the classical adversary, then compares the resulting costs with high-dimensional GBS experiments. It explains how photon-number cut-offs and loss affect the simulations, and estimates Hafnian-based runtimes on powerful supercomputers.

Fock cut-off

  • The Fock cut-off sets the retained photon-number levels per mode and simulation cost; the authors use a cut-off of 4 as a conservative estimate despite its inaccuracy.A cut-off of 3 yields highly inaccurate beam-splitter simulations, while higher cut-offs are more accurate but more expensive.Source: Fock cut-off · p. 12
  • Loss contracts the photon-number mean and variance with transmission η, shifting the distribution toward lower photon numbers and making lossy distributions easier to simulate.The displayed mean and variance are E(n) = ηM sinh^2 r and Var(n) = ηM sinh^2 r(1 + η[1 + 2 sinh^2 r]).Source: Fock cut-off · p. 13
  • The benchmark favors classical simulation by using a low cut-off, pure-state calculations, low photon numbers, and computation-time estimates rather than sampling.The authors argue that pure-state and mixed-state GBS have the same complexity for calculating a number of pure-state amplitudes proportional to the mode count.Source: Fock cut-off · p. 13

Hafnian-based algorithms

  • For general matrices, Hafnian calculation scales as O(poly(n)2^n/2), and the task-based implementation runs about 5× faster than the cited OpenMP implementation.The figure benchmarks double-precision Hafnian calculation time against matrix size.Source: Hafnian-based algorithms · p. 14, Figure 4 · p. 14
  • Fugaku would require around 14 hours to compute a 100 × 100 Hafnian, so photon-number distributions with significant support above 100 imply many costly probability amplitudes.The benchmark uses the best-known O(n^3 2^n/2) scaling for matrices without special structure.Source: Hafnian-based algorithms · p. 14
  • 6.8 × 10^15 seconds would be required to match the samples from a 10 KHz quantum device; the estimated classical cost is on par with the USTC experiment, while high-dimensional GBS is programmable and closer to the collision-free regime.The comparison assumes 3 dB of loss and the stated high-dimensional GBS instance.Source: Hafnian-based algorithms · pp. 14–15
  • For the considered USTC setup, a hypothetical PNR distribution has mean and standard deviation 83.3 ± 20.1 photons over 100 modes, compared with 85.2 ± 13.9 over 216 modes for the Figure 3 instance.The USTC estimate assumes transmission η = 0.3.Source: Hafnian-based algorithms · p. 15

Tensor networks methods

Tensor-network simulations are feasible for two-dimensional lossy GBS at 200 modes, while the reported three-dimensional benchmark projects a much larger cost. The hiding analysis gives analytical evidence in extreme regimes and numerical evidence across the range N ≤ K ≤ M, with a stated boundary when there is no short side.

Tensor networks methods

  • A 216-mode, 200-second 3-D experiment is estimated to take ∼10^20 seconds to simulate on Fugaku.The benchmark table covers D = 3 instances with minimal Fock-space cut-off c = 4.Source: Table I · p. 15, Tensor networks methods · p. 15
  • Slicing reduces tensor-contraction memory use at the cost of slower computation, so contraction paths and available memory shape simulation estimates.The paper notes that finding optimal contraction paths is NP-hard and performing contractions is #P-hard.Source: Tensor networks methods · p. 15
  • Tensor-network algorithms can simulate two-dimensional lossy GBS experiments on 200 modes in a reasonable amount of time.For D = 2 and one cycle, a = 14 gives a mean detected photon number near 80, and the estimated contraction takes under 100 microseconds on Fugaku.Source: Tensor networks methods · p. 15

EVIDENCE FOR HIDING IN GBS

  • Conjecture 6 predicts that the symmetric products of Haar-unitary submatrices approach the corresponding Gaussian symmetric-product ensemble for N ≤ K ≤ M.The conjectured distributional relation captures the hiding property for GBS.Source: EVIDENCE FOR HIDING IN GBS · pp. 18–19
  • For K = M, total-variation distance increases with N but decreases as N becomes smaller relative to M; in the collision-free regime, varying K has little effect.These numerical observations support the corresponding convergence claims for the symmetric-matrix ensembles.Source: EVIDENCE FOR HIDING IN GBS · p. 20
  • Analytical evidence supports the conjecture at K = N and K = M, while numerical evidence supports it for intermediate K.The numerical evidence concerns an inverse-polynomial total-variation-distance bound across N ≤ K ≤ M.Source: EVIDENCE FOR HIDING IN GBS · pp. 19–20
  • The conjecture does not apply when N ∈ Ω(M), where the submatrices lack a short side and the compared distributions can be far apart.The cited discussion relates this boundary to the failure of the conjectured statement in that regime.Source: EVIDENCE FOR HIDING IN GBS · p. 20

AVERAGE-CASE HARDNESS OF COMPUTING GBS OUTPUT PROBABILITIES

This section formulates average-case hardness for computing GBS output probabilities through squared Hafnians of Gaussian symmetric products. Its proof strategy uses an oracle for the Gaussian-distributed problem to address a worst-case task.

AVERAGE-CASE HARDNESS OF COMPUTING GBS OUTPUT PROBABILITIES

  • The target is #P-hardness of computing GBS output probabilities, expressed as approximating squared Hafnians of Gaussian symmetric products.The problem is to estimate |Haf(XXT)|2 to additive error ϵ with probability at least δ over Gaussian X.Source: AVERAGE-CASE HARDNESS OF COMPUTING GBS… · p. 20
  • The proof proceeds by using an oracle for the Gaussian squared-Hafnian problem to approximate a worst-case instance.The supplied proof outline says the first step establishes that the oracle can approximate the worst-case quantity; the next step forms the worst-to-average-case reduction.Source: AVERAGE-CASE HARDNESS OF COMPUTING GBS… · p. 20
  • The reduction connects average-case Gaussian inputs to squared-Hafnian computation for arbitrary matrices.Source: AVERAGE-CASE HARDNESS OF COMPUTING GBS… · p. 20

Worst-case hardness

The section establishes worst-case #P-hardness for approximating squared Hafnians of matrices YYT. The argument reduces squared permanents to squared Hafnians and represents the resulting symmetric matrices in the required form.

Worst-case hardness

  • Additive error ϵ ≤ 1/(2M^N) suffices for worst-case #P-hardness of squared-Hafnian computation.The proof converts an approximation at this precision into an exact squared-Hafnian computation.Source: Worst-case hardness · pp. 20–21
  • The reduction encodes a squared permanent as the squared Hafnian of a corresponding block matrix, then factors that symmetric matrix as XXT.The factorization uses a Takagi decomposition and pads with zero columns when needed.Source: Worst-case hardness · pp. 20–21
  • The hardness argument also holds when N is polynomial in K, by embedding a square matrix in CK×K and appending zero rows.Source: Worst-case hardness · p. 21

Worst-to-average equivalence

The section reduces worst-case squared-Hafnian computation to an average-case Gaussian oracle using polynomial interpolation. The robust Berlekamp-Welch procedure reconstructs the polynomial from mostly successful queries, under stated error and success-probability conditions.

Worst-to-average equivalence

  • Theorem 8 states that the Gaussian squared-Hafnian problem is #P-hard under PH reductions for ϵ ≤ O(exp[−6N log N − Ω(N)]) and constant δ > 3/4.Source: Worst-to-average equivalence · p. 21
  • Polynomial interpolation uses p(t) = |Haf(X(t)XT(t))|2, querying near-Gaussian instances and evaluating at t = 1 to recover the worst-case squared Hafnian.The robust Berlekamp-Welch algorithm reconstructs the polynomial when most queried values are correct.Source: Worst-to-average equivalence · p. 22
  • Choosing the oracle error sufficiently small lets the reduction compute the worst-case squared Hafnian to additive error O(1/M^N), the precision used in the hardness argument.Source: Worst-to-average equivalence · p. 22

AVERAGE-CASE HARDNESS OF COMPUTING NOISY GBS OUTPUT PROBABILITIES

The section establishes average-case hardness for noisy GBS output probabilities under a loss threshold. Its reductions use error detection and polynomial interpolation to connect noisy probabilities to worst-case-hard ideal probabilities.

AVERAGE-CASE HARDNESS OF COMPUTING NOISY GBS OUTPUT PROBABILITIES

  • For η ≤ η∗, δ > 3/4, and ϵ ≤ 2^-p(N), (ϵ, η)-NOISYGBS-PROBABILITY is #P-hard under PH reductions.The lemma asserts the existence of a polynomial p(N) and a loss threshold η∗.Source: AVERAGE-CASE HARDNESS OF COMPUTING… · p. 22
  • Below a noise threshold, error detection provides a fixed heralding outcome whose conditioned distribution is exponentially close to the target noiseless distribution.The heralding outcome flags the no-error event, whose probability is exponentially small and approximately (1 − η)^O(Md).Source: AVERAGE-CASE HARDNESS OF COMPUTING… · pp. 22–23
  • Computing noisy output probabilities to additive error O(2^-poly(N)(1 − η)^O(Md)) is #P-hard, following the error-detection connection to ideal probabilities.The passage establishes worst-case hardness for this additive-error scale.Source: AVERAGE-CASE HARDNESS OF COMPUTING… · p. 23
  • Noisy output probabilities remain polynomial in circuit gate entries, enabling worst-to-average-case interpolation with a robust Berlekamp-Welch algorithm.The reduction interpolates each gate along a Cayley path from an average-case instance to a worst-case-hard instance.Source: AVERAGE-CASE HARDNESS OF COMPUTING… · p. 23

AVERAGE-CASE HARDNESS OF COMPUTING NOISY PROBABILITIES IN HIGH-DIMENSIONAL GBS

For high-dimensional GBS, the section extends noisy-probability hardness arguments using amplitude-preserving reductions and robust interpolation. It also gives computational procedures and moments for total photon number under loss.

AVERAGE-CASE HARDNESS OF COMPUTING NOISY PROBABILITIES IN HIGH-DIMENSIONAL GBS

  • An amplitude-preserving reduction connects BQP output amplitudes to high-dimensional GBS, supporting worst-case noisy-probability hardness below a constant noise threshold.The section distinguishes this #P-hardness argument from post-selection alone, which implies PP-hardness of strong simulation.Source: AVERAGE-CASE HARDNESS OF COMPUTING… · p. 23
  • Cayley interpolation, variable rescaling, and robust Berlekamp-Welch strengthen the average-case hardness argument for noisy high-dimensional GBS probabilities.These techniques exploit polynomial structure in output probabilities.Source: AVERAGE-CASE HARDNESS OF COMPUTING… · p. 23

TOTAL PHOTON NUMBER DISTRIBUTION

  • When η = 1, odd photon-number probabilities vanish; moments remain polynomial-time computable even when losses are nonuniform.The lossless limit is identified as the well-known limit of the distribution.Source: TOTAL PHOTON NUMBER DISTRIBUTION · p. 24
  • For pure-state GBS, total photon-number distributions can be computed by convolving the input modes’ distributions; under uniform loss, E(n) = ηM sinh^2 r and Var(n) = ηM sinh^2 r[1 + η(1 + 2 sinh^2 r)].The moment formulas apply to M identical squeezed states with squeezing parameter r and transmission η.Source: TOTAL PHOTON NUMBER DISTRIBUTION · p. 24
Loading 2102.12474v3…