Related papers: Quantum Sub-Gaussian Mean Estimator

Quantum Sub-Gaussian Mean Estimator

URL: http://arxiv.org/abs/2108.12172v1
Date: Fri, 27 Aug 2021 08:34:26 GMT
Title: Quantum Sub-Gaussian Mean Estimator
Authors: Yassine Hamoudi
Abstract summary: We present a new quantum algorithm for estimating the mean of a real-valued random variable. Our estimator achieves a nearly-optimal quadratic speedup over the number of classical i.i.d. samples.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present a new quantum algorithm for estimating the mean of a real-valued random variable obtained as the output of a quantum computation. Our estimator achieves a nearly-optimal quadratic speedup over the number of classical i.i.d. samples needed to estimate the mean of a heavy-tailed distribution with a sub-Gaussian error rate. This result subsumes (up to logarithmic factors) earlier works on the mean estimation problem that were not optimal for heavy-tailed distributions [BHMT02,BDGT11], or that require prior information on the variance [Hein02,Mon15,HM19]. As an application, we obtain new quantum algorithms for the $(\epsilon,\delta)$-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.

Related papers

Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
A Quantum Natural Gradient (QNG) algorithm for optimization of variational quantum circuits has been proposed recently. In this study, we employ the Langevin equation with a QNG force to demonstrate that its discrete-time solution gives a generalized form, which we call Momentum-QNG.
arXiv Detail & Related papers (2024-09-03T15:21:16Z)
Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
arXiv Detail & Related papers (2023-10-17T17:55:32Z)
Noise-Free Sampling Algorithms via Regularized Wasserstein Proximals [3.4240632942024685]
We consider the problem of sampling from a distribution governed by a potential function. This work proposes an explicit score based MCMC method that is deterministic, resulting in a deterministic evolution for particles.
arXiv Detail & Related papers (2023-08-28T23:51:33Z)
Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
arXiv Detail & Related papers (2023-02-13T19:57:17Z)
Importance sampling for stochastic quantum simulations [68.8204255655161]
We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
arXiv Detail & Related papers (2022-12-12T15:06:32Z)
A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time. This is the first speed-up of this type to be obtained over the seminal nearly-linear time of vStefankovivc, Vempala and Vigoda.
arXiv Detail & Related papers (2022-07-18T14:41:48Z)
Dual-Frequency Quantum Phase Estimation Mitigates the Spectral Leakage of Quantum Algorithms [76.15799379604898]
Quantum phase estimation suffers from spectral leakage when the reciprocal of the record length is not an integer multiple of the unknown phase. We propose a dual-frequency estimator, which approaches the Cramer-Rao bound, when multiple samples are available.
arXiv Detail & Related papers (2022-01-23T17:20:34Z)
Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. We apply this algorithm to rate distortion and its variants including the quantum setting.
arXiv Detail & Related papers (2022-01-07T13:33:28Z)
Near-Optimal Quantum Algorithms for Multivariate Mean Estimation [0.0]
We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable. We exploit a variety of additional algorithmic techniques such as amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation.
arXiv Detail & Related papers (2021-11-18T16:35:32Z)
Quantum state preparation with multiplicative amplitude transduction [0.0]
Two variants of the algorithm with different emphases are introduced. One variant uses fewer qubits and no controlled gates, while the other variant potentially requires fewer gates overall. A general analysis is given to estimate the number of qubits necessary to achieve a desired precision in the amplitudes of the computational basis states.
arXiv Detail & Related papers (2020-06-01T14:36:50Z)
Statistical Inference for Model Parameters in Stochastic Gradient Descent [45.29532403359099]
gradient descent coefficients (SGD) has been widely used in statistical estimation for large-scale data due to its computational and memory efficiency. We investigate the problem of statistical inference of true model parameters based on SGD when the population loss function is strongly convex and satisfies certain conditions.
arXiv Detail & Related papers (2016-10-27T07:04:21Z)

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