Exponential improvements to the average-case hardness of BosonSampling

• URL: http://arxiv.org/abs/2411.04566v2
• Date: Thu, 04 Sep 2025 00:11:55 GMT
• Title: Exponential improvements to the average-case hardness of BosonSampling
• Authors: Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez,
• Abstract summary: We show that additive-error estimates to output probabilities of random BosonSampling experiments are $#P$-hard for any $delta>0$.<n>We also show, for the first time, a hardness of average-case classical sampling result for BosonSampling.
• Score: 0.4515414068394328
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that $e^{-n\log{n}-n-O(\log n)}$ additive-error estimates to the output probability of most random BosonSampling experiments are $\#P$-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that $e^{-n\log n-n-O(n^\delta)}$ additive-error estimates to output probabilities of most random BosonSampling experiments are $\#P$-hard for any $\delta>0$, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now "merely" to show that the $O(n^\delta)$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-2^{-\tilde{\mathstrut O}(N^{1/3})}$ for input size $N$, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.

Related papers

• Beyond Boson Sampling: Higher Spin Sampling as a Practical Path to Quantum Supremacy [0.0]
  We introduce spin sampling for arbitrary spin-$S$ states as a practical path to quantum supremacy.<n>We identify a quasi-linear scaling relation between the number of sites $m$ and the number of spins $n$ as $msim n1+epsilon$.<n>This suggests that, within a spin system, an equivalent Fock-state boson sampling task in the linear mode region is experimentally feasible with reduced resource requirements.
  arXiv  Detail & Related papers  (2025-05-12T07:57:21Z)
• Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity [0.0]
  We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset.<n>In a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation.
  arXiv  Detail & Related papers  (2025-02-12T19:00:10Z)
• Diffusion at Absolute Zero: Langevin Sampling Using Successive Moreau Envelopes [conference paper] [52.69179872700035]
  We propose a novel method for sampling from Gibbs distributions of the form $pi(x)proptoexp(-U(x))$ with a potential $U(x)$. Inspired by diffusion models we propose to consider a sequence $(pit_k)_k$ of approximations of the target density, for which $pit_kapprox pi$ for $k$ small and, on the other hand, $pit_k$ exhibits favorable properties for sampling for $k$ large.
  arXiv  Detail & Related papers  (2025-02-03T13:50:57Z)
• On the sampling complexity of coherent superpositions [0.4972323953932129]
  We consider the problem of sampling from the distribution of measurement outcomes when applying a POVM to a superposition.<n>We give an algorithm which $-$ given $O(chi |c|2 log1/delta)$ such samples and calls to oracles to evaluate the probability density functions.
  arXiv  Detail & Related papers  (2025-01-28T16:56:49Z)
• Experimental lower bounds on entanglement entropy without twin copy [0.0]
  We calculate the Shannon entropy $S_ABX$ associated with the experimental measurements of adiabatically prepared ground states. We show several examples for which, in good approximation, $S_AvNpropto (2S_AX-S_ABX)$ with a constant of proportionality slightly larger than one.
  arXiv  Detail & Related papers  (2024-04-15T17:02:17Z)
• Boson Sampling from Non-Gaussian States [0.0]
  We study Boson sampling from general, single-mode states using a scheme that can generate any such state. We derive a formula that can be used to calculate the output photon number probabilities of these states after they travel through a linear interferometer.
  arXiv  Detail & Related papers  (2024-03-25T20:49:19Z)
• Transition of Anticoncentration in Gaussian Boson Sampling [0.0]
  We develop a graph-theoretic framework for analyzing the moments of the Gaussian Boson Sampling distribution. We show that when the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration.
  arXiv  Detail & Related papers  (2023-12-13T19:00:00Z)
• Classical sampling from noisy Boson Sampling and the negative probabilities [0.0]
  It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy Boson Sampling can be approximately sampled from approximation in a time in the total number of bosons. The quantum probability factors in a convex-sum expression, if truncated to a finite order of multiboson interference, have, on average, a finite amount of negativity in a random interferometer. The conclusion that the negativity issue is inherent to all efficient classicals to noisy Boson Sampling may be premature.
  arXiv  Detail & Related papers  (2023-07-11T15:33:37Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. We study the maximum entropy exploration problem two different types. For visitation entropy, we propose a game-theoretic algorithm that has $widetildemathcalO(H3S2A/varepsilon2)$ sample complexity. For the trajectory entropy, we propose a simple algorithm that has a sample of complexity of order $widetildemathcalO(mathrmpoly(S,
  arXiv  Detail & Related papers  (2023-03-14T16:51:14Z)
• Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent [0.0]
  We consider the hardness of computing additive approximations to output probabilities of random quantum circuits. For Haar random circuits with $m$ gates, we show $mathsfcoC_=P$ hardness of average-case additive approximations to an imprecision of $2-O(m)$. For random $p=1$ QAOA and IQP circuits, we show that in the average-case, it is $mathsfcoC_=P$ hard to approximate the output probability to within an additive error of $2-O(n)$
  arXiv  Detail & Related papers  (2022-06-12T02:35:51Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.