CFCS Youth Talks

Quantum and classical query complexity of functions of matrices

  • Dr. Changpeng Shao, CAS
  • Time: 2024-03-12 16:00
  • Host: Dr. Tongyang Li
  • Venue: Room 204, Courtyard No.5, Jingyuan


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).



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