A new quantum toolkit for optimization

From designing more efficient airline routes to organizing clinical trials, optimization problems are everywhere. Yet for many real-world challenges, even our most powerful supercomputers struggle to find the best solution. This has led to a major, decades-long question in quantum computing: could quantum machines succeed on optimization problems where classical ones fall short? This has proven to be a very difficult mathematical question, which remains largely open. As the capabilities of quantum hardware undergo rapid advancement, such theoretical problems of working out the eventual commercial and scientific use cases of large-scale error-corrected quantum computers become only more urgent.

In a recent Nature paper, researchers from Google Quantum AI and collaborators from Stanford, MIT, and Caltech shed new light on this question. We introduce an efficient quantum algorithm — called Decoded Quantum Interferometry (DQI) — that uses the wavelike nature of quantum mechanics to create interference patterns that converge on near-optimal solutions that are incredibly difficult to find using classical computers.

A quantum link between optimization and decoding

There is a catch, however. To build the necessary interference patterns, one must solve another hard computational problem called decoding. In a decoding problem one is given a lattice and a point in space, and one needs to find the nearest lattice element to the point. For example, the corners of the squares on a chessboard form a two dimensional lattice. After dropping a grain of sand at a random location on a chessboard, the decoding problem would be to find the nearest corner. Although this problem is easy for a square lattice in two dimensions, it can become very difficult on some lattices in hundreds or thousands of dimensions.