The Doomsday Chip

[jordan179]

Note - I give anyone and everyone my express permission to mirror or otherwise repost this article, anywhere in the world and for all time.

Dedication - To two wonderful friends I have abroad, each of whom has helped me greatly in his and her own way.  My best wishes to both of you -- and keep safe!

IntroductionBack in the 1950's, the Egyptian

Comments

Re: Quantum Computing and Evil Presidents

[irked_indeed]

I'm not sure that you two are really disagreeing except insofar as how many qubits are currently possible in quantum computing.

(For those who are maybe a little less familiar with quantum computing: So, one of the big ways that modern security - RSA, let's say - works is by relying on certain properties of very large prime numbers. It turns out to be very time-consuming to factor a product of two extremely large primes; without doing this factoring, it is difficult/impossible to break the relevant encryptions.

With a sufficiently large quantum computer, though, it's possible to check all possible factorings simultaneously. Don't think of this as the computer being just "faster," or even "orders of magnitude faster": think of this as taking something that formerly took anywhere from a second to a few thousand years and making it always take a flat few seconds.

The reason we can still use things like RSA, then, is that there are - to our knowledge - no quantum computers large enough to allow this kind of work to be done on the kinds of very big primes currently in use. If that stops being true - if quantum computers of appropriate size are developed - everything changes, cryptographically-speaking.)

Re: Quantum Computing and Evil Presidents

[jordan179]

With a sufficiently large quantum computer, though, it's possible to check all possible factorings simultaneously. Don't think of this as the computer being just "faster," or even "orders of magnitude faster": think of this as taking something that formerly took anywhere from a second to a few thousand years and making it always take a flat few seconds.

Well yeah -- that's what I meant by "orders of magnitude faster." An order of magnitude is a factor of 10 -- if something would normally take a millennium and now takes a second, it is roughly 10 orders of magnitude faster, as a millennium is some 30 trillion seconds long.

I think the limitation on quantum computing is resolution of the results -- you have to arrange the circuit very delicately to avoid premature collapse of the wave function and past a certain point of complexity your detection equipment wouldn't be able to figure out what the wave was doing fast enough to be of any use. Wouldn't the ultimate limit on performance here be the Heisenberg one itself, such that sufficiently complex problems would require absurdly large quantum computers?

Re: Quantum Computing and Evil Presidents

[irked_indeed]

An order of magnitude is a factor of 10 -- if something would normally take a millennium and now takes a second, it is roughly 10 orders of magnitude faster, as a millennium is some 30 trillion seconds long.

Right, but it's not so much about the fact that the time is different as it is that the growth of the time is different - we move from time that's super-polynomial on the length of the product to time that's something like linear on the length of the product. That's a bigger deal, from an algorithmic point of view, than even a very large constant-factor speed-up.

Wouldn't the ultimate limit on performance here be the Heisenberg one itself, such that sufficiently complex problems would require absurdly large quantum computers?

*shrugs* Really depends on how far you're willing to push "ultimate," I guess. Quantum computing at a reasonable scale - let's say the storage capabilities of the traditional computers of a few decades ago - would smash anything remotely like current RSA, I think.