Seminar: Bridging Quantum and Classical: New Horizons in Algorithm Design for Optimization and Machine Learning
Ruizhe Zhang
Quantum Postdoctoral Fellow
Simmons Institute for the Theory of Computing
UC Berkeley
Wednesday, March 5
9:30 - 10:30AM
1100 Torgersen Hall
Abstract
Quantum computing has the potential to outperform classical computing; however, our understanding of where its advantages may be found is still limited. Meanwhile, AI and machine learning demonstrate remarkable performance but face significant challenges in training and deployment due to their high computational demands. In this talk, I will present theoretical results that explore the interplay between quantum and classical algorithm design, highlighting their potential to advance optimization and machine learning. I will first introduce an early fault-tolerant approach to quantum phase estimation (QPE), a powerful quantum method for solving the eigenvalue problem for exponentially large matrices. By incorporating classical signal processing techniques, we show that QPE can achieve high accuracy with minimal quantum resources. Motivated by this, I will discuss our research on spectral estimation and super-resolution, achieving optimal error scaling for recovering signal frequencies from coarse-grained and noisy measurements. This result resolves a long-standing open question in classical signal processing and advances quantum algorithm design. Finally, I will present quantum algorithms for classical sampling and related optimization problems, showcasing an exponential improvement in an online learning task. These results illustrate promising directions for leveraging quantum algorithms to address computational challenges in optimization and machine learning and for applying classical techniques to refine and optimize quantum algorithm implementations.
Biography
Ruizhe Zhang is currently a Quantum Postdoctoral Fellow at the Simons Institute for the Theory of Computing at UC Berkeley. Before joining the Simons Institute, he obtained his PhD in Computer Science in 2023 from the University of Texas at Austin, where he was advised by Dana Moshkovitz. His research interests center on the intersections of quantum computing, theoretical computer science, and the foundations of machine learning. He was previously awarded the University Graduate Continuing Fellowship at UT Austin.