On the average-case hardness of BosonSampling

• URL: http://arxiv.org/abs/2411.04566v1
• Date: Thu, 07 Nov 2024 09:41:45 GMT
• Title: On the average-case hardness of BosonSampling
• Authors: Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez,
• Abstract summary: Proving the "Gaussian Permanent Estimation" conjecture has become the central question in the theory of quantum advantage. We prove that $e-nlog n -n - O(ndelta)$ additive error estimates to output probabilities of most random BosonSampling experiments are $#P$-hard. Our result allows us to show, for the first time, a hardness of classical sampling result for random BosonSampling experiments.
• Score: 0.13194391758295113
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: BosonSampling is a popular candidate for near-term quantum advantage, which has now been experimentally implemented several times. The original proposal of Aaronson and Arkhipov from 2011 showed that classical hardness of BosonSampling is implied by a proof of the "Gaussian Permanent Estimation" conjecture. This conjecture 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. Proving this conjecture has since become the central question in the theory of quantum advantage. In this work we make progress by proving 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$. In the process, we circumvent all known barrier results for proving the hardness of BosonSampling experiments. This is nearly the robustness needed to prove hardness of BosonSampling -- the remaining hurdle is now "merely" to show that the $n^\delta$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. Our result allows us to show, for the first time, a hardness of classical sampling result for random BosonSampling experiments, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-e^{-O(n)}$, unless the Polynomial Hierarchy collapses.

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.