IQIM Postdoctoral and Graduate Student Seminar

Abstract: Numerous computational problems that can be solved by quantum computers can be framed as instances of matrix functions. This topic has gained significant attention following the introduction of a unified framework for quantum algorithms based on quantum singular value transformation. However, not all efficient quantum algorithms for matrix functions provide a super-polynomial speedup compared to classical counterparts. In this seminar, we will discuss this dividing line in terms of computational complexity. Specifically, we will characterize complexity using several hyperparameters, including the access model to the matrix, matrix normalization, sparsity, precision, and the type of function involved. In the second half of the seminar, we will present a concrete application of matrix functions in a quantum algorithm for estimating partition functions. This algorithm does not rely on expensive subroutines such as quantum phase estimation or amplitude amplification and demonstrates a quadratic advantage over previous general-purpose algorithms that utilize similar quantum resources.

Lunch will be provided following the talk.