Changpeng Shao (Chinese Academy of Sciences) — Query complexities of functions of matrices*

*Full title: Quantum and classical query complexities of functions of matrices

Abstract:
In this talk, I will introduce joint work with Ashley Montanaro on query complexity of functions of matrices [arXiv:2311.06999, STOC 2024]. The problem is as follows: Let A be a sparse Hermitian matrix with operator norm at most 1, let f(x) be a function from [-1,1] to [-1,1]. The goal is to approximate an entry of f(A). Here we focus on quantum and classical query complexities. Quantum singular value transformation (QSVT, STOC 2019) is a powerful technique for functions of matrices. It provides an efficient quantum algorithm for this problem, with complexity mainly dominated by the approximate degree of f(x). Here I will show that this is also a lower bound. So the quantum algorithm for this problem is indeed optimal. I will also discuss lower bounds analysis for classical algorithms. The result shows that the quantum-classical separation is exponential. As another hardness result, I will show that the decision version of the entry estimation problem is BQP-complete for any f(x), as long as its approximate degree is large enough.

Date of talk: 2025-03-07

Видео Changpeng Shao (Chinese Academy of Sciences) — Query complexities of functions of matrices* канала QuSoft