Quantum Algorithms on Graphs
Asaf Ferber (UC Irvine)
Monday, February 23rd, 2026, 3-4pm
Abstract:
In this talk, I will provide a brief introduction to quantum computation and demonstrate its potential for accelerating classical graph algorithms. Specifically, I will present an asymptotically tight result for learning a Hamiltonian cycle using OR queries, as well as a significant polynomial improvement on the best-known quantum algorithm for (Δ+1)-coloring a graph with maximum degree Δ. We will also discuss graph states and the problem of finding large independent sets in locally-complementation equivalent graphs to random graphs.
This work is based on joint research with Liam Hardiman (UCI) and Xiaonan Chen (UCI), and on joint work with Xiaonan Chen, Kenneth Goodenough and Marcelo Sales.