We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators [Lugosi and Mendelson, 2019] to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, [Heinrich, 2004] ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there does exist a quantum estimator that outperforms any classical estimator. More precisely, we prove that the approximation error can be decreased by a factor of about the square root of the ratio between the dimension and the sample complexity. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as linear amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis is also deeply rooted in proving concentration inequalities for multivariate truncated statistics. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning.
We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators [Lugosi and Mendelson, 2019] to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, [Heinrich, 2004] ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there does exist a quantum estimator that outperforms any classical estimator. More precisely, we prove that the approximation error can be decreased by a factor of about the square root of the ratio between the dimension and the sample complexity. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as linear amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis is also deeply rooted in proving concentration inequalities for multivariate truncated statistics. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning.
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 [Brassard et al., 2002; Brassard et al., 2011], or that require prior information on the variance [Heinrich, 2002; Montanaro, 2015; Hamoudi and Magniez, 2019]. As an application, we obtain new quantum algorithms for the (ε,δ)-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.
In this work, we present an efficient algorithm for multivariate mean value estimation. Our algorithm outperforms previous work by polylog factors and nearly saturates the known lower bound. More formally, given a random vector X of dimension d, we find an algorithm that uses O(nlogδd) samples to find a mean estimate that μ~ that differs from the true mean μ by ntr Σ in ℓ∞ norm and hence nd tr Σ in ℓ2 norm, where Σ is the covariance matrix of the components of the random vector. We also presented another algorithm that uses smaller memory but costs an extra d41 in complexity. Consider the Grover operator, the unitary operator used in Grover's algorithm. It contains an oracle that uses a ±1 phase for each candidate for the search space. Previous work has demonstrated that when we substitute the oracle in Grover operator with generic phases, it ended up being a good mean value estimator in some mathematical notion. We used this idea to build our algorithm. Our result remains not exactly optimal due to a logδd term in our complexity, as opposed to something nicer such as logδ1; This comes from the phase estimation primitive in our algorithm. So far, this primitive is the only major known method to tackle the problem, and moving beyond this idea seems hard. Our results demonstrates that the methodology with generalized Grover operator can be used develop the optimal algorithm without polylog overhead for different tasks relating to mean value estimation.
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 (ϵ,δ)-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.
There is growing interest in constructing quantum devices that control increasingly large numbers of quantum systems. There is a tremendous need for methods that can measure the quality and other properties of these devices. Such measurements often amount to learning the expectation value of a quantum observable with respect to the quantum state of the device. Learning expectation values is also a key component in many well-known applications such as quantum machine learning and quantum optimization algorithms. Because of the large system sizes involved, it is essential to find methods for learning expectation values that are efficient with respect to the system size. Existing methods that have rigorous guarantees and are practical to implement are often not optimal for observables of interest. Other methods are heuristic, or require the use measurement protocols that are challenging to implement experimentally with current technology. In this study, we propose an estimation procedure, The Optimal Observable expectation value Learner or TOOL, that can learn the expectation values of observables using the outcomes of any given measurement protocol. We show that there is a seminorm on the set of all observables, which we call the minimax norm, that characterizes the smallest possible estimation error for learning a given observable using the outcomes of a given non-adaptive measurement protocol to a specified confidence level in the worst case over all states. We prove that TOOL is minimax optimal for every observable by showing that it can achieve an estimation error to within a small constant factor of the minimax norm. For many applications, one wishes to learn the expectation value of more than one observable from the same experiment. A popular method for learning the expectation values of one or many observables with rigorous guarantees is classical shadows. Classical shadows has near-optimal performance in the worst case over all observables. We prove that TOOL always performs at least as well as classical shadows. Moreover, we show by example that TOOL dramatically outperforms classical shadows for many observables of interest. This highlights the need to characterize the optimal performance for the task of simultaneously learning the expectation values of many observables. Under a mild assumption, we give such a characterization using the minimax norm and prove that TOOL is nearly minimax optimal for this task. We also study the applications of TOOL to fidelity estimation. Using experimental data from a trapped-ion quantum computer, we show that TOOL performs well in practice and matches the estimates obtained from Maximum Likelihood Estimation (MLE), but with rigorous guarantees on the estimation error unlike MLE. We also compare TOOL with another popular method called direct fidelity estimation, which estimates the fidelity by judiciously sampling Pauli observables and measuring them. We show that there is a different importance sampling scheme for Pauli measurements for which TOOL performs as well as, or better than, direct fidelity estimation. Since TOOL constructs an estimator using only the observable, the measurement protocol, and the confidence level, it provides the flexibility to perform estimation for experiments that have already been performed and experiments that will be performed in the future. Similarly, since the minimax norm can be computed beforehand, it can be used to compare the performance of different measurement protocols and allow minimax optimal design of experiments.
We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension d of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index p>4/3, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (QNSGD), which finds an ε-stationary point using O~(dε−2p−25p−4) queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (QPSGD), which computes a solution with ε-optimal solution using O~(dε−2p−23p−2+ε−2) queries in expectation. These sharper bounds improve upon the classical lower bounds Ω(ε−p−13p−2) for nonconvex problems and Ω(ε−p−1p) for convex problems in the low-dimensional regimes d≲ε−p−1p and d≲ε−p−12−p, respectively.
We consider the problem of estimating the expected outcomes of Monte Carlo processes whose outputs are described by multidimensional random variables. We tightly characterize the quantum query complexity of this problem for various choices of oracle access to the Monte Carlo process and various normalization conditions on its output variables and the estimates to be made. More specifically, we design quantum algorithms that provide a quadratic speed-up in query complexity with respect to the precision of the resulting estimates and show that these complexities are asymptotically optimal in each of our scenarios. Interestingly, we find that these speed-ups with respect to the precision come at the cost of a (up to exponential) slowdown with respect to the dimension of the Monte Carlo random variables, for most of the parameter settings we consider. We also describe several applications of our algorithms, notably in the field of machine learning, and discuss the implications of our results.