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

[Brian Gordon]

My guess is that miniaturizing a optical processor into silicon is probably going to be less powerful than normal optical processors. They should be factoring numbers larger than 15 before trying to fit it on a chip.

Quantum computing is extraordinarily difficult though, even just in theory, so I guess I understand why its development is so slow.

I wonder what the curve is for how much education you need to be terrified of the Shor's algorithm article rather than just mystified, and then how much more you need to master it. I'm deep into nightmare territory.

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: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

[maxume]

It's only frightening when operating a quantum computer becomes trivial. Until then, it really isn't that big a deal to send your credit card details to Amazon.com. So when there are 5 powerful quantum computers running, there will probably still be a year or two to fix things. Even then, I'm not sure people will be running quantum computers against the vast majority of communication (so it really only sucks for the people who are trying to secure something worth getting at, us gmail https users aren't out much).

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.

MIM day

[youn]

shortly after, secret service agencies worldwide have decided to make the day a holiday and call it man in the middle day (MIM)

Re:How many qubits?

[Trepidity]

That's their claim. The full version of the article says of previous implementations, "these approaches cannot be scaled to a large number of qubits because of purity, size, and stability limitations of these systems". And of theirs: "Although it currently uses an inefficient single photon source and modest efficiency detectors, ongoing progress to address heralded gates and efficient sources and detectors combined with the results presented here will allow large-scale quantum circuits on many qubits to be implemented".

Version 2

[epine]

int a = 0, b = 0;
if (x == 14) { a = 2; b = 7; }
else
if (x == 15) { a = 3; b = 5; }
if (a == 0)
    printf ("%s\n", "more funds required");
else
    printf ("%d, %d\n", a, b);

Re:changing of the guard

[BungaDunga]

Unless you're using 3 and 5 for your factors, I think you're safe for now...

Re:changing of the guard

[sakdoctor]

That's the kinda factors an idiot would have on his luggage.

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