To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on this (see QAZ for precise definitions and references. This is another way to say I don’t even pretend to understand many of the problems of this list!)
Algebraic and Number Theoretic Problems
If I’m not mistaken, all problems listed before the Abelian hidden subgroup problem are special cases of it.
- Factorization
- Discrete logarithm
- Pell’s Equation. Factoring reduces to Pell’s equation.
- Principal Ideal Ideal problem. Pell’s equation reduces to this problem, which therefore at least as hard as factoring.
- Unit Group problem
- Class Group problem
- Gauß Sums estimation
- Matrix Elements of Group Representations
- Group Order and Membership
- The Abelian hidden subgroup problem
- Some (but not all) non-Abelian hidden subgroup problems
- Some (but not all) problems phrased as special cases of the hidden shift problem
- Some (but not all) Hidden Nonlinear Structures problems
- Exploring some graphs (Welded trees)
- Group Isomorphism, for Abelian and some non-Abelian groups
- Find some properties of Finite Rings and Ideals
Approximation and Simulation
- Quantum simulation. Obviously $BQP$-complete
- Computing some knot-invariants, including HOMFLY polynomial, of which the Jones polynomial is a special case. Some of them are $BQP$-complete
- Computing some Three-manifold Invariants. Some of them are $BQP$-complete.
- Estimating the thermodynamic partition function of some classical systems
- Computing Zeta Functions over finite fields
- A string rewriting problem is $\mathit{PromiseBQP}$-complete
- approximating matrix elements of powers of exponentially large sparse matrices.
Algorithm I don’t really get.
These are mainly algorithms where QAZ claims a superpolynomial increase, but I don’t get why the original problem is supposed to be out of $P$. That said, I’ll bet lots of my money on QAZ being right and myself being wrong on that.
- Pattern matching for large enough ($>\log(n)$) patterns
- Some linear system problems, in $P$ but having a $\mathrm{polylog}$ quantum algorithm if the linear system is given as an oracle.
- Computing the Electrical Resistance of a graph,has a $\mathrm{polylog}$ quantum algorithm if the electric circuit is given as an oracle
- Weight Enumerators problem. Something related to code and partition functions, but I don’t understand what it is about.
$P$ problems 1st proved to be in $BQP$ and then in $P$
Here are some problems where an efficient quantum algorithm has been published before a classical one. In other words, they were once conjectured to be in $BQP$ but not in $P$, but this conjecture is now invalidated.
- Satisfying more than $(\tfrac12-\tfrac{\text{constant}}{D})N$ (but less than $\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$) constraints of the Max E3LIN2 problem. As pointed by Juan Berego Vega in the comments : there is now a classical algorithm for $(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$, which was motivated by the quantum result. (Blog post on this result, paper 1, paper2)
- Recommendation systems (see Scott Aaronson’s blog post for a more detailed explanation). Recommendation system — à la Netflix/Amazon/etc.— can be seen as completing a sparse $m×n$ matrix of low rank $k$ with very incomplete data. Known classical algorithm where polynomial in $m$, $n$ ad $k$. If the matrix is given as an oracle, Iordanis Kerenidis an Anupam Prakash found a $\mathrm{poly}(k)\mathrm{polylog}(mn)$ quantum algorithm finding samples of the unknown elements of the matrix in 2016 (paper). In 2018, while trying to prove this scaling is impossible to reach with a classical machine, Ewin Tang actually found a classical algorithm achieving the same performance under the same conditions (paper available here and here).
