Speaker: Dr. Changpeng Shao, CAS

Time: 16:00 p.m., March 12, 2024, GMT+8

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

Source: Center on Frontiers of Computing Studies, PKU