Quantum optimization through atomic quantum simulations of spin glasses

Spin glasses have been attracting continuous research interest in the field of condensed matter physics. Their ground state also encode different computation problems including NP hard ones. In this talk, I will present several protocols for quantum simulations of general spin glass models considering atomic tweezer arrays, and describe how to use such quantum simulations to solve difficult optimization problems. We construct a quantum wiring scheme, and establish a mapping from spin glass models on a graph to completely local Ising models on a cubic lattice, which allows quantum simulations of non-local spin glass models by Rydberg atoms having finite-range interactions. Considering atoms in an optical cavity, we find that this system naturally encodes the number partition problem. We construct an explicit mapping for the 3-SAT and vertex cover problems to be efficiently encoded by the cavity atom cavity system, which costs linear overhead in the number of atomic qubits. Our theory implies atomic systems are promising for demonstrating practical quantum advantage.