UC Berkeley

Recent years have witnessed significant advancements in quantum algorithms for scientific computing. Central to these quantum algorithms is Quantum Signal Processing (QSP), which provides a unified framework for designing and understanding quantum algorithms through the exact implementation of matrix polynomials on quantum computers. Asymptotic analyses of QSP-based quantum algorithms indicate their potential to achieve optimal results for various tasks, for example, Hamiltonian simulation. An additional advantage of QSP is its minimal requirement for ancilla qubits, making it more feasible for implementation on near-to-intermediate term quantum architectures. QSP was first introduced theoretically in a seminal paper of Low and Chuang in 2017, and the task of designing scalable algorithms for its explicit implementation was initially considered challenging. However, in recent years, significant strides have been made in solving and comprehending this issue, effectively paving the way for the practical application of QSP.

QSP can be conceptualized as a nonlinear polynomial approximation framework. It maps a set of parameters, known as phase factors, to a polynomial function that adheres to minimal requirements. The essence of solving QSP problems lies in the inversion process: given a target function, the goal is to identify an appropriate set of phase factors such that the QSP-parametrized function closely approximates the target. This dissertation focuses on both the numerical resolution and theoretical exploration of QSP problems, along with their wide-ranging applications, from near-term quantum technologies to fault-tolerant quantum computing regimes. Included within this scope are various fundamental applications in quantum numerical linear algebra and quantum benchmarking. Furthermore, while QSP offers a simple and elegant theoretical framework for designing and understanding quantum algorithms, it also exhibits rich structures. These structures can be leveraged to accelerate not only the practical deployment of quantum technologies but also to advance theoretical research in this field. This aspect also falls within the scope of this dissertation.

This dissertation is organized as follows: Chapter 1 introduces the developments associated with QSP problems, providing motivation and a brief overview of the results presented in this dissertation. Chapter 2 offers a review of the theory of QSP and its variants. Following this, Chapter 3 presents several topics that serve as streamlined subroutines for enhancing QSP applications. In Chapter 4, a comprehensive overview of efficient iterative algorithms recently developed for solving QSP phase factors is provided, along with their convergence analysis and numerical justifications. Chapter 5 delves into important structural features of QSP problems, highlighting their role in accelerating practical implementations of QSP. The final two chapters showcase applications of QSP through two examples: Chapter 6 introduces a state-of-the-art quantum algorithm for ground-state preparation and energy estimation, highly suitable for early fault-tolerant quantum devices. In Chapter 7, an innovative benchmarking method is presented, which utilizes a random input model and a simplified QSP-based circuit to gauge the performance of quantum computers in scientific computing tasks. Additionally, this chapter provides a thorough analysis of the statistical properties of the ensemble of random input models on quantum computers.