Jul 17 – 22, 2022
Royal Conservatory of Music, Toronto
America/Toronto timezone

Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays

Jul 20, 2022, 5:00 PM
1h 30m
Hart House (Hart House)

Hart House

Hart House

7 Hart House Cir, Toronto, ON M5S 3H3
Poster presentation Quantum information: gates, sensing, communication, and thermodynamics Poster session


Realizing quantum speedup for solving practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays composed of up to 289 coupled qubits in two spatial dimensions, we experimentally investigate quantum optimization algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of nonplanar graphs with programmable connectivity. We find that the problem's hardness is controlled by the solution degeneracy and the number of local minima, and experimentally benchmark the quantum algorithm's performance against optimized classical simulated annealing. On the hardest instances, we observe a superlinear quantum speedup in finding exact solutions for sufficiently long evolution times beyond the shallow-circuit-depth regime, and analyze its origins.

Presenter name Sepehr Ebadi
How will you attend ICAP-27? I am planning on in-person attendance

Primary authors

Presentation materials

There are no materials yet.