静5青年讲座 | Quantum and classical query complexity…

Quantum and classical query complexity of functions of matrices

报告人

Dr. Changpeng Shao

Chinese Academy of Sciences

时  间

2024年3月12日 星期二 4:00pm

地  点

静园五院204

Host

李彤阳 助理教授

 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次报告。

往 期 讲 座

• 静5前沿讲座回顾 | Dr. Alan Szepieniec介绍区块链中可扩展且隐私保护的存储技术

• 静5前沿讲座回顾 | 周俊杰教授谈多层网络上的协作博弈

• 静5青年讲座回顾 | 黄昕博士谈从家务分配到工作调度的规约

• 静5前沿讲座回顾 | 区文浩教授谈密码学前沿进展及在区块链中的应用

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”查看海报