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:Is this really a big deal?

[Trepidity]

They only factored the number 15 here as well--- in fact what they implemented was a version of the algorithm compiled to a specialized implementation for the input "15". Their claim from why it's an improvement is (from the full article):

[P]roof-of-principle demonstrations of Shor's algorithm have so far only been possible with liquid-state nuclear magnetic resonance and bulk optical implementations of simplified logic gates, owing to the need for several logic gates operating on several qubits, even for small-scale compiled versions. However, these approaches cannot be scaled to a large number of qubits because of purity, size, and stability limitations of these systems. We demonstrate a compiled version of Shor's algorithm operating on four qubits in which the processing occurs in a photonic circuit of several one- and two-qubit gates fabricated from integrated optical waveguides on a silica-on-silicon chip.

Essentially they claim that, while their demonstration here is as small-scale as the previous ones, it's at least plausible that it might scale up, while the previous demonstrations have inherent limitations that prevent them from scaling up.

Re:Interesting and a qustion

[Trepidity]

Currently, they and the traditional techniques can each manipulate 4 non-error-checking qubits. =]

The article argues that their approach is more promising for scaling up, though, and has fewer inherent limits to doing so. That of course is still to be demonstrated, but the result still seems interesting--- basically, here's proof-of-concept of a new method that at least works as well as previous methods, along with some reasons to believe it might scale up better.

Re:What about ECC?

[Anonymous Coward]

All Discrete-Logarithm and Factoring based public key algorithms are vulnerable.

THe current known safe alternatives are hash-based (Merkle), code based (e.g. McEliece), lattice based (NTRU) or multivariate equation based (HFE). All of them have quite the disadvantages and comparatively less research on them.

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 this really a big deal?

[Dyinobal]

You really don't understand the impact world wide reliable and fast code breaking has. Cryptology has won wars.

Re:Interesting and a qustion

[SpazmodeusG]

No it is frightening now if you transmit anything that still has to be secret in the future. After all someone might simply record both sides of the encrypted conversation now for later reference.
This is why government agencies want secure quantum links now. As even though there is no way for someone to decrypt their plans right now there's still a chance of the plans getting out once quantum computers do come about.

I have a feeling a lot of criminals will find themselves being arrested for past crimes once quantum computers do come about as all their past recorded conversations, no matter how encrypted, suddenly become decryptable.

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).