Code-Breaking Quantum Algorithm On a Silicon Chip 133
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."
Re:How many qubits? (Score:5, Insightful)
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".
Re:Interesting and a qustion (Score:5, Insightful)
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 (Score:5, Insightful)
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:Is this really a big deal? (Score:3, Insightful)
Outside of science fiction novels, where did it do that? If you're thinking of WWII, the Allies had a gigantically larger industrial base than the Axis could ever summon, and basically won by throwing enough men and materiel at the problem. At most, crypto might have shortened that war, but even that's not crystal clear.
Re:Is this really a big deal? (Score:5, Insightful)
Breaking Enigma helped get those men and materiel past the U-boats. If they hadn't D-day wouldn't have happened (and it was almost a failure even with the resource there) and the Germans wouldn't have been caught in a pincer between the allies and the soviets. I wouldn't discount its influence.
Re:What about ECC? (Score:3, Insightful)
Sweet, thanks for the awesome pointers. You've given me a whole lot of stuff to look over as a research starting point.
Re:Can someone explain this... (Score:1, Insightful)
Quantum Entanglement isn't some esoteric, exotic process we can only observe in a laboratory, it pervades the universe continuously. Most of the particles in your body are probably entangled with most of the particles in your keyboard right now.
We don't need rare materials and expensive equipment, entanglement sortof just happens on its own. The tricky part is shielding them from what's called decoherence: The qubits we're trying to do computations with tend to want to become entangled with particles that aren't a part of the system. This can screw things up pretty badly. It's a lot like Windows getting a BSOD when you decide to pick your nose.
That said... not all problems are instantly sped up just because you're working with qubits instead of normal bits. The problems that get a speedup all have a few common traits.
With a Quantum Computer, when you use a quantum logic gate, essentially every possible value is computed at once (in reality it's not that simple, but that's beyond the scope of this comment). However, when you attempt to measure the state of the qubits, it'll "snap" into any of the results, and this cannot be controlled. So you can perform "2*x" on 1..8, but the probability of actually getting the answer you want gets lower and lower as you take advantage of quantum parallelization more and more.
However, sometimes you don't want to know a specific answer, you want to know something about all of them. For these problems, Quantum Computers win. This is how Shor's Algorithm works.
Anyway, there are plenty of encryption methods that aren't vulnerable to Quantum Computers, like Lamport Signatures, for example.