Combinatorics Colloquium
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Altgeld Hall 245
- Date
- May 19, 2025 11:00 am
- Speaker
- Asaf Ferber (UC Irvine)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 71
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).