10
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Complexity advantage as in no speed up in the overall running time, or that the language class is closed under the operation? $\endgroup$
    – Ryan Dougherty
    Jun 28, 2015 at 1:08
  • $\begingroup$ @Ryan I meant no speed up in the overall running time. Thank you for the question. $\endgroup$
    – Simd
    Jun 28, 2015 at 5:43
  • $\begingroup$ Anything already polynomial time. :-) $\endgroup$
    – kasterma
    Jun 29, 2015 at 10:01
  • 2
    $\begingroup$ @kasterma I don't think this is correct. There are plenty of poly time problem for which there is currently a quantum speedup. $\endgroup$
    – Simd
    Jun 29, 2015 at 10:22
  • $\begingroup$ 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. $\endgroup$
    – Juan Bermejo Vega
    Jul 13, 2015 at 9:16

2 Answers 2

Reset to default
5
$\begingroup$

This is not in NP, but comparison-based sorting. The $\Omega(n \log n)$ lower bound is information theoretic.

Improve this answer
$\endgroup$
10
  • $\begingroup$ The bound being information theoretic does not show that quantum algorithms can't beat it. $\:$ (Consider Grover's algorithm.) $\;\;\;\;$ $\endgroup$
    – user6973
    Jun 27, 2015 at 23:12
  • 3
    $\begingroup$ @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. $\endgroup$
    – Tyson Williams
    Jun 28, 2015 at 0:06
  • 4
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Jun 28, 2015 at 3:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tyson Williams
    Jun 28, 2015 at 23:19
  • 2
    $\begingroup$ @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. $\endgroup$
    – Robin Kothari
    Jun 29, 2015 at 14:58
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I don't think the last sentence is correct. There are no complexity consequences to a classical solution with the same complexity. $\endgroup$
    – Simd
    Apr 23, 2018 at 9:07
  • $\begingroup$ @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. $\endgroup$
    – Mohemnist
    Nov 22, 2018 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.