About Me

Since October 2023, I have been a CNRS researcher in the Quantum Information & Computation group at LaBRI (Université de Bordeaux).

Previously, I was a Quantum Postdoctoral Fellow at the Simons Institute (UC Berkeley) hosted by Umesh Vazirani and a Ph.D. student at IRIF (Université Paris Cité) advised by Frédéric Magniez and Miklos Santha.

Email: ys.hamoudi@gmail.com

Research Interest

My primary research interest is quantum computing. I study the impact of quantum mechanics on algorithm design and computational complexity theory. I have contributed to new quantum algorithms in diverse areas such as optimization, statistical analysis, streaming data, graph problems and cryptanalysis. I am also interested in new algorithmic and lower-bound methods for understanding the interplay between the computational resources available to quantum computers, with a particular interest in time-space tradeoffs.

scholar orcid cv yt

Publications

  1. The NISQ Complexity of Collision Finding
    Yassine Hamoudi, Qipeng Liu, Makrand Sinha
    Proceedings of the 43rd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2024).
    [PDF] [arXiv] [Conference]

  2. A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
    Arjan Cornelissen, Yassine Hamoudi
    Contributed talk at the 26th Conference on Quantum Information Processing (QIP 2023).
    Proceedings of the 34th Symposium on Discrete Algorithms (SODA 2023).
    [PDF] [arXiv] [Conference]

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

  4. 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]

  5. Preparing Many Copies of a Quantum State in the Black-Box Model
    Yassine Hamoudi
    Physical Review A, vol. 105, p. 062440 (2022).
    [PDF] [arXiv] [Journal]

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

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

  8. 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]

  9. 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]

  10. 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]

  11. 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

Talks

Posters

Teaching

Service

Program committee member: QTML 2022, TQC 2023, TQC 2024.

Conference reviewer: ESA 23,24; FCT 23; FOCS 20,21; FSTTCS 20,21; ICALP 19,21,22,23; ITCS 20,25; MFCS 18,21,22,23,24; QIP 21,22,23,24; SAC 21; SoCG 22; SODA 21,22,23,24,25; STACS 21,23,24; STOC 23,24; TQC 22.

Journal reviewer: ACM Transactions on Quantum Computing, Algorithmica, Discrete Mathematics & Theoretical Computer Science, IEEE Transactions on Computers, International Journal of Quantum Information, Mathematics of Operations Research, Quantum, Quantum Information & Computation, SIAM Journal on Computing.

I am the head of the Quantum Information and Computation group at LaBRI since October 2024.

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


Theme's credit