The mean of a random variable can be understood as a *linear* functional on the space of probability distributions. Quantum computing is known to provide a quadratic speedup over classical Monte Carlo methods for mean estimation. In this paper, we investigate whether a similar quadratic speedup is achievable for estimating *non-linear* functionals of probability distributions. We propose a \textit{quantum-inside-quantum} algorithm that achieves this speedup for the broad class of nonlinear estimation problems known as nested expectations. Our algorithm improves upon the direct application of the quantum-accelerated multilevel Monte Carlo algorithm introduced by An et. al.. The existing lower bound indicates that our algorithm is optimal up to polylogarithmic factors. A key innovation of our approach is a new sequence of multilevel Monte Carlo approximations specifically designed for quantum computing, which is central to the algorithm's improved performance.

We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space. This is the first speed-up of this type to be obtained over the seminal nearly-linear time algorithm of Štefankovič, Vempala and Vigoda [45]. Our result also preserves the quadratic speed-up in precision and spectral gap achieved in previous work by exploiting the properties of quantum Markov chains. As an application, we obtain new polynomial improvements over the best-known algorithms for computing the partition function of the Ising model, counting the number of k-colorings, matchings or independent sets of a graph, and estimating the volume of a convex body. Our approach relies on developing new variants of the quantum phase and amplitude estimation algorithms that return nearly unbiased estimates with low variance and without destroying their initial quantum state. We extend these subroutines into a nearly unbiased quantum mean estimator that reduces the variance quadratically faster than the classical empirical mean. No such estimator was known to exist prior to our work. These properties, which are of general interest, lead to better convergence guarantees within the paradigm of simulated annealing for computing partition functions. * The full version of the paper can be accessed at http://arxiv.org/abs/2207.08643.

International audience

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 discuss quantum algorithms that calculate numerical integrals and descriptive statistics of stochastic processes. With either of two distinct approaches, one obtains an exponential speed increase in comparison to the fastest known classical deterministic algorithms and a quadratic speed increase in comparison to classical Monte Carlo (probabilistic) methods. We derive a simpler and slightly faster version of Grover's mean algorithm, demonstrate how to apply quantum counting to the problem, develop some variations of these algorithms, and show how both (apparently quite different) approaches can be understood from the same unified framework. Finally, we discuss how the exponential speed increase appears to (but does not) violate results obtained via the method of polynomials, from which it is known that a bounded-error quantum algorithm for computing a total function can be only polynomially more efficient than the fastest deterministic classical algorithm.

In this paper we provide new quantum algorithms with polynomial speed-up for a range of problems for which no such results were known, or we improve previous algorithms. First, we consider the approximation of the frequency moments $F_k$ of order $k \geq 3$ in the multi-pass streaming model with updates (turnstile model). We design a $P$-pass quantum streaming algorithm with memory $M$ satisfying a tradeoff of $P^2 M = \tilde{O}(n^{1-2/k})$, whereas the best classical algorithm requires $P M = Θ(n^{1-2/k})$. Then, we study the problem of estimating the number $m$ of edges and the number $t$ of triangles given query access to an $n$-vertex graph. We describe optimal quantum algorithms that perform $\tilde{O}(\sqrt{n}/m^{1/4})$ and $\tilde{O}(\sqrt{n}/t^{1/6} + m^{3/4}/\sqrt{t})$ queries respectively. This is a quadratic speed-up compared to the classical complexity of these problems. For this purpose we develop a new quantum paradigm that we call Quantum Chebyshev's inequality. Namely we demonstrate that, in a certain model of quantum sampling, one can approximate with relative error the mean of any random variable with a number of quantum samples that is linear in the ratio of the square root of the variance to the mean. Classically the dependency is quadratic. Our algorithm subsumes a previous result of Montanaro [Mon15]. This new paradigm is based on a refinement of the Amplitude Estimation algorithm of Brassard et al. [BHMT02] and of previous quantum algorithms for the mean estimation problem. We show that this speed-up is optimal, and we identify another common model of quantum sampling where it cannot be obtained. For our applications, we also adapt the variable-time amplitude amplification technique of Ambainis [Amb10] into a variable-time amplitude estimation algorithm.

The Number On the Forehead (NOF) model is a multiparty communication game between k players that collaboratively want to evaluate a given function F : X_1 x *s x X_k - > Y on some input (x_1,...,x_k) by broadcasting bits according to a predetermined protocol. The input is distributed in such a way that each player i sees all of it except x_i (as if x_i is written on the forehead of player i). In the Simultaneous Message Passing (SMP) model, the players have the extra condition that they cannot speak to each other, but instead send information to a referee. The referee does not know the players' inputs, and cannot give any information back. At the end, the referee must be able to recover F(x_1,...,x_k) from what she obtained from the players. A central open question in the simultaneous NOF model, called the log n barrier, is to find a function which is hard to compute when the number of players is polylog(n) or more (where the x_i's have size poly(n)). This has an important application in circuit complexity, as it could help to separate ACC^0 from other complexity classes [Håstad and Goldmann, 1991; Babai et al., 2004]. One of the candidates for breaking the log n barrier belongs to the family of composed functions. The input to these functions in the k-party NOF model is represented by a k x (t * n) boolean matrix M, whose row i is the number x_i on the forehead of player i and t is a block-width parameter. A symmetric composed function acting on M is specified by two symmetric n- and kt-variate functions f and g (respectively), that output f o g(M) = f(g(B_1),...,g(B_n)) where B_j is the j-th block of width t of M. As the majority function Maj is conjectured to be outside of ACC^0, Babai et. al. [Babai et al., 1995; Babai et al., 2004] suggested to study the composed function Maj o Maj_t, with t large enough, for breaking the log n barrier (where Maj_t outputs 1 if at least kt/2 bits of the input block are set to 1). So far, it was only known that block-width t = 1 is not enough for Maj o Maj_t to break the log n barrier in the simultaneous NOF model [Babai et al., 2004] (Chattopadhyay and Saks [Chattopadhyay and Saks, 2014] found an efficient protocol for t <= polyloglog(n), but it requires randomness to be simultaneous). In this paper, we extend this result to any constant block-width t > 1 by giving a deterministic simultaneous protocol of cost 2^O(2^t) log^(2^(t+1))(n) for any symmetric composed function f o g (which includes Maj o Maj_t) when there are more than 2^Omega(2^t) log n players.