Author name cluster

Yassine Hamoudi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

NeurIPS Conference 2025 Conference Paper

Quantum speedup of non-linear Monte Carlo problems

Jose Blanchet
Yassine Hamoudi
Mario Szegedy
Guanyang Wang

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.

PDF Details

SODA Conference 2023 Conference Paper

A Sublinear-Time Quantum Algorithm for Approximating Partition Functions

Arjan Cornelissen
Yassine Hamoudi

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.

Details

STOC Conference 2022 Conference Paper

Near-optimal Quantum algorithms for multivariate mean estimation

Arjan Cornelissen
Yassine Hamoudi
Sofiène Jerbi

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.

Details

MFCS Conference 2018 Conference Paper

Simultaneous Multiparty Communication Protocols for Composed Functions

Yassine Hamoudi

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.

Details