In the first half of the talk, I will give a brief introduction to quantum computing from the perspective of a computer scientist/mathematician. While it may seem obvious that quantum computers should be better than classical computers, this can be surprisingly hard to rigorously prove, especially using the types of quantum computers that are available today. In the second half of the talk, I will describe this quest for provable quantum advantage and some of the research directions I find most interesting.