About Me

I am a Simons Quantum Postdoctoral Fellow, hosted by Umesh Vazirani. Previously, I completed my Ph.D. at IRIF, Université de Paris advised by Frédéric Magniez and Miklos Santha.

Research Interest

My main research interest is to understand the impact of quantum mechanics on algorithm design and computational complexity theory. I have contributed to new quantum algorithms for optimization, statistical analysis, streaming data, random sampling and graph problems. I have worked on lower bounds in query complexity with applications to cryptography. I am also interested in computational learning theory and communication complexity.

scholar orcid cv yt


  1. Classical and Quantum Dynamic Programming for Subset-Sum and Variants
    Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, Miklos Santha
    Proceedings of the 30th European Symposium on Algorithms (ESA 2022).
    [PDF] [arXiv]

  2. Preparing many copies of a quantum state in the black-box model
    Yassine Hamoudi
    Physical Review A, vol. 105, p. 062440 (2022).
    [PDF] [Journal]

  3. Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
    Arjan Cornelissen, Yassine Hamoudi, Sofiene Jerbi
    Contributed talk at the 25th Conference on Quantum Information Processing (QIP 2022).
    Proceedings of the 54th Symposium on Theory of Computing (STOC 2022).
    [PDF] [arXiv] [Conference]

  4. Quantum Sub-Gaussian Mean Estimator
    Yassine Hamoudi
    Proceedings of the 29th European Symposium on Algorithms (ESA 2021).
    [PDF] [arXiv] [Conference]

  5. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
    Yassine Hamoudi, Frédéric Magniez
    Proceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021).
    medal Outstanding Paper Award.
    [PDF] [arXiv] [Conference]

  6. Quantum Algorithms for Hedging and the Learning of Ising Models
    Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, Miklos Santha
    Physical Review A, vol. 103, p. 012418 (2021).
    [PDF] [arXiv] [Journal]

  7. Quantum and Classical Algorithms for Approximate Submodular Function Minimization
    Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, Miklos Santha
    Quantum Information & Computation, vol. 19, pp. 1325–1349 (2019).
    [PDF] [arXiv] [Journal]

  8. Quantum Chebyshev’s Inequality and Applications
    Yassine Hamoudi, Frédéric Magniez
    Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019).
    [PDF] [arXiv] [Conference]

  9. Simultaneous Multiparty Communication Complexity of Composed Functions
    Yassine Hamoudi
    Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
    [PDF] [arXiv] [Conference]

Other Manuscripts



Teaching Assistant


I was in charge of organizing the Algorithms and Complexity seminar at IRIF from 2017 to 2021.

I have been a conference reviewer for: FOCS (x2), FSTTCS (x2), ICALP (x3), ITCS (x1), MFCS (x3), QIP (x3), SAC (x1), SoCG (x1), SODA (x3), STACS (x2), TQC (x3).

I have been a journal reviewer for: Algorithmica, IEEE Transactions on Computers (TC), International Journal of Quantum Information (IJQI), Quantum, Quantum Information & Computation (QIC).

I am in the program committee of QTML 2022.

Theme's credit