[Tyr42]

There's a lot of research at the "P = BQP?", "NP < BQP" kinda level, which is more like comparing big O notation runtimes.

I can tell you that Shor's algorithm for factoring takes O((log n)^2 (log log n)(log log log n)) (we can round that up to O((log n)^4) if you want) to a the best known classical algorithm of

O(exp(1.9 * (log n)^(1/3) (log log n)^(2/3)))

But unless I tell you how fast each gate is, that tells you nothing about the constant time factors.

Also, all these quantum algorithms are constructed out of logical gates, but each logical gate might be built out of 10 physical gates, using some error correcting code.

Since you really need to know the physical characteristics of the particular architecture to know how much error correction you need, it's hard to even say how many gates something will use and how fast they are until we pick a particular architecture.

All we can really say is that given a big enough number, a quantum computer can factor it faster than a classic computer.

[The_rationalist]

But could quantum computing accelerate AI workloads such as graph traversal/rewriting?

Iff quantum computing is only useful at breaking encryption, I don't see the point in funding quantum computing research.

[ahelwer]

Getting an exponential speedup on simulating quantum-mechanical systems (protein folding/binding, material design) is the killer app of quantum computing. Nobody is funding quantum computers because they want to break public-key crypto; that's just a somewhat unfortunate (though interesting) side-effect bringing a bunch of costs with cryptographic R&D plus transitioning systems to post-quantum crypto.

Quantum computing is not expected to have large impacts on machine learning at this time after Ewin Tang's paper. There's an especially large amount of fluff in this area, though.