Problems with no known quantum advantage I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. 

To start things off, I think computation of the edit distance is one for which the fastest known quantum algorithm seems to be the fastest known classical one. More tentatively, I would also suggest sorting as another problem for which there is no known quantum speedup (compared to the fastest known unit-cost word RAM algorithm).



Although I don't want to set a hard restriction, I am particularly interested in problems in NP and/or problems with no known efficient classical solution.



Following a suggestion of Juan Bermejo Vega  here is some further clarification.  I am interested in problems in NP for which there is currently no known big $O$ time complexity advantage at all if you use a quantum computer. 

I am not focusing on cases where we can prove there can't be an advantage nor am I focusing on exponential speedups (i.e. polynomial would also be fine).  So far it seems the only two examples are the ones in my question which seems very surprising if it is really true.
This is not in NP, but comparison-based sorting. The $\Omega(n \log n)$ lower bound is information theoretic.