Which problems can and can't a quantum computer solve? - Ricardo Rivera Cardoso

Giving a definite answer to this question could either be the cause for celebration or concern, as quantum computing now connects many of the natural sciences and has received significant attention and funding across the globe. To study this question formally, we must turn to a sub-field of computer science called “complexity theory”. Here, we will introduce some of the basics of this field and illustrate the best answer we can provide currently. Along the way, we will discuss the relationship between classical and quantum computers, and whether one is truly more powerful than the other. Finally, we will discuss some shortcomings of the picture we’ve painted so far, which relate to approximation algorithms, average-case complexity, and quantum computers without fault-tolerance.