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