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 The unstructured search problem, as I defined it for Ricky, didn't provide the option to fail. The argument that I gave holds for that problem. The lower bound given by Ambainis at FOCS (which I was not able to find) is probably for the more general problem that only requires one to succeed with small probability. Same goes for the problem of sorting and the arXiv paper that you link to. – Tyson Williams Jun 28 '15 at 23:19
• @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

Recently, this paper in SODA 2018 shows a constant factor approximation algorithm for edit distance in quantum computers with subquadratic time. Note that, no constant factor approximation algorithm for edit distance in classical computers with subquadratic time is known, yet. Moreover, it is believed that no such algorithm exist in classical computers.

• I don't think the last sentence is correct. There are no complexity consequences to a classical solution with the same complexity. – Lembik Apr 23 '18 at 9:07
• @Lembik You were right. The paper somehow de-quantumized the previous paper and found a constant factor approximation algorithm for edit distance in subquadratic time complexity. See this blog post for more info. – Mohemnist Nov 22 '18 at 19:49