Google quantum computers are now solving optimization problems that even our most powerful supercomputers can’t crack.
Their new algorithm, called Decoded Quantum Interferometry (DQI), uses quantum interference patterns to find near-optimal solutions. It converts optimization problems into decoding problems, which are well-studied thanks to decades of error correction research [I need to dig a little deeper into this].
For certain polynomial intersection problems, a quantum computer using DQI could solve instances with just a few million quantum operations. The same problem would require over 10^23 operations (one hundred sextillion) on a classical computer using the best known algorithm.
What’s more interesting here is that it now opens new research directions for both classical and quantum algorithms.
I still need to dig deeper into a few aspects of it. But I read the blog post, so I thought of sharing.
Give it a read.