Code-Breaking Quantum Algorithm On a Silicon Chip

Urchin writes "Shor's quantum algorithm, which offers a way to crack the commonly-used RSA encryption algorithm, has been demonstrated on a silicon chip for the first time. The algorithm was first demonstrated on large tabletop arrays 3 years ago, but the photonic quantum circuit can now be printed relatively easily onto a silicon chip just 26 mm long. You can see the abstract from the team's academic paper in the journal Science; the full text requires a subscription."

Comments

Interesting and a qustion

[doublebackslash]

So, this is really impressive. I'd also like to know how many (useful, as opposed to error checking) qbits they can manipulate in total using this technique, and traditional techniques, for that matter. Those are the big limiting factors in this technique's use.

Side question: Which asymmetrical encryption algorithms are safe(er) against quantum algorithms (Some algorithms do not benefit from a tremendous quantum speedup, only a large one)?

Re:Interesting and a qustion

[doublebackslash]

As far as being terrified by it, that's fairly easy.

I'm a bit of a crypto nerd (more of a fan, not exactly up to sratch on designing the algorithms, but I've read EXTENSIVELY on their proper use) and if you get a large quantum computer working, things go titsup for any of our currently viable public key crypto schemes. The short of it is this: you can no longer trust any key exchange system that relies on public keys. SSH is no longer secure, SSL is trash, the list goes on. Any time you need to exchange secure data without having previously encountered the far end securely first, game over.

That's frightening. I know that there are some proposed algorithms that only allow for a polynomial speedup in quantum computers, but I couldn't find them between when I posted initially and now.

So yeah, fear it, but in terms of cracking larger numbers this is not even a proverbial "smoke in the building" scenario. It looks like their technique does not employ error checking, making large numbers of qbits near impossible to work with.

Re:Interesting and a qustion

[Captain Segfault]

I think the real question is whether or not quantum computing can solve the Travelling Salesman problem.

It can not.

There is no reason to believe QBP contains NP. (We might be wrong, but then we might be wrong about P != NP!)

Any approach along the lines of "do everything quantumly in parallel and somehow select the interesting results" will do no better than a Grover search, which is a quadratic speedup.

Re:Interesting and a qustion

[mckinleyn]

With a 6-digit UID, I'm sure you know this, but for those who might not have taken a university level computing class (or who took one a long time ago), I'm going to elaborate briefly on your post.

Problems like factoring products of primes (This is a big deal in crypto, but the explanation of why is hard if you haven't taken a university number theory course) and the above-mentioned Traveling Salesman Problem (The question of how I can most efficiently reach each of a given set of points, after given fixed distances between said points) are what we call np-complete. This means, in short, that the amount of time it takes to solve them goes up more and more for each item (point in TS, making the prime gigantic in crypto) you add. It's trivial to factor 15, as shown here, but non-trivial to factor (2 ^ 43112609 -1) * (2 ^ 42643801 -1).

So, yes, if it can solve the traveling salesman problem (in polynomial time. Solving it is easy, unless you consider that with enough nodes, it'll take until the heat death of the universe), it IS a big deal for modern crypto because it shows that np-complete problems (whose only REAL issue is that they are computationally difficult) can be solved in a realistic amount of time, and most modern crypto counts on the fact that it cannot.

Re:Interesting and a qustion

[wurp]

As far as I know, the "only" crypto applications of QC that would give an exponential speed-up are for factoring (Shor's algorithm). I realize that that's essentially all currently used asymmetric (public/private key) encryption, but afaik elliptical encryption, which is also usable for asymmetric encryption, isn't impacted.

Of course, no one knows if elliptical encryption will fall to some quantum algorithm, and you can always get a O^0.5 speed up using Grover's algorithm, but O^0.5 just requires double the key length rather than making encryption impractical.

Scott Aaronson, a quantum algorithm complexity researcher at MIT, believes that quantum computing does not in general give an exponential speed-up to algorithms, and I believe him...

Re:Interesting and a qustion

[mark-t]

It's only frightening when operating a quantum computer becomes trivial.

So not anytime soon... the refrigeration units required to produce the temperatures at which quantum computing is viable are not likely to be within a typical consumer's budget (or likely to fit in their apartment, for that matter) for the forseeable future.

Re:Is this really a big deal?

[Hal_Porter]

http://en.wikipedia.org/wiki/Ultra#Battle_of_the_Atlantic

It is commonly claimed that breaking of German Naval Enigma shortened the war by a year, but given its effects on the Second Battle of the Atlantic alone, that might be an underestimate.

An exhibit in 2003 on "Secret War" at the Imperial War Museum, in London, quoted British Prime Minister Winston Churchill telling King George VI, "It was thanks to Ultra that we won the war." Churchill's greatest fear, even after Hitler had suspended Operation Sealion and invaded the Soviet Union, was that the German submarine wolf packs would succeed in strangling sea-locked Britain. He would later write, in Their Finest Hour (1949), "The only thing that ever really frightened me during the war was the U-boat peril." A major factor that averted Britain's defeat in the Battle of the Atlantic was her regained mastery of Naval Enigma decryption.