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.
Publications
-
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] -
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]
Other Manuscripts
- Quantum Algorithms for the Monte Carlo Method
PhD Thesis, 2021.
[PDF] [Slides] [Link] - Communication Complexity
Master’s Thesis, 2016.
[PDF] [Slides] - Extracting RDF triples using the Stanford Parser
Master’s Project, 2015.
[PDF] - Balanced Mobiles with applications to phylogenetic trees and Huffman-like problems
Preprint, 2015.
[PDF] [HAL] [Slides] - PSPACE and Continuous Time Models of Computations
Undergraduate internship, 2014.
[PDF (french)] [Slides (french)]
Talks
- The NISQ Complexity of Collision Finding
- Quantum-Classical Tradeoffs in the Random Oracle Model
- COSMIQ Seminar, INRIA, Paris, 30 January 2023 [Slides]
- Quantum Speedups for Computing Expectation Values and Partition Functions
- A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
- Quantum Summer Cluster Workshop, Simons Institute, 11 July 2023 [Slides] [Video]
- QIP 2023, Ghent University, Belgium, 8 February 2023 [Slides] [Video]
- Quantum Information Seminar, LIP6, Paris, 8 December 2022
- GT Info-Quantique, LaBRI, Bordeaux, 6 December 2022
- CAPP Seminar, LIG, Grenoble, 30 November 2022
- QInfo Seminar, École normale supérieure de Lyon, 28 November 2022
- Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming
- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
- Quantum Sub-Gaussian Mean Estimator
- Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
- Quantum and Classical Algorithms for Approximate Submodular Function Minimization
- Quantum Chebyshev’s Inequality and Applications
- ICALP 2019, University of Patras, 9 July 2019 [Slides]
- Centre for Quantum Technologies Seminar, NUS, Singapore, 6 March 2019 [Slides]
- QUDATA Project, IRIF, Paris, 10 January 2019 [Slides]
- Journées Informatique Quantique, LORIA, Nancy, 8 November 2018 [Slides]
- QUANTALGO Workshop, IRIF, Paris, 25 September 2018 [Slides]
- Simultaneous Multiparty Communication Complexity of Composed Functions
Posters
- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation [PDF]
- Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming [PDF]
- Quantum Chebyshev’s Inequality and Applications [PDF]
Teaching
- Introduction to Quantum Computing, Summer Course on Quantum Technologies, University of the Basque Country, 2024.
- Quantum Query Complexity, PCMI Graduate Summer School, 2023.
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.