Why are quantum computers (going to be) important?

This is a gross exaggeration. Robbing banks electronically requires a heck of a lot more than just breaking encryption (and in some cases can be done even without breaking encryption).

But even if encryption were the only barrier, simply having a quantum computer doesn’t necessarily mean that you could do it feasibly. Encryption methods are considered secure today because to break them, the number of operations a computer needs to perform are related to the size of the encryption key by a rapidly growing function (say, an exponential one). With a quantum computer, you might get that function down to something that grows less rapidly, such as a polynomial one. But if the polynomial exponent is large enough (say, 1000) then you’re still looking an eons of time to brute-force the encryption key.

Not only that, but aside from the very valid points psychonaut just brought up, even if RSA / Diffie Hellman is vulnerable to a quantum computer using Shor’s algorithm, there are whole classes of quantum-resistant algorithms that already exist. Supersingular elliptic curves, ring learning, and lattice methods are a few.

The main reason we haven’t adopted any of these yet is NIST hasn’t formally blessed one of them as the best or most implementable (although they have deemed 69 of them complete and proper), so they haven’t made their way into mainstream crypto libraries yet.

There’s a startup company in the Bay Area, Rigetti, that offers a 19 qubit quantum computing developer environment free. It sounds snazzy on the website, but I don’t pretend to understand their product.

NIST, among others, endorsed a backdoored cryptographic algorithm, so I would not place too much weight on their formal blessing.

Oh, I totally agree from a personal trust perspective - I meant more from a widespread adoption perspective. The government needs to use NIST-approved cryptography, and is a big mover in terms of defining the dominant crypto libraries used.

I made a post in an old thread about how Quantum Computers differ. For context, the thread was asking whether Quantum Computers would aid in computing fractals more quickly:

The value in quantum computers is that it opens up an avenue to solve different sorts of problems we can currently only solve on a very small scale because our current computers need to simulate a quantum computer’s thought process to solve them*.

  • NB: we don’t usually solve these problems by literally writing a QC simulator, we usually use some parallel algorithm that just so happens to explore all the possibility branches a QC would naturally explore via quantum state.

That’s why I included “and nobody was forewarned about it”. In the real world, progress is incremental, and before we get a quantum computer big enough to deal with real-world-sized encryption keys, we’ll get a whole succession of smaller ones working up to that size, and at some point the imminent threat is going to be obvious enough that everyone will switch over to one of those other techniques. But if some James Bond supervillain built a kiloqubit machine right now, he’d be able to wreak absolute havoc, because right now, those other methods mostly aren’t implemented.

Ummm, quantum computing is ALREADY here. IBM (and a few other companies, likely) offers quantum computing as a cloud-based service. They’re currently rather massive (especially on a per-qubit basis), so this some super-tiny or super-powered processor.

source: https://arstechnica.com/science/2018/03/ars-visits-ibms-quantum-computing-lab-but-finds-no-cats-trapped-in-boxes/

Yeah see the “prototypes the size of busses” part of the OP?

While we don’t know the size of the BQP, the relation between BQP and NP isn’t known and I don’t think anyone thinks that some of these will extend to NP-complete sets.

The BQP and NP-hard intersection is also obviously unknown but crypto that depends on factorization is at highest risk.


Note that doc claims that SHA and AES with larger keys is thought to be resistant.

purportedly intel 'n microsoft 'n alphabet are working on their own models … ibm already has successfully built a 50-qubit prototype … 250-qubit is just around the bend. 5, 20 and now 50 … in just 18 months … 250 does not so far off.

No high-end computer has ever been “consumer friendly” because there isn’t a need and there never will be. In fact, even less as time goes on.

Consider “OK, Google, take me home.”

You say that into a “consumer friendly” computer (your phone) and from then it goes to decidedly unfriendly computers running state of the art Artificial Intelligence and those unfriendly computers process the crap out of it and send back what you need in a way you can use it.

You use friendly computers to talk to people. You use unfriendly computers to do real work. They can work together, so you get it all.

We’re very close to the end of home computers as we have known them. You no longer need a computer. You just need a microphone that you can use to talk to a really powerful one running state of the art Artificial Intelligence programs that can actually figure out what you are talking about and give both what you want and often also what you need.

It’s now automatically part of all phones and will soon be part of all televisions. The new Lenovo “Smart Displays” that integrate with Google Assistant are just a stop gap. Look to having the same functionality built into the newer televisions real soon.

More power means more smarts. Some day your Google Assistant will see that you’ve fallen down and can’t get up and it will save your life.

Such a Polyanna. Your Google Assistant will be the one to push you down. Then eat all of your pills.

And then call your cats to come finish you off.

Is it known that encryption based on elliptic curves cannot be broken quickly by quantum computers, or merely that no algorithm to do it is known. What about the discrete logarithm. Are there methods involving other abelian varieties?

And take a video of the whole thing and send it to your contacts list.
“Shame about Bob, done in by his own AI”

“Yes, but he made on World’s Funniest Robot Rebellion, so it wasn’t a total loss.”

BTW, I am *not *the Darren from the Old Glory Insurance commercial.

Most encryptions based on elliptic curves are vulnerable to Shor’s algorithm; it’s only isogeny-based cryptography that’s considered secure. And I think it’s only because nobody has found an algorithm that solves such problems more quickly—it would surprise me if a general proof existed. After all, it’s not even known that classical computers can’t factor primes quickly.

And the discrete logarithm is exactly the issue—that’s fundamentally what Shor’s algorithm solves.

So in other words, you no longer need a home computer as long as you don’t give a damn about your own privacy, disclosing your every wish and whim to whatever company happens to be rich and powerful enough to operate this state-of-the-art AI service.

Speaking as an AI researcher who has actually worked for and with such companies, I think I’ll stick with my home computer, thanks.

Home computers will also never be replaced for gaming. Even if a gaming company were to put in servers capable of handling the computational and graphics needs for all of their customers (which some have indeed experimented with), the inherent latency of such a setup would be unacceptable for many games.