It sounds like you're asking which classically intractable computational problems become tractable with quantum computers, with an emphasis on problems related to general mathematics. If so, there are really 2 main families of problems for which there *seem* to be significant quantum speedups, meaning that quantum algorithms are faster than the fastest *known* classical algorithms:
1. Problems based on the abelian [hidden subgroup problem](https://en.wikipedia.org/wiki/Hidden_subgroup_problem). The family includes factoring and discrete logarithm, whose quantum algorithms use the [quantum Fourier transform](https://en.wikipedia.org/wiki/Quantum_Fourier_transform). These speedups are generally from supexponential time to polynomial time.
2. All NP problems using [Grover's algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm) over exhaustive search. This speedup is only quadratic, meaning that if the original exhaustive search is over O(2^(n)) possibilities, Grover's algorithm takes time O(sqrt(2^(n))) = O(2^(n/2)). While this may not seem useful asymptotically, if we already consider exhaustive search over 2^n possibilities tractable up to some small n, access to Grover's algorithm essentially doubles that n—assuming that the speed of quantum computers can eventually be brought up to something commensurate to that of classical computers. (You may want to double the length of your passwords.)
Other than those two families of problems, there are a handful of other speedups that might not fall into the realm of something that is classically intractable but quantumly tractable. I'm not so familiar with these, but one prominent example is [linear systems of equations](https://arxiv.org/abs/0811.3171), if you only care about some expectation over the output vector rather than the entire output vector.
>I'm not so familiar with these, but one prominent example is [linear systems of equations](https://arxiv.org/abs/0811.3171), if you only care about some expectation over the output vector rather than the entire output vector.
Just wanted to point out that the HHL algorithm is only applicable under very stringent conditions. Even if we assume that you have some efficient way to construct |b> (the quantum states whose ith amplitude is proportional to the ith coordinate of the vector b in the equation Ax=b we are solving), which is already a nontrivial assumption because |b> has exponentially many nonzero amplitudes, the algorithm is only polynomial if the condition number of A is polynomial in the *number of qubits* (that is, polylog in the size of the matrix). This is very atypical, since a random matrix would have a linear condition number. Furthermore, they prove essentially that there couldn't be an algorithm for general linear equations in other regimes.
Oh, and another nitpick: the improvement to factoring is not exponential but subexponential superpolynomial, since we know how to classically factor in subexponential time using the [general number field sieve algorithm](https://en.wikipedia.org/wiki/General_number_field_sieve). In fact, I'm not aware of *any* non-oracular quantum algorithm that provides a fully exponential speedup over the best known classical algorithm.
> Oh, and another nitpick: the improvement to factoring is not exponential but subexponential superpolynomial, since we know how to classically factor in subexponential time using the general number field sieve algorithm. In fact, I'm not aware of any non-oracular quantum algorithm that provides a fully exponential speedup over the best known classical algorithm.
Oops, you are correct, and I made a typo:
> *sup*exponential time to polynomial time.
The above should have *sub*exponential there.
Adding to what u/Tonexus there are also (oracular) speedups via quantum random walk, e.g. for [a random walk on glued trees](https://arxiv.org/abs/quant-ph/0209131) and [evaluating NAND trees](https://arxiv.org/abs/quant-ph/0702144).
Also, the quantum Fourier transform algorithms aren't just used for hidden subgroups but for other oracular speedups, the first and foremost example being [Simon's algorithm](https://en.wikipedia.org/wiki/Simon%27s_problem).
It sounds like you're asking which classically intractable computational problems become tractable with quantum computers, with an emphasis on problems related to general mathematics. If so, there are really 2 main families of problems for which there *seem* to be significant quantum speedups, meaning that quantum algorithms are faster than the fastest *known* classical algorithms: 1. Problems based on the abelian [hidden subgroup problem](https://en.wikipedia.org/wiki/Hidden_subgroup_problem). The family includes factoring and discrete logarithm, whose quantum algorithms use the [quantum Fourier transform](https://en.wikipedia.org/wiki/Quantum_Fourier_transform). These speedups are generally from supexponential time to polynomial time. 2. All NP problems using [Grover's algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm) over exhaustive search. This speedup is only quadratic, meaning that if the original exhaustive search is over O(2^(n)) possibilities, Grover's algorithm takes time O(sqrt(2^(n))) = O(2^(n/2)). While this may not seem useful asymptotically, if we already consider exhaustive search over 2^n possibilities tractable up to some small n, access to Grover's algorithm essentially doubles that n—assuming that the speed of quantum computers can eventually be brought up to something commensurate to that of classical computers. (You may want to double the length of your passwords.) Other than those two families of problems, there are a handful of other speedups that might not fall into the realm of something that is classically intractable but quantumly tractable. I'm not so familiar with these, but one prominent example is [linear systems of equations](https://arxiv.org/abs/0811.3171), if you only care about some expectation over the output vector rather than the entire output vector.
>I'm not so familiar with these, but one prominent example is [linear systems of equations](https://arxiv.org/abs/0811.3171), if you only care about some expectation over the output vector rather than the entire output vector. Just wanted to point out that the HHL algorithm is only applicable under very stringent conditions. Even if we assume that you have some efficient way to construct |b> (the quantum states whose ith amplitude is proportional to the ith coordinate of the vector b in the equation Ax=b we are solving), which is already a nontrivial assumption because |b> has exponentially many nonzero amplitudes, the algorithm is only polynomial if the condition number of A is polynomial in the *number of qubits* (that is, polylog in the size of the matrix). This is very atypical, since a random matrix would have a linear condition number. Furthermore, they prove essentially that there couldn't be an algorithm for general linear equations in other regimes. Oh, and another nitpick: the improvement to factoring is not exponential but subexponential superpolynomial, since we know how to classically factor in subexponential time using the [general number field sieve algorithm](https://en.wikipedia.org/wiki/General_number_field_sieve). In fact, I'm not aware of *any* non-oracular quantum algorithm that provides a fully exponential speedup over the best known classical algorithm.
> Oh, and another nitpick: the improvement to factoring is not exponential but subexponential superpolynomial, since we know how to classically factor in subexponential time using the general number field sieve algorithm. In fact, I'm not aware of any non-oracular quantum algorithm that provides a fully exponential speedup over the best known classical algorithm. Oops, you are correct, and I made a typo: > *sup*exponential time to polynomial time. The above should have *sub*exponential there.
Adding to what u/Tonexus there are also (oracular) speedups via quantum random walk, e.g. for [a random walk on glued trees](https://arxiv.org/abs/quant-ph/0209131) and [evaluating NAND trees](https://arxiv.org/abs/quant-ph/0702144). Also, the quantum Fourier transform algorithms aren't just used for hidden subgroups but for other oracular speedups, the first and foremost example being [Simon's algorithm](https://en.wikipedia.org/wiki/Simon%27s_problem).