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

CC BY-SA 3.0
2015-06-28T00:06:32.197Z
@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
CC BY-SA 3.0
2015-06-28T03:16:49.380Z
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 http://arxiv.org/abs/quant-ph/0102078. So it seems that your claim is correct, but not as immediate as you suggest.
Sasho Nikolov
CC BY-SA 3.0
2015-06-28T05:45:00.660Z
Thank you for the answer. It isn't quite what I had in mind however as the restriction to "comparison based sorting" seems potentially to neuter the power of the quantum computer I am interested in. On the other hand, is there a linear time quantum sorting algorithm or one faster than $\Theta(n \sqrt{\log \log{n}})$?
Simd
CC BY-SA 3.0
2015-06-28T23:19:46.270Z
@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
CC BY-SA 3.0
2015-06-28T23:23:59.460Z
@eleanora Sure, that is why I prefaced my answer with "this is not in NP".  Your comment seems to suggest that there is something more specific about quantum computing that you are interested in.  I think it would improve your question if you were to elaborate on this point.
Tyson Williams
CC BY-SA 3.0
2015-06-29T09:10:13.473Z
Your answer is very interesting, thank you. I just meant that I would be particularly interested in problems in NP. Also, as far as I know sorting is a problem for which the classical and quantum complexities are currently the same (the complexity I quoted in my previous comment).
Simd
CC BY-SA 3.0
2015-06-29T14:58:42.063Z
@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
CC BY-SA 3.0
2015-06-29T16:23:14.347Z
@RobinKothari I am not saying that information theoretic bounds of the form "one bit is learned with one query" hold for every problem and every model of computation. I am only saying this for the problem in my answer (sorting) and the simpler example given in my comment (unstructured search).
Tyson Williams
CC BY-SA 3.0
2015-06-27T18:22:35.553Z
2015-06-27T18:22:35.553Z
Tyson Williams
<p>Recently, <a href="https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.76" rel="nofollow noreferrer">this paper</a> 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.</p>

CC BY-SA 3.0
2018-04-23T09:07:05.283Z
I don't think the last sentence is correct. There are no complexity consequences to a classical solution with the same complexity.
Simd
CC BY-SA 4.0
2018-11-22T19:49:49.713Z
@Lembik You were right. The [paper](https://arxiv.org/abs/1810.03664) somehow de-quantumized the previous paper and found a constant factor approximation algorithm for edit distance in subquadratic time complexity. See this [blog post](https://theorydish.blog/2018/07/20/approximating-edit-distance/) for more info.
Mohemnist
CC BY-SA 3.0
2018-04-22T10:57:28.473Z
2018-04-22T10:57:28.473Z
Mohemnist
<p>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. </p>

<p>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).</p>

<hr>

<p>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.</p>

<hr>

<p>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. </p>

<p>I am not focusing on cases where we can prove there <em>can't</em> be an advantage nor am I focusing on <em>exponential</em> speedups (i.e. <em>polynomial</em> 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.</p>

CC BY-SA 3.0
2015-07-13T09:16:16.950Z
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
CC BY-SA 3.0
2015-06-28T01:08:27.680Z
Complexity advantage as in no speed up in the overall running time, or that the language class is closed under the operation?
Ryan Dougherty
CC BY-SA 3.0
2015-06-28T05:43:57.943Z
@Ryan I meant no  speed up in the overall running time. Thank you for the question.
Simd
CC BY-SA 3.0
2015-06-29T10:01:32.070Z
Anything already polynomial time. :-)
kasterma
CC BY-SA 3.0
2015-06-29T10:22:03.853Z
@kasterma I don't think this is correct. There are plenty of poly time problem for which there is currently a quantum speedup.
Simd
<ds.algorithms><quantum-computing><big-list>
Problems with no known quantum advantage
Simd
# Problems with no known quantum advantage

(Asked by: username_0 on 2015-06-27)

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

**Tags:** ds.algorithms, quantum-computing, big-list

> **Comments:**
> **username_2**: Complexity advantage as in no speed up in the overall running time, or that the language class is closed under the operation?  
> **username_0**: @Ryan I meant no  speed up in the overall running time. Thank you for the question.  
> **username_3**: Anything already polynomial time. :-)  
> **username_0**: @username_3 I don't think this is correct. There are plenty of poly time problem for which there is currently a quantum speedup.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_4 on 2015-06-27. Score: 6

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

> **Comments:**
> **username_4**: @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.  
> **username_5**: 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 http://arxiv.org/abs/quant-ph/0102078. So it seems that your claim is correct, but not as immediate as you suggest.  
> **username_0**: Thank you for the answer. It isn't quite what I had in mind however as the restriction to "comparison based sorting" seems potentially to neuter the power of the quantum computer I am interested in. On the other hand, is there a linear time quantum sorting algorithm or one faster than $\Theta(n \sqrt{\log \log{n}})$?  
> **username_4**: @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.  
> **username_4**: @eleanora Sure, that is why I prefaced my answer with "this is not in NP".  Your comment seems to suggest that there is something more specific about quantum computing that you are interested in.  I think it would improve your question if you were to elaborate on this point.  
> **username_0**: Your answer is very interesting, thank you. I just meant that I would be particularly interested in problems in NP. Also, as far as I know sorting is a problem for which the classical and quantum complexities are currently the same (the complexity I quoted in my previous comment).  
> **username_6**: @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.  
> **username_4**: @RobinKothari I am not saying that information theoretic bounds of the form "one bit is learned with one query" hold for every problem and every model of computation. I am only saying this for the problem in my answer (sorting) and the simpler example given in my comment (unstructured search).  

---

### Answer by username_7 on 2018-04-22. Score: 4

Recently, [this paper](https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.76) 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.

> **Comments:**
> **username_0**: I don't think the last sentence is correct. There are no complexity consequences to a classical solution with the same complexity.  
> **username_7**: @Lembik You were right. The [paper](https://arxiv.org/abs/1810.03664) somehow de-quantumized the previous paper and found a constant factor approximation algorithm for edit distance in subquadratic time complexity. See this [blog post](https://theorydish.blog/2018/07/20/approximating-edit-distance/) for more info.  

---

