Last updated on 2012-12-11
You are probably asking yourself what the hell is going on here. Obviously 15=3×5, and not half the time, but all the time. But in the world of computer science, quantum computing and the academy, things are a bit different. Quantum computers are a “new” kind of computational machines, that from what I understand behave similarly to non-deterministic Turing machines, but I’m no expert on the subject.
What the researchers did was to execute a theoretical quantum-computing algorithm that does prime factoring in a real quantum computer (see the press release). The result (that 15=3×5 about 50% of the time) was the expected result of the algorithm, so it worked. And this is important because prime numbers and their factors are key players in modern public key encryption schemes like RSA, because factoring a large prime number is considered a hard problem. But if you have a machine that can factor prime numbers really fast (like a quantum computer), and it gives you the right solution half of the time… you can break public-key encryption half the time. And this is very bad for all of us (not the new computer, but the new lack of security). For now, quantum computers are limited to a very small number of bits, so this is not a real problem yet, but technology sometimes advances in leaps, so we must beware.
And this is the reason this result, while sounding strange, is very interesting and important (IMHO).