Timeline for Problems with no known quantum advantage
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2018 at 19:49 | comment | added | Mohemnist | @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. | |
| Apr 23, 2018 at 9:07 | comment | added | Simd | I don't think the last sentence is correct. There are no complexity consequences to a classical solution with the same complexity. | |
| Apr 22, 2018 at 10:57 | history | answered | Mohemnist | CC BY-SA 3.0 |