Speaker: Asaf Ferber (UC Irvine)
Title: Quantum Algorithms on Graphs
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 Δ.
This work is based on joint research with Liam Hardiman (UCI) and Xiaonan Chen (UCI).