We explore the provable advantages and limitations of quantum computers in three contexts. First, we consider how to design quantum algorithms by studying a result on the regular languages. Next, we discuss unconditional quantum advantage in the context of shallow circuits. We give separations with relation problems and interactive problems. Finally, we explore the problem of efficiently learning quantum states.
