[false-mirror]

I'm disappointed that this article doesn't answer my only real question about quantum computers: What does a reasonable expectation look like? What is the range of potential performance gains?

I understand that this is the frontier and no one has any definite answers, but I hear everything from "trivial" improvements to "insta-crack AES-256" (thousands of trillion trillion trillion trillions times faster).

Does anyone have a well informed upper/lower bound estimate?

[ahelwer]

Quantum computers won't insta-crack AES. They only give a square-root speedup for symmetric crypto (so you can double the key length for equivalent security) with Grover's algorithm. It's public-key crypto algorithms based on prime factorization or the descrete log problem which will be broken by Shor's. However, running Shor's algorithm on production key sizes requires a huge quantum computer (with millions of qbits) and Scott Aaronson says he would be "astounded" if this was accomplished within the next decade.

Improvements are believed to be exponential when simulating physical quantum systems.

[nestorD]

This.

Quantum computing have be designed to solve a single problem : the simulation of quantum systems on a classical computer is very slow, lets build a quantum computer so that it will be fast.

It might seem like a fringe use case but it matters (a lot) to industrials and researchers in a wide variety of topics.

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

[vincent-toups]

Read Quantum Computing Since Democritus. Its the best you can do as a lay person.

[PeterisP]

For most problems, no performance gains whatsoever. There's no expection for quantum computers to replace or improve general computing.

You can get immense speedups for a very particular set of problems, turning them from "can't possibly complete ever" to solvable; so it would be like an assistive device for these niche tasks, but it would be very important for them because otherwise they're not really practical to solve.

[fixf]

There's multiple bounds. The mounting evidence for BPP=BQP unfortunately falls aside P=BPP for evidence without proof. The weak interpretation is that BQP is vulnerable, and the strong interpretation is that BQP is broken. It's in the air, but for certain applications people can't afford to guess wrong. It's reasonable to remove it as a dependency in those fields.