I know next to nothing about quantum computing, is such a thing even possible with the current state of QC + billions of dollars?

Does the current state of quantum computing excite or keep security researchers awake at night?

Nobody really knows. It has not been proved that useful QC is possible. (All existing QC is practically useless, and it is not clear that it is even possible to scale it up. This is not snark; if it ever will be useful, we must of course walk before we run.) It is possible that there is no amount of money that will make it useful. It has also not been proved to be impossible, and interesting and tantalizing breakthroughs have been made over time such that it's hard to look at them and firmly promise it's impossible, either. (I fall on the skeptical side myself, but it's what I call "true" skepticism; produce it and I won't try to argue out it out existence, I'll just update my beliefs and move on. And celebrate whoever produces it for doing what I believed to be impossible.)

This is rather like commercial fusion research; it has not yet been shown to even be possible to economically use fusion for power generation, yet it has not been proved impossible either. Contrast this to nuclear fission research, which at this point is more like engineering; modulo lawsuits and administrative compliance, we could probably take a pretty good guess at what it would take to, say, bring a commercial thorium reactor online.

Well anyone with photovoltaics can demonstrate working economical fusion power at a certain large scale. At least there is an existence proof at the extreme there, which QC does not have.

It's a long-term concern. One way to gauge it is that many researchers working seriously on post-quantum cryptography are far more seriously engaged in pre-quantum work like secure elliptic curve.

Ok thanks, last question and I'll leave you alone.

Could you recommend some relatively accessible reading for the layman on how the security world would react to a sudden shift into the post-quantum world?

And, in your opinion, how concerned should average Joes and Janes, like me, be concerned about a sudden shift to a post-quantum world?

Edit: For example: Would my bank be safe? Would my health records be safe?

(On this hyperbolic fear legitimacy scale: Y2K <----> Cryptopocalypse)

Why exactly would it cost so much?

Because it involves a result that would be new to computer science and electrical engineering?

I wish people could make requests for supporting information like the grandparent post did without getting this kind of snarky reply. Sometimes questions are just questions, not attacks.

In this case, it would be easiest to simply read the sentence as though there's no snark, as I'd bet it's the correct answer.

Quantum computing is brilliant at certain types of computation, it's not a Singularity-level silver bullet. Simplified to the point of lie, it can transform certain classes of computation by taking shortcuts; the oft referenced Shor's algorithm, for example, can factor a prime in polynomial time, which is immensely faster. [0]

But that wouldn't necessarily be enough to break crypto, as anything that wasn't based on factoring a polynomial would need another algorithm. Also, while fast, the algorithm is not instant nor easy to run: a lot of qubits would be needed, and the current state-of-the-art can't support that level of computation against large numbers without a prohibitive amount of expense (qubits are not naturally stable at room temperature). For comparison, factoring a 1024 bit number would take 1024 qubits together, while only a few have ever operated together under ideal lab conditions (Wikipedia notes IBM's accomplishment factoring 15 with 7 qubits, and notes the number 21 was factored in 2012).

There is a huge amount of work in the pipe, and there's plenty of room to be shocked and amazed by new developments. But it will require innovations that would revolutionize whole industries. This is still very new tech, decades from maturity (though naturally not from commercial early-adoption).

At least, I think that's what tptacek meant. Sorta.

[0]http://en.wikipedia.org/wiki/Shor's_algorithm

> the oft referenced Shor's algorithm, for example, can factor a prime in polynomial time, which is immensely faster.

Actually, Shor's algorithm is for factoring composites, not factoring primes.

Don't feel bad about that little word mixup. You are in good company. Bill Gates did it in his book "The Road Ahead".

Not gonna lie, I feel a bit dumb for that. Factoring primes is as useful as a one-input mux, as a college roomie would say.

True, but sometimes questions also don't show a whole lot of effort on the part of the asker, and so the answerer is not inclined to put in much of their own. If I'm going to ask a question and want a thorough answer, I try to at least provide a little background on what I already know.