Quantum algorithm for integer programming using synthetic dimensions

Integer programming (IP) is an integer-variable optimization problem under given constraints. It is quite common for typical industry-related optimization problems such as warehouse assignments to have discrete variables and are generally formulated in terms of IP, which falls into the category of NP-hard problems. Such NP-hard problems are ideal candidates to solve on a quantum device to establish an advantage over classical algorithms. The current approaches involve reformulating the IP into an unconstrained form through the use of binary variables, which is an indirect and resource-inefficient process. We introduce a quantum algorithm that directly maps and solves an IP problem to any quantum system possessing multiple internal degrees (similar to synthetic dimensions). The resources required for this mapping are minimal as a selective superposition of the internal states in an atom can encode the problem. Specifically, we use multi-levels of a single Rydberg atom and utilize quantum optimal control to selectively transfer the population between the Rydberg manifolds to find the optimal solution. We choose a few prototypical IP problems with varying difficulty including the ones with non-linearity, that are usually harder to solve classically. We benchmark our quantum algorithm with a classical Branch & Bound method, where the quantum version has two advantages, a smaller number of iterations needed for convergence and getting better bounds than the standard classical algorithm.