5 ms·

There are many problems where the best known quantum algorithm is asymptotically better than the best known classical algorithm but, as far as I've heard, nobod

There are many problems where the best known quantum algorithm is asymptotically better than the best known classical algorithm but, as far as I've heard, nobody has ever found a case where the best quantum algorithm can be proved to be better than the best classical algorithm. So there's always going to be a danger of this happening no matter what problem you attack.

hktuotroi 7y ago
Isn't quantum factoring proven to be exponentially faster than the best known classical one? The only question is we don't know if there is a better classical factoring algorithm. Wikipedia: > On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time
- orbifold 7y ago
  As far as I'm aware there actually is no proof that there is no polynomial time factoring algorithm. Complexity theory contains a lot of cargo cult belief with little solid proofs unfortunately. One reason is of course that it is a very hard field of mathematics. See https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book for a recent survey.
  - hktuotroi 7y ago
    But parent was stating something very different, that today quantum factoring is only asymptotically better that classical one, when that is clearly not the case.
- missosoup 7y ago
  The other thing we don't know is whether it's physically possible to build a quantum computer capable of it. As opposed to a theoretical ideal quantum computer. The thing that gets smoothed over with QC is managing the error rates and the fact that it hasn't been shown to be physically possible to scale up computation without the error rates also scaling up exponentially and making the thing useless.
- wongarsu 7y ago
  Yes, for factoring integers the best known quantum algorithm is better than the best known classical algorithm. The catch is that we don't know if a better classical algorithm exists but just wasn't discovered yet. Compare this for example to sorting. We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist.
  - logicchains 7y ago
    >We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist. You can have a faster classical algorithm if it's distributed across n threads for a size n array. For each index i in an array arr, spawn a thread that counts the number of values in arr that are less than arr[i] (an O(n) linear scan), call this x, then do outputArray[x] = (arr[i], 1), where outputArray is initialised to all zeros. If outputArray[x] already exists, instead increment the second term (count) in the tuple. Once all threads are finished, then outputArray will contain the sorted values and the count of duplicate values (so this only works if !(x < y) && !(y < x) implies y == x). Each thread does O(n) work, so total work is O(n^2), but because the threads all run in parallel, the runtime is only O(n).
    - dragontamer 7y ago
      For the most part, classical algorithms assume a fixed-amount of compute power. "Total Work" is the important part to minimize in practice. If "total work" scales at O(n^2), then in practice, the job scales at O(n^2). Its infeasible to build O(n^2) CPUs running O(n^2) threads as n-grows.
    - tmerr 7y ago
      This is an apples to orange comparison. Time complexities are with respect to some computational model. When not specified one typically assumes it's with respect to a deterministic turing machine or something a lot like it. Te model you are describing allows for unbounded parallel execution.
  - webkike 7y ago
jessriedel 7y ago
There are provable quadratic speedups over all possible classical algorithms.
- atq2119 7y ago
  Those are all about problems started in terms of querying some blackbox oracle. Whether the speedup holds up with a concrete instantiation of the blackbox is unknown.
  - jessriedel 7y ago
    Could you elaborate? You can search for the solution to any computational problem for which there is a binary function f(n) mapping candidates n to {0,1}, depending on whether it's a solution. Here, f is the "oracle", but it's only playing the role of representing the problem you're trying to solve, and I believe an f exists for all problems in NP. If your set of solutions has N candidates, this requires only O(sqrt(N)) evaluations rather than O(N). If that function takes exponential time, then there is still of course no polynomial-time solution, but the quadratic speedup holds. https://quantumcomputing.stackexchange.com/questions/2166/grovers-algorithm-and-its-relation-to-complexity-classes https://quantumcomputing.stackexchange.com/questions/2166/gr... There are some NP problems for which we know techniques that are faster than brute-force search, but even then we can generally speed up those techniques in the same way. https://link.springer.com/chapter/10.1007/978-3-540-78773-0_67 https://link.springer.com/chapter/10.1007/978-3-540-78773-0_... (I guess you could worry that for every problem there is an unknown techniques for classically speeding things up over brute-force search, but I thought this was known to be false, and in any case is unrelated to your point. I'm not an expert though.)
    - voxic11 7y ago
      But is there actually a proof that these are improvements over all possible classical algorithms or are they just improvements over the best currently known classical algorithms?
      - 7y ago

