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
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.
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]
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]
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]
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]
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]
Quantum Sub-Gaussian Mean Estimator
Yassine Hamoudi
Proceedings of the 29th European Symposium on Algorithms (ESA 2021).
[PDF] [arXiv] [Conference]
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).
Outstanding Paper Award.
[PDF] [arXiv] [Conference] [Journal]
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]
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]
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]
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]
Program committee member: QTML 2022, TQC 2023, TQC 2024.
Conference reviewer: ESA 23; FCT 23; FOCS 20,21; FSTTCS 20,21; ICALP 19,21,22,23; ITCS 20; MFCS 18,21,22,23; QIP 21,22,23,24; SAC 21; SoCG 22; SODA 21,22,23,24; 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 was in charge of organizing the Algorithms and Complexity seminar at IRIF from 2017 to 2021.