Solving optimization problems on quantum systems.

Solving industry-related optimization problems using classical computers is challenging as they are NP-hard. The current era of quantum computers is characterized by a limited number of qubits, high levels of noise, and imperfect quantum gates. Despite these limitations, exploring resource-efficient encoding schemes for such problems is motivated by the potential of achieving practical quantum advantage. These problems are typically formulated either as a quadratic unconstrained binary optimization (QUBO) or integer programming (IP). Our first work provides a novel framework to solve QUBO problems such as Maximum Cut (Max-Cut) and Maximum Independent Set (MIS) on the Rydberg platform, providing a more favorable scaling of the number of atoms with problem size compared to existing schemes. Using locally controlled light shifts on Rydberg atoms, we establish a one-to-one mapping from the graph problems (MIS/Max-Cut) to a many-body interacting setup. In our second work, an algorithm is introduced that directly solves an IP problem using a single atom. Specifically, we use multi-levels of a Rydberg atom and selectively transfer the population between the Rydberg manifolds to find the optimal solution. Both of the quantum algorithms utilize quantum optimal control to reach the solution of the problems. They are also benchmarked against the respective classical algorithms, where our schemes performed better in terms of the number of iterations to converge to the solution with respect to the complexity of the problems.