PROPOSITION DE STAGE – L3 INFORMATIQUE – ENS LYON
If you are interested in doing an internship on the topic of quantum algorithms and computing, feel free to contact me at apers@irif.fr.
Below is one suggested topic, but also do not hesitate to ask for others.
- Quantum expansion testing.
Quantum expanders are a generalization of expander graphs to the quantum setting [BST10]. In the classical setting, there is a famous random walk algorithm for testing whether a graph is an expander or not [GR11]. Goal of the internship is to devise a quantum algorithm for testing quantum expanders.
[BST10] Ben-Aroya, Avraham, Oded Schwartz, and Amnon Ta-Shma. "Quantum expanders: Motivation and constructions." 2008 23rd Annual IEEE Conference on Computational Complexity. IEEE, 2008.
[GR11] Goldreich, Oded, and Dana Ron. "On testing expansion in bounded-degree graphs." Studies in Complexity and Cryptography (2011): 68-75.