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

Re:Interesting and a qustion

[Dc0der]

There are a few algorithms resistant against quantum computers, based on alternative problems. A good reference of the main, usable ones, is at http://pqcrypto.org/. Quantum computers can also speed up exhaustive searches (see Grover's algorithm) and collision searches, but this is easily mitigated by increasing symmetric key sizes to e.g. 256 bits up from 128.

Re:Is factoring np-complete?

[Trepidity]

You're right, it isn't currently known either way.

To review briefly,

P problems are those solvable in polynomial time on a regular computer.

NP problems are (one definition) those verifiable in polynomial time on regular computers. That is, if you gave the answer to the problem, in polynomial time I could tell you if it was the correct one.

QBP problems are those solvable in polynomial time on a quantum computer.

It is not known whether any of these classes are equivalent. However, the possibilities are constrained by,

NP-complete, which are problems in NP to which all other NP problems can be reduced (provably!) in polynomial time.

Traveling salesman is NP-complete. Therefore, if we found a polynomial-time algorithm on regular computers, P = NP. If we found a polynomial-time algorithm on quantum computers, QBP = NP.

Integer factorization is in NP, but not known to be either NP-complete or in P. Therefore, a polynomial-time algorithm on regular computers could exist without P = NP--- but we don't know of one. Shor's algorithm (the subject of this article) is a polynomial-time algorithm for quantum computers, so integer factorization is in QBP. However, since integer factorization isn't NP-complete, this doesn't have any implications for whether QBP = NP or not.

So it's not provably known that integer factorization is easier than traveling salesman on any kind of computer. But on quantum computers, the fastest known integer factorization algorithm is polynomial, while the only way we could do that for traveling salesman is if QBP = NP. On regular computers, no polynomial algorithm is known for either problem. But in a sense it'd be more surprising if one were found for traveling salesman, because that would imply P = NP... while finding one for integer factorization wouldn't have such wide-ranging implications on other problems (though it might have implications for other not-yet-known-to-be-in-P problems, if the technique were transferable).