Quantum and classical query complexities of functions of matrices

报告题目：Quantum and classical query complexities of functions of matrices

报告地点：雷军科技楼A806报告厅

报告时间：7月30日 10:30-11:30

报告人：邵长鹏（中国科学院数学与系统科学研究院）

摘要：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.