by BENJAMIN SCHIFFER, Max Planck Institute of Quantum Optics, Garching, Germany
Optimization problems are ubiquitous in industry and quantum computers offer the potential to solve them with a scaling advantage over classical computers. The recent experimental progress in Rydberg atom arrays, which offer flexible geometries of hundreds of qubits, has led to investigations into their potential as a platform for solving such problems. Notably, the Hamiltonian describing this physical system closely resembles the cost function of the Maximum Independent Set (MIS) problem, which is an NP-hard optimization problem.
In this talk, I present a variational adiabatic quantum algorithm that significantly improves upon the standard adiabatic algorithm and has been experimentally tested against the quantum alternating operator ansatz (QAOA) on Rydberg atom arrays. We provide numerical evidence of a scaling advantage of the variational adiabatic quantum algorithm over simulated annealing for the MIS problem on average king’s graphs, and identify a specific class of graphs where the quantum algorithm fails due to a provable super-exponential runtime as a function of system size. These results offer insights into the potential current and future utility of Rydberg atom arrays for solving optimization problems.