And it's definitely not "try every possibility in parallel", as is sometimes portrayed by people who don't know better. While quantum computing makes it possible to superpose multiple possibilities, the way quantum mechanics works, you can only measure one (and you have to decide ahead of time which one to measure, i.e. you can't ask the quantum system like "give me the superposition with the highest value"). That's why only a few specific algorithms are aided by quantum computing at all. Integer factorization (or more generally, anything that uses Fourier transforms) is the biggest, where it's exponential speedup, but most others are just quadratic speedup.

And even if you could simulate and measure multiple things in parallel, that still wouldn't let you solve the halting problem, which would require simulating and measuring infinite things in parallel.

Another way of saying it: everything that can be done on a quantum computer can also be done on a classical computer. It's just that some specific algorithms can be done much faster on a quantum computer, and in the case of integer factorization, a quantum computer could factor numbers larger than would ever be practical on a classical computer. But that's really it. There's nothing magical about them.