Abstract: Quantum computers—computers which exploit quantum mechanics—are poised to reshape the landscape of computation. But understanding when 'quantum' can help speed up algorithmic tasks is tricky, particularly for those tasks which have the greatest potential for real-world impact. In this talk, I will survey my work in quantum algorithms to understand where quantum computers will be useful. I will argue that this research can shed light, not only on quantum computation, but also on its proposed applications.