Virtual Talk: Fast algorithms for quantum signal processing

Yulong Dong
University of California, Berkeley (UC Berkeley)

The recently developed quantum singular value transformation (QSVT) [Gilyen, Su, Low, Wiebe, STOC 2019] provides a unified viewpoint of a large class of practically useful quantum algorithms. At the heart of QSVT is a perhaps new way of representing polynomials, called quantum signal processing (QSP), which encodes a polynomial using parameterized products of matrices in SU(2). For a given polynomial, finding the parameters (called "phase factors") is a challenging problem. I will introduce an optimization based fast algorithm, which is able to solve a large-scale QSP problem parameterized by more than 10,000 phase factors. I will then discuss recent progress in understanding the energy landscape of the optimization problem, which allows us to solve the open problem of finding phase factors using only standard double precision arithmetic operations. I will also discuss another interesting progress in understanding the structure of phase factors which shows a duality between the smoothness of the target function and the decaying rate of the phase factors.

Back to Long Programs