5 ms·
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.
by akjssdk 7y ago
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-programmable.html https://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...
- AlexCoventry 7y agoSo if they increase the number number of qubits they'll be have a classically infeasible calculation again? Should be interesting.
- lallysingh 7y agoIf the problem is linear, then frankly I don't think anyone cares if there's a QC implementation.
- AlexCoventry 7y agoMy impression is that the difficulty is linear in the depth of the calculation, exponential in the number of qubits.
- deleted 7y ago[deleted]
- Symmetry 7y agoThere 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 agoIsn'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 agoAs 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 agoBut 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 agoThe 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 agoYes, 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.