AF: Small: The Quantum Complexity of Physical and Algebraic Problems

This award aims to increase our understanding about the power of quantum computers. The goal is to determine which problems have efficient quantum algorithms and which do not. One source of problems relates to the simulation of quantum mechanical systems. Another direction is determining which cryptosystems are secure against quantum computers. The most commonly used cryptosystems, such as systems based on RSA and elliptic curves, can be broken by quantum computers and an important question is to determine which systems to use instead. This question involves both understanding which problems are hard for quantum computers as well as how to design secure protocols.

The PI and his graduate students will consider three types of problems. The first comes from Hamiltonian complexity, which addresses computing properties of physical systems. Depending on the setup, these systems range from being solvable classically to being very hard even for quantum computers. The second set of problems comes from proposals for quantum-resistant cryptography using the Learning With Errors problem. The PI will study the recent assumptions that have been made to make these systems more efficient to see if they are secure against quantum computers. The third set of questions involves determining when the security arguments work for classical protocols in the presence of quantum computers.