News for hackers. Stuff that matters.
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by Volpe on Sunday April 07, 2013 @02:44AM (#5506342)
So does this mean Shor's Algorithm is going to kick in for real and ruin all our securityz?
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by adrianhoward on Sunday April 07, 2013 @03:38AM (#5506429)
So does this mean Shor's Algorithm is going to kick in for real and ruin all our securityz?

Nope.

First, as I understand it, the D-Wave stuff isn't a system that can run Shor's.

Second, Shor's only ruins security for a certain class of crypto algorithm. There are already algorithms that exist today that a proof against it (e.g the McEliece cryptosystem http://en.wikipedia.org/wiki/McEliece_cryptosystem).

Third, if you're really worried about the man cracking your s3cr3t stuff with quantum computers go pick the right cryptosystem ;-) Plenty of symmetric encryption systems that only get their key lengths reduced (effectively halved) by Grover's algorithm.

Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by daeken on Sunday April 07, 2013 @04:56AM (#5506568)
People tend to equate asymmetric crypto with the likes of RSA; systems where the efficient factoring of large numbers is a death sentence. But there's a whole slew of other asymmetric cryptosystems without such properties, e.g. elliptic-curve cryptography.
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by forTheRecord on Sunday April 07, 2013 @05:52AM (#5506665)
Shors algorithm also breaks elliptic-curve cryptography.
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by daeken on Sunday April 07, 2013 @05:55AM (#5506671)
Oh, wow, I've never seen the variant that breaks ECC; that's really quite awesome. Time to read some papers!
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by adrianhoward on Sunday April 07, 2013 @07:15AM (#5506818)
Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202 is what you want ;)
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by Devilboy on Sunday April 07, 2013 @07:10AM (#5506805)
This is not correct anymore, according to D-Wave they do have a factoring algorithm now.
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by adrianhoward on Sunday April 07, 2013 @07:31AM (#5506855)
Interesting. Do you have some pointers to that?

I thought both the D-Wave 1 & 2 both had specialist quantum chips that couldn't run Shor's.

Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by Devilboy on Sunday April 07, 2013 @07:53AM (#5506885)
Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by adrianhoward on Sunday April 07, 2013 @09:05AM (#5507071)
Hmmm... can't find anything else on that apart from the mention in that blog post. Is there more detail anywhere?

They also implicitly state that it's not Shor's which is (to the best of my knowledge) the most effective integer factorisation algorithm for general purpose QCs currently know.

They also say that they "have a factoring algorithm". They don't say that it's actually implemented on running hardware.

I also notice the complete lack of clarification on the followup question that poked on the explicit "executed it on real hardware" question ;-)

Re:Lockheed Martin pays $10M for D-Wave's Quantum Computer by jd007 on Sunday April 07, 2013 @02:50AM (#5506348)
Probably not anytime soon. Right now a 4 year old kid can beat the best implemented Shor's algo (http://www.nature.com/nphoton/journal/v6/n11/full/nphoton.20...).