Re:Quantum computing device hints at powerful future
by wlievens on Tuesday March 22, 2011 @06:18AM
(#2353729)
Shor's algorithm is the classic (pun intended) example:
http://en.wikipedia.org/wiki/Shors_algorithm
Re:Quantum computing device hints at powerful future
by Jach on Tuesday March 22, 2011 @10:54AM
(#2354627)
I think this is a better writeup: http://www.scottaaronson.com/blog/?p=208
Re:Quantum computing device hints at powerful future
by retube on Tuesday March 22, 2011 @06:21AM
(#2353740)
Factorisation is the common example. You'll be able to factor gigantic numbers like an RSA public key pretty much instantaneously, as thanks to a qubit's super-position of states you can operate on all possible states at once. But in general it's all about parallelisation - being able to perform an operation on all states (ie numbers) at once. Due to the probabilistic/uncertain nature of measurements of a quantum system though I believe operations have to be performed a number of times in order to build statistics around the "right" answer.
Re:Quantum computing device hints at powerful future
by trotsky on Tuesday March 22, 2011 @08:55AM
(#2354084)
While the other answer about factorization hit the nail on the head, let me say it again in more direct terms. There is a strong belief among those who pay serious attention to encryption (NSA, etc.) that quantum computing would/will render all traditional encryption (minus things like one time pads) obsolete. An actor with a sufficiently advanced quantum computer would be able to break everyone else's comms.
Re:Quantum computing device hints at powerful future
by maggit on Tuesday March 22, 2011 @09:40AM
(#2354266)
I understand how quantum computers can break RSA; by factoring numbers quickly. That's exploiting a known "weakness" in RSA.
I'm curious as to how quantum computers would break other encryption algorithms like AES or ElGamal. Do you have any details?
Re:Quantum computing device hints at powerful future
by NickM on Tuesday March 22, 2011 @10:04AM
(#2354361)
There's much more concern with asymmetric algorithms like RSA or elliptic curve crypto. I don't know the details on symmetric ciphers like AES, but nobody really seems to be worried about them.
However, it's also not necessarily true that all asymmetric cryptosystems would be broken by quantum computing. For example, the McEliece cryptosystem is gaining attention lately because it's not known to be vulnerable to any quantum attacks. If you're interested in finding out more, google for post-quantum cryptography; there's lots of interesting info out there.
Re:Quantum computing device hints at powerful future
by trotsky on Tuesday March 22, 2011 @03:18PM
(#2355961)
I was repeating it as explained to me by someone whose opinion I trust, however it seems likely now that I misunderstood or perhaps it was being simplified for me. I should know better than to comment on issues like that that I don't fully understand. Thanks for correcting me.
Re:Quantum computing device hints at powerful future
by maggit on Tuesday March 22, 2011 @06:43PM
(#2356882)
Hehe, well, don't think of it as "correcting". I didn't (and still don't) understand it fully myself, so you should thank me for clearing things up or something instead :)
Re:Quantum computing device hints at powerful future
by mchouza on Tuesday March 22, 2011 @12:01PM
(#2354963)
Quantum algorithms halve the "strength in bits" of symmetric encryption algorithms by using the Grover's search algorithm (AFAIK):
Re:Quantum computing device hints at powerful future
by danparsonson on Tuesday March 22, 2011 @09:44AM
(#2354287)
You might find this useful: http://michaelnielsen.org/blog/quantum-computing-for-everyon...
can anyone describe a program which cannot be written (efficiently) today, which might run on quantum computers eventually?