Why are quantum computers (going to be) important?

[psychonaut]

@Chronos

The biggest one is that, if we could get them to work, quantum computers could quickly solve the sorts of problems which currently serve as the backbone for all of our cryptography. If you had a decent-sized quantum computer right now, and nobody was forewarned about it, you could rob banks. All of them, at once, completely.

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.

[Textual_Innuendo]

@psychonaut

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

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.

[Bone]

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.

[DPRK]

@Textual_Innuendo

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.

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

[Textual_Innuendo]

@DPRK

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.

[Jragon]

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:

@Jragon

I’m not a quantum physicist, but I am familiar with computational complexity theory, and have some knowledge about quantum complexity classes. My answer is no.

The issue you’re describing is a matter of throughput, not complexity. It is inherently parallelizable throughput, but still a throughput issue. A fractal is just a really, really long series of computations. Bigger resolutions mean more computations have to be done, but bigger resolutions can also be computed in parallel chunks by farming different parts of the image off to multiple cores (though some of this depends on how sequential your fractal generation technique is).

This is just a lot of computation, but nothing is really unknown. You’re never enumerating possibilities and guessing their candidacy, everything is known a priori.

What quantum computers theoretically excel at are certain variations of classes of problems known as “promise classes”. One of the classic “promise classes” is BPP or “Bounded-error Probabilistic Polynomial time”, that is, the set of problems such that, given a question, you can check very quickly whether:

1. If the answer is ‘yes’ then at least 2/3 of all possible computation paths accept.
2. If the answer is ‘no’ then at most 1/3 of all possible computation paths accept.

In fact, BPP is contained in BQP, which is one of the simpler quantum classes. Meaning a quantum computer can solve all BPP problems in polynomial time with error no more than a 1 in 3 chance of making an error. Or, more simply, a quantum computer can solve these problems quickly.

Technically, this means BQP can solve P problems, like fractal generation, as well. However, it won’t be any faster at this. This is because any computer that can solve a higher complexity class problem generally solves a less complex problem by merely simulating a less powerful machine. (There are a few exceptions here, I think)

Basically quantum computers aren’t inherently any “faster” it’s just that they can solve more types of problems. The reason we may describe them as “faster” is that our current computers can solve these problems, but they do it by simulating a more powerful machine. Essentially, our current computers enumerate possibilities, guess, and check whereas a more powerful machine could simply try all guesses at once (I’m being imprecise here, but that’s the gist). This is extremely, extremely slow.

In fact, almost all of these classes I’m describing are defined in terms of being able to solve a certain class of problem as fast as a current computer. BQP is effectively saying “a machine that can solve BQP can solve quantum problems as fast as a normal computer solves non-quantum problems”. It makes no claims about how fast it can solve problems that a normal computer already can solve.

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.

[Chronos]

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.

[dstarfire]

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/

[Ruken]

@dstarfire

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?

[rat_avatar]

@Chronos

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.

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.

https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf

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

[albino_manatee]

@Ruken

" Note that we don’t have anywhere close to 250 qubit computers available right now. "

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.

IBM makes 20 qubit quantum computing machine available as a cloud service –...

[Ornery_Bob]

@Mrdeals

I watched a short documentary on QC, and the whole thing kind of made me say “why?”
(According to the doc) never intended to be consumer friendly

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.

[Darren_Garrison]

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

[mind_the_gap]

@Darren_Garrison

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.

[Hari_Seldon]

@Textual_Innuendo

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.

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?

[dtilque]

@mind_the_gap

And then call your cats to come finish you off.

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

[Darren_Garrison]

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

[Half_Man_Half_Wit]

@Hari_Seldon

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?

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.

[psychonaut]

@Ornery_Bob

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.

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.

[Chronos]

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.