While Shor's algorithm for integer factoring and Grover's algorithm for search are the most celebrated quantum algorithms, many other quantum algorithms have been discovered in the past 25 years (a good reference is the Quantum Algorithm Zoo). One of the main goals of our group is to find novel quantum algorithms and discover "killer applications" of quantum computers. We also aim at showing the superiority of quantum algorithms via rigorous mathematical analysis of their performance.
The central question in quantum complexity theory is to understand in which situations quantum compution is more powerful than classical computation, and then quantify the quantum advantage. In our group we investigate this question using mathematical tools, in several setting such as time complexity, space complexity, query complexity, communication complexity or complexity classes.
