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.

Fortunately, decoding problems have been extremely well studied over the past several decades, mainly due to applications in correcting errors incurred during data storage or transmission. Many sophisticated and powerful algorithms have been devised to solve decoding problems for various specially structured lattices. We have discovered that for certain kinds of optimization problems, the related decoding problems have the right kind of structure to be solved by some of these powerful decoding algorithms. However, it is only through the power of quantum computing that these decoding algorithms can be leveraged to also solve optimization problems. By pairing the quantum interference of DQI with these sophisticated decoding algorithms, a sufficiently large quantum computer could find approximate solutions to these optimization problems — solutions that appear to be beyond the reach of any known classical method.

This mathematical discovery of a quantum algorithm that offers speedup for optimization improves our understanding of the eventual use cases for quantum computers. When quantum computing hardware is advanced enough, researchers can use the DQI algorithm to solve classically challenging optimization problems.

A clear quantum win: Optimal polynomial intersection

In this work, our best result is for a problem that we call optimal polynomial intersection (OPI). In the OPI problem, one is given a list of target points and wishes to intersect as many as possible by tuning the coefficients of a polynomial whose degree is lower than the number of points. This is a common task in data science known as polynomial regression. Variants of this problem have arisen in the context of digital error correction as well as cryptography. Consequently, sophisticated algorithms have been developed for solving it in certain special cases, but for other cases, the problem remains hopelessly difficult to solve using known algorithms with conventional classical computers.

Using DQI, a quantum computer could convert this into a problem of decoding Reed-Solomon codes (a widely-used family of codes found in DVDs and QR codes). Very good decoding algorithms have been developed for decoding Reed-Solomon codes, and as a result, quantum computers using DQI can find better approximate optima to the OPI problem than can be found by known algorithms on classical computers. For example, our analysis shows that certain examples of the OPI problem could be solved by quantum computers using only on the order of a few million elementary quantum logic operations which would require over 1023 (one hundred sextillion) elementary operations to solve on a conventional classical computer using the most efficient known classical algorithm.

Where does the quantum advantage come from?

Taking a step back, we can ask why converting optimization problems into decoding problems should ever be advantageous in the first place? By understanding this more deeply, one could hope to gain intuition to guide the search for additional optimization problems on which quantum computers may provide advantage.

Both the optimization problems that we start with and the decoding problems that we convert them into are something called NP-hard problems. This suggests that it is impossible to efficiently find exact solutions to all instances of these problems, even with the help of quantum computers. By using quantum effects, DQI has converted one hard problem into another hard problem. How does this accomplish anything? The key is that the NP-hardness speaks to the difficulty of the very hardest instances of a given problem. If the problem instances are restricted to have some additional structure, this can make them easier. The promise of DQI is that certain kinds of structure may make the decoding problem much easier, without also making the optimization problem easier to solve using conventional computers.

In the OPI problem, the lattice that arises is algebraically structured; the components of the basis vectors, instead of being arbitrary, are obtained by raising a number to successively higher powers. This algebraic structure is reflected in both the original optimization problem (OPI) and the decoding problem that quantum computers can convert it into (Reed-Solomon decoding). This structure makes the decoding problem much easier, but as far as we can tell does not make the optimization problem easier for conventional computers. In this circumstance, the ability to convert the optimization problem into the decoding problem, using the power of quantum computing, provides advantage.

Random sparse optimization problems: A tantalizing challenge

In the paper, we also consider more generic lattices that lack algebraic structure but whose basis vectors are sparse, i.e., consisting mostly of zeros. The corresponding optimization problem is called max-k-XORSAT and is illustrated below. The sparsity of the lattice is reflected in the fact that each of the constraints involves only a few of the variables (at most k). In max-k-XORSAT there are more constraints than variables and it is impossible to satisfy all of them. Instead, one wishes to find a solution that satisfies as many constraints as possible. Though it may sound abstract, the max-k-XORSAT problem is commonly used as a testbed for new optimization algorithms and includes a number of other well-known optimization problems as special cases, such as max-cut and QUBO.

DQI can convert max-k-XORSAT into a decoding problem for codes defined by sparse matrices. Such codes are called low density parity check (LDPC) codes. It was discovered in the 1960s that sparsity makes the decoding problem much easier. However, the sparsity of the original max-k-XORSAT problem also makes it easier to solve on conventional computers using an algorithm called simulated annealing. Thus, it is hard to find max-k-XORSAT problems that have just the right sparsity so that the decoder is helped more than the simulated annealing algorithm that we are comparing against. In the paper we present one example problem where the sparsity is just right so that DQI appears to have a speed advantage over simulated annealing. However, we managed to solve this efficiently on a conventional computer using a specialized algorithm that we tailored to our example. So, at present, unlike for OPI, we do not have an example of a max-k-XORSAT problem that both can be solved by DQI and cannot be solved efficiently by any known algorithm running on conventional computers.

Since sparse optimization problems have widespread practical applications, we continue to search for ways that DQI might achieve quantum advantage on sparse optimization problems. In particular, DQI has motivated new lines of research into both classical and quantum algorithms for decoding LDPC codes.

Prospects

The DQI algorithm provides a powerful new toolkit for developing quantum optimization algorithms. This approach of translating optimization problems into decoding problems offers a new way to address one of the longest-standing questions in the field. We are excited to see what researchers, both at Google and in the broader community, will build with these tools.