Solving optimization problems with local light shift encoding on Rydberg quantum annealers*

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, neutral atom analog quantum computers offer opportunities to explore potential advantages. Combinatorial optimization problems that are NP-hard, for example, Maximum Cut (Max-Cut) and Maximum Independent Set (MIS), are interesting to tackle on a quantum computer. In contrast to the well-known schemes such as unit disk encoding and quantum wires, we provide a novel framework to solve the MIS/Max-Cut problems on Rydberg platforms. It involves taking advantage of locally controlled light shifts on Rydberg atoms to establish a one-to-one mapping from the graph problems (MIS/Max-Cut) to a many-body interacting setup. This approach has the advantage of linear scaling of the number of atoms required with the problem size. 

Optimal control methods are used in our numerical simulations to shape the laser pulses for driving the Rydberg annealer to the desired many-body ground state, which solves the optimization problem. The solutions are obtained for prototype graphs with varying sizes at time scales well within the system lifetime and with approximation ratios close to one. A comparative analysis with classical simulated annealing is made which highlights the advantages of our scheme in terms of system size, hardness of the graph, and the number of iterations required to converge to the solution.