" In December 2015, Google and NASA announced that their shared D-Wave 2X quantum annealing computer solved a complex optimization problem up to 100 million times faster than a single-core classic computer did"
IDC, Quantum Computing in the Real World, 2016.
https://www.youtube.com/watch?v=-LhPE6FpJYk
Modern crypto systems (block ciphers) and AES in particular, already took into account the accelaration of exhaustive search by a possible future quantum computer and the key size was double (since exhaustive search via Grover's algorithm is accelerated to square-root(n) rather than n on a quant. computer, see https://en.wikipedia.org/wiki/Grover%27s_algorithm). Thus, 128 and higher was the block/ key size in AES.
BTW: D-Wave seems to be doing something on certain optimization problems, and its influence on cryptography [or quantum computing as defined in other places] is not known/clear.
Breaking the classical public-key encryption schemes faster would require a universal quantum computer to run Shor's algorithm, whereas the D-Wave chip was never meant to be such. It relies on quantum annealing, which, in theory, is equivalent to a universal gate-based quantum computer with a polynomial overhead (see arXiv:quant-ph/0001106), but the connectivity structure of the D-Wave does not allow it. The speedup you cited is a remarkable feat, but keep in mind that the optimization landscape was hand-crafted to fit the hardware best. It was a demonstration of the theoretical maximum speedup in nonconvex optimization problems. It has nothing to do with breaking classical encryption.
While we hear breakthroughs towards a universal quantum computer almost every day, a scalable technology is still far away. Till then, post-quantum crypto has time to evolve, furthermore, quantum key distribution systems are already available from commercial vendors.
https://arxiv.org/abs/quant-ph/0001106
https://en.wikipedia.org/wiki/Post-quantum_cryptography
http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/pqcrypto-2016-presentation.pdf
Newbie question/remark: AES( which is a private key crypto) is not dependent on the prime factorization problem, so the big push of Shor's algorithm is not relevant on AES. Right?
Concerning the answer of Dr. Patricio,
Yes, we can not apply the Shor's algorithm to break the AES cryptosystem, it's private-key cryptosystem.The posed problem in the last one is to find the corresponding key. The quantum computer is faster than classical (see the following paper).
http://springerplus.springeropen.com/articles/10.1186/s40064-016-3159-4
- Badges
- Science topic