【报告摘要】In this talk, I will introduce a recent work on query complexity of functions of matrices. The problem is as follows: Let A be a sparse Hermitian matrix, f(x) be a univariate function. We want to estimate the quantum/classical query complexity of approximating an entry of f(A). In [arXiv:1806.01838], a quantum algorithm is given and the complexity is dominated by the minimal degree of the polynomial that approximates f(x). Here I will show you that this is also a lower bound. So the quantum algorithm for this problem is indeed optimal. I will also talk about some lower bounds analysis of classical algorithms to show that the quantum-classical separation is exponential.

【报告人简介】2023年入职中国科学院数学与系统科学研究院，担任副研究员。这之前，在英国布里斯托大学读博士后，主要从事量子算法与复杂度方面的研究。2016年博士毕业于中国科学院大学。在权威期刊Communications in Mathematical Physics，SIAM Journal on Matrix Analysis and Applications上发表过论文，在量子计算权威会议 QIP, TQC 上各做过2次报告。