Speaker: Changpeng Shao
Time: 2024.5.30 15:00-16:00
Venue: Lecture Hall, 1st Floor, Conference Center
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, STOC 2019], 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 lower bounds analysis of classical algorithms to show that the quantum-classical separation is exponential. This talk is based on joint work with Ashley Montanaro arXiv:2311.06999 (accepted by STOC 2024).
Biography: Shao Changpeng joined the Academy of Mathematics and Systems Sciences of the Chinese Academy of Sciences in 2023 as an associate researcher. Prior to this, he studied as a postdoctoral fellow at the University of Bristol, UK, mainly engaged in the research of quantum algorithms and complexity. He received his Ph.D. from the University of Chinese Academy of Sciences in 2016. Published papers in authoritative journals Communications in Mathematical Physics, SIAM Journal on Matrix Analysis and Applications, He has made 3 presentations at QIP and TQC, the authoritative conferences of quantum computing.