AF: Small: Quantum Algorithms and Complexity

This project studies the power of quantum computers. The main goal is to determine which problems have efficient quantum algorithms and

which ones remain hard in the presence of quantum computers. This is a fundamental question in computer science. One objective is to find new applications for quantum computers. A second objective is to understand which cryptosystems are secure against quantum computers. These systems must be based on problems that cannot be solved efficiently by quantum computers. The PI and his graduate students are considering these types of problems.

The project considers new approaches for the dihedral hidden subgroup problem. A quantum algorithm for this problem, if found, would break some candidates for quantum-secure cryptosystems. If more evidence is found that the problem is difficult to solve, then it increases the confidence in the security of the proposed systems. Another type of potential speedup is for optimization problems. The work addresses whether certain settings for the approximate adiabatic algorithm exist for which the quantum algorithm achieves a better

approximate solution than the best classical algorithm. The last problem deals with understanding Hamiltonian complexity.