hktuotroi 7y ago

Isn't quantum factoring proven to be exponentially faster than the best known classical one? The only question is we don't know if there is a better classical factoring algorithm. Wikipedia: > On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time

orbifold 7y ago
As far as I'm aware there actually is no proof that there is no polynomial time factoring algorithm. Complexity theory contains a lot of cargo cult belief with little solid proofs unfortunately. One reason is of course that it is a very hard field of mathematics. See https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book for a recent survey.
- hktuotroi 7y ago
  But parent was stating something very different, that today quantum factoring is only asymptotically better that classical one, when that is clearly not the case.
missosoup 7y ago
The other thing we don't know is whether it's physically possible to build a quantum computer capable of it. As opposed to a theoretical ideal quantum computer. The thing that gets smoothed over with QC is managing the error rates and the fact that it hasn't been shown to be physically possible to scale up computation without the error rates also scaling up exponentially and making the thing useless.
wongarsu 7y ago
Yes, for factoring integers the best known quantum algorithm is better than the best known classical algorithm. The catch is that we don't know if a better classical algorithm exists but just wasn't discovered yet. Compare this for example to sorting. We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist.
- logicchains 7y ago
  >We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist. You can have a faster classical algorithm if it's distributed across n threads for a size n array. For each index i in an array arr, spawn a thread that counts the number of values in arr that are less than arr[i] (an O(n) linear scan), call this x, then do outputArray[x] = (arr[i], 1), where outputArray is initialised to all zeros. If outputArray[x] already exists, instead increment the second term (count) in the tuple. Once all threads are finished, then outputArray will contain the sorted values and the count of duplicate values (so this only works if !(x < y) && !(y < x) implies y == x). Each thread does O(n) work, so total work is O(n^2), but because the threads all run in parallel, the runtime is only O(n).
  - dragontamer 7y ago
    For the most part, classical algorithms assume a fixed-amount of compute power. "Total Work" is the important part to minimize in practice. If "total work" scales at O(n^2), then in practice, the job scales at O(n^2). Its infeasible to build O(n^2) CPUs running O(n^2) threads as n-grows.
  - tmerr 7y ago
    This is an apples to orange comparison. Time complexities are with respect to some computational model. When not specified one typically assumes it's with respect to a deterministic turing machine or something a lot like it. Te model you are describing allows for unbounded parallel execution.
- webkike 7y ago

jessriedel 7y ago

There are provable quadratic speedups over all possible classical algorithms.

atq2119 7y ago
Those are all about problems started in terms of querying some blackbox oracle. Whether the speedup holds up with a concrete instantiation of the blackbox is unknown.
- jessriedel 7y ago
  Could you elaborate? You can search for the solution to any computational problem for which there is a binary function f(n) mapping candidates n to {0,1}, depending on whether it's a solution. Here, f is the "oracle", but it's only playing the role of representing the problem you're trying to solve, and I believe an f exists for all problems in NP. If your set of solutions has N candidates, this requires only O(sqrt(N)) evaluations rather than O(N). If that function takes exponential time, then there is still of course no polynomial-time solution, but the quadratic speedup holds. https://quantumcomputing.stackexchange.com/questions/2166/grovers-algorithm-and-its-relation-to-complexity-classes https://quantumcomputing.stackexchange.com/questions/2166/gr... There are some NP problems for which we know techniques that are faster than brute-force search, but even then we can generally speed up those techniques in the same way. https://link.springer.com/chapter/10.1007/978-3-540-78773-0_67 https://link.springer.com/chapter/10.1007/978-3-540-78773-0_... (I guess you could worry that for every problem there is an unknown techniques for classically speeding things up over brute-force search, but I thought this was known to be false, and in any case is unrelated to your point. I'm not an expert though.)
  - voxic11 7y ago
    But is there actually a proof that these are improvements over all possible classical algorithms or are they just improvements over the best currently known classical algorithms?
    - 7y ago