Hacker News Reader

Comment by akjssdk | Hacker News Reader

The main takeaway here is figure 1 in this article: they show that for an increasing circuit depth, computation time (on a classical computer) scales linearly. Google claims, on the other hand, that a classical calculation would scale exponentially. This is the basis for the graph in the Google blog [1], which seems to suggest that the Quantum computer can easily reach points (such as qbits=50, cycles=25) which the classical computer would never be able to reach. This is not true, if IBM is right. Their linearly scaling graph proves that they are not nitpicking their input, I would say.

[1]: https://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...

View on HN

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.

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

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.

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

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.

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.

No, the bound is not on the performance of the sorting algorithm, but rather on the minimum number of comparisons required

I would argue that "number of comparisons" is just the popular performance metric.

Of course in reality we care about execution time, and in order to go from "we need O(n * log(n)) comparisons" to "we need O(n * log(n)) time" you need additional assumptions, like "memory access takes O(1) time, and the speed of one comparison is independent of the total amount of data". But for any reasonable set of assumptions an algorithm that uses O(n * log(n)) comparisons takes at least O(n * log(n)) time (probably more since memory access isn't really O(1), it's just common to pretend that it is).

I disagree, because it is perfectly possible to sort without comparisons. For example, sorting a list of distinct integers is theoretically O(N). (radix sorting)

That's not sorting, that's sorting distinct integers, which is a different problem.

That's like saying multiplication can't have any lower bound because multiplying by zero is O(1).

That's not a definition supported by any literature I've read. Seems like you're moving the goalpost because you don't like the definition. For what it's worth, radix sort is listed on the wikipedia page for "Sorting Algorithms", and its runtime is listed as O(n * k) where k is the number of digits per number: https://en.wikipedia.org/wiki/Sorting_algorithm#Radix_sort

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 for a recent survey.

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.

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.

There are provable quadratic speedups over all possible classical algorithms.

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.

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

(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.)

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?

That's what my last two sentences address.

So if they increase the number number of qubits they'll be have a classically infeasible calculation again? Should be interesting.

If the problem is linear, then frankly I don't think anyone cares if there's a QC implementation.

My impression is that the difficulty is linear in the depth of the calculation, exponential in the number of qubits.

Reply on news.ycombinator.com