Exploring the Potential of Rydberg Atom Arrays for Solving Optimization Problems: Optimized Adiabatic Sweeps, Algorithmic Breakdown, and Quantum Speedup

by Mr Benjamin Schiffer (Max Planck Institute of Quantum Optics)

Friday 12 May 2023, 11:30 → 13:30 Europe/Stockholm

Albano 3: 6228 - Mega (22 seats) (Albano Building 3)

Optimization problems are ubiquitous in industry and quantum computers offer the potential to solve them with a scaling advantage over classical computers. The recent interest 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 graphs, and identify a specific class of graphs where the quantum algorithm fails due to its requirement of a 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.
 

Join Zoom Meeting
https://stockholmuniversity.zoom.us/j/61480529419