traq;11029579 wrote:the advantage of quantum computing, IIUC, is in its ability to represent multiple states at once. Where a normal bit is either 1 or 0, a quantum bit is either 1 or 0 and may also be 0 or 1 (or vice versa) at the same time. I don't know the actual algorithm, but I've read (for example) that a 16-bit machine could represent 216 states at any given time.
That sounds somewhat more concise. I have this vague feeling (not backed by any actual study) that the computer's ability to use this uncertainty relies on nudging the computer toward the optimal solution by somehow taking advantage of some basic laws of physics or something which sort of suck the uncertain states toward certain ones in such a way to avoid violating some kind of constraint.
traq;11029579 wrote:The disadvantage is that calculations are not deterministic: the answer to a math routine might be correct and might not. If you'll pardon me, I have to go read wikipedia footnotes now.
A Douglas Adams episode comes to mind.
The wikipedia article on QC does offer a little more detail regarding encryption:
other existing cryptographic algorithms do not appear to be broken by these algorithms.[14][15] Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory.[14][16] Lattice-based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice based cryptosystems, is a well-studied open problem.
Regarding the impact of QC on encryption, two questions arise:
1) Are these other algorithms commonly used for encryption or does most encryption currently rely on the algorithms vulnerable to Shor's algorithm?
2) Is there yet a viable, working QC computer than actually crack anything?
Regarding #2, this article looks interesting: http://www.technologyreview.com/news/514846/google-and-nasa-launch-quantum-computing-ai-lab/