A new quantum toolkit for optimization

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.