Classical sampling from noisy Boson Sampling and the negative probabilities

• URL: http://arxiv.org/abs/2307.05344v1
• Date: Tue, 11 Jul 2023 15:33:37 GMT
• Title: Classical sampling from noisy Boson Sampling and the negative probabilities
• Authors: Valery Shchesnovich
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is known that, by accounting for the multiboson interferences up to a finite order, the output distribution of noisy Boson Sampling, with distinguishability of bosons serving as noise, can be approximately sampled from in a time polynomial in the total number of bosons. The drawback of this approach is that the joint probabilities of completely distinguishable bosons, i.e., those that do not interfere at all, have to be computed also. In trying to restore the ability to sample from the distinguishable bosons with computation of only the single-boson probabilities, one faces the following issue: 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 truncated distribution does become a proper one, while allowing for sampling from it in a polynomial time, only in a vanishing domain close to the completely distinguishable bosons. Nevertheless, the conclusion that the negativity issue is inherent to all efficient classical approximations to noisy Boson Sampling may be premature. I outline the direction for a whole new program, which seem to point to a solution. However its success depends on the asymptotic behavior of the symmetric group characters, which is not known.

Related papers

• Sampling through Algorithmic Diffusion in non-convex Perceptron problems [2.860608352191896]
  We introduce a formalism based on the replica method to characterize the feasibility in terms of a few order parameters. We show that, in the case of the perceptron problem with negative stability, approximate uniform sampling is achievable across the entire replica region. In contrast, for the binary perceptron, uniform sampling via diffusion invariably fails due to the overlap gap property exhibited by the typical set of solutions.
  arXiv  Detail & Related papers  (2025-02-22T16:43:01Z)
• Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
  We consider the problem of sampling a multimodal distribution with a Markov chain given a small number of samples from the stationary measure. We show that if the Markov chain has a $k$th order spectral gap, samples from the stationary distribution will efficiently generate a sample whose conditional law is $varepsilon$-close in TV distance to the stationary measure.
  arXiv  Detail & Related papers  (2024-11-14T01:37:02Z)
• 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)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• On classical simulation algorithms for noisy Boson Sampling [2.8655318786364408]
  We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai Kindler.
  arXiv  Detail & Related papers  (2023-01-27T04:42:59Z)
• Multi-Label Quantification [78.83284164605473]
  Quantification, variously called "labelled prevalence estimation" or "learning to quantify", is the supervised learning task of generating predictors of the relative frequencies of the classes of interest in unsupervised data samples. We propose methods for inferring estimators of class prevalence values that strive to leverage the dependencies among the classes of interest in order to predict their relative frequencies more accurately.
  arXiv  Detail & Related papers  (2022-11-15T11:29:59Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• Boson Sampling for Generalized Bosons [0.7698863100388946]
  Examples of "generalized bosons" include boson pairs and spins. We propose implementations of generalized boson sampling in circuit-QED and ion-trap platforms.
  arXiv  Detail & Related papers  (2022-04-18T16:29:53Z)
• Boson sampling cannot be faithfully simulated by only the lower-order multi-boson interferences [0.0]
  I show that the output data from any such classical simulations can be efficiently distinguished from that of the quantum device they try to simulate. I present more accessible account of the main result enhanced by additional insight on the contribution from the higher-order multi-boson interferences in presence of noise.
  arXiv  Detail & Related papers  (2022-04-16T12:53:10Z)
• 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)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Distributed, partially collapsed MCMC for Bayesian Nonparametrics [68.5279360794418]
  We exploit the fact that completely random measures, which commonly used models like the Dirichlet process and the beta-Bernoulli process can be expressed as, are decomposable into independent sub-measures. We use this decomposition to partition the latent measure into a finite measure containing only instantiated components, and an infinite measure containing all other components. The resulting hybrid algorithm can be applied to allow scalable inference without sacrificing convergence guarantees.
  arXiv  Detail & Related papers  (2020-01-15T23:10:13Z)

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.