54 citations · 113 across the 14 of their papers we have counts for
15 papers
Quantum Sampling of Random Spanning Trees via Amortized Data Structures
Yassine Hamoudi, Adrian Tanasa, Shrinidhi Teganahally Sridhara
We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to…
Dequantization Barriers for Guided Stoquastic Hamiltonians
Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, which cannot be efficiently sampled by any classical algorith…
A Brief Introduction to Quantum Query Complexity
Yassine Hamoudi
Quantum query complexity is a fundamental model for analyzing the computational power of quantum algorithms. It has played a key role in characterizing quantum speedups, from early…
Quantum speedup of non-linear Monte Carlo problems
Jose Blanchet, Yassine Hamoudi, Mario Szegedy +1
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 cla…
The NISQ Complexity of Collision Finding
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This p…
Preparing Many Copies of a Quantum State in the Black-Box Model
Yassine Hamoudi
We describe a simple quantum algorithm for preparing copies of an -dimensional quantum state whose amplitudes are given by a quantum oracle. Our result extends a previous wo…
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 spee…
Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
Arjan Cornelissen, Yassine Hamoudi, Sofiene 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…
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming
Jonathan Allcock, Yassine Hamoudi, Antoine Joux +2
Subset-Sum is an NP-complete problem where one must decide if a multiset of integers contains a subset whose elements sum to a target value . The best-known classical and qu…
Quantum Sub-Gaussian Mean Estimator
Yassine Hamoudi
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…
Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
Yassine Hamoudi, Frédéric Magniez
We study the problem of finding collision pairs in a random function by using a quantum computer. We prove that the number of queries to the function…
Quantum algorithms for hedging and the learning of Ising models
Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray +3
A paradigmatic algorithm for online learning is the Hedge algorithm by Freund and Schapire. An allocation into different strategies is chosen for multiple rounds and each round inc…
Quantum and Classical Algorithms for Approximate Submodular Function Minimization
Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis +1
Submodular functions are set functions mapping every subset of some ground set of size into the real numbers and satisfying the diminishing returns property. Submodular minimiz…
Quantum Chebyshev's Inequality and Applications
Yassine Hamoudi, Frédéric Magniez
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…
Simultaneous Multiparty Communication Complexity of Composed Functions
Yassine Hamoudi
In the Number On the Forehead (NOF) multiparty communication model, players want to evaluate a function on some input $(x_1,\dots,…