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 Fourier sparse recovery and the optimal error scaling in noisy super-resolution. 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 optimization problems. These results illustrate promising directions for leveraging quantum algorithms to address computational challenges in optimization and machine learning and applying classical techniques to refine and optimize quantum algorithm implementations.

Bio: 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.