# 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.

• Complexity advantage as in no speed up in the overall running time, or that the language class is closed under the operation? – Ryan Jun 28 '15 at 1:08
• @Ryan I meant no speed up in the overall running time. Thank you for the question. – Lembik Jun 28 '15 at 5:43
• Anything already polynomial time. :-) – kasterma Jun 29 '15 at 10:01
• @kasterma I don't think this is correct. There are plenty of poly time problem for which there is currently a quantum speedup. – Lembik Jun 29 '15 at 10:22
• I would suggest to refine this question specifying whether (a) it is about "no provable quantum advantage" vs "no known quantum advantage"; whether (b) the question is about exponential or polynomial speed-ups (with respect to problems not in P or BPP); and whether (c) other types of speed-ups (eg logarithmic speed-ups over problems within P or BPP) are allowed. – Juan Bermejo Vega Jul 13 '15 at 9:16

This is not in NP, but comparison-based sorting. The $\Omega(n \log n)$ lower bound is information theoretic.
• The bound being information theoretic does not show that quantum algorithms can't beat it. $\:$ (Consider Grover's algorithm.) $\;\;\;\;$ – user6973 Jun 27 '15 at 23:12
• @RickyDemer I am not sure what you are thinking. Information theoretic arguments hold reguardless of the model of compuation. For unstructured search, the input is an array $A$ of $n$ items and a target item $x$, and the output is an index $i$ such that $A[i] = x$ (which I assume exists for simplicity). Since one bit is learned with each query, information theory says that any algorithm must make $\log n$ queries. Grover's algorithm, at $\Theta(\sqrt{n})$ queries, is far from being tight to this bound, let along being less than it. – Tyson Williams Jun 28 '15 at 0:06
• As far as I understand, entropy/counting-based arguments do not immediately hold for quantum algorithms, because they are about probability distributions and not about superpositions of quantum states. The $\Omega(\log n)$ ordered search lower bound for example was a FOCS paper by Ambainis, and the sorting lower bound also seems to require some work arxiv.org/abs/quant-ph/0102078. So it seems that your claim is correct, but not as immediate as you suggest. – Sasho Nikolov Jun 28 '15 at 3:16
• @SashoNikolov: I agree with what you have written. Information theoretic bounds of the form Tyson describes where "one bit is learned with one query" don't necessarily hold for quantum. Consider the Bernstein-Vazirani problem, where the problem's output is $n$ bits, and thus a classical machine needs to make $n$ queries for information-theoretic reasons, but a quantum computer can do it with 1 query. – Robin Kothari Jun 29 '15 at 14:58