【学术视频】2019年复旦大学量子信息与计算暑期学校 | 中科院计算技术研究所孙晓明研究员

更多精彩视频登陆网站

www.koushare.com

图 | 孙晓明

题   目：Quantum Query Complexity (Lecture 1-2)

Amplitude Amplification-2 (Lecture 3-4)

Quantum Exact Algorithms for Weight Decision Problems (Lecture 5-6)

报告人：孙晓明单   位：中国科学院计算技术研究所

时   间：2019-07-21

地   点：复旦大学

扫码观看精彩报告视频

报告提纲

The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-n input is k or it is l. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of k, l and sufficiently large n, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of with matching upper and lower bounds, and finally we generalize to other cases via a new quantum padding technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.

个人简介

孙晓明，2001年、2005年在清华大学计算机系分别获得学士、博士学位；2005年-2008年任清华大学高等研究院助理研究员；2008年12月-2011年9月任清华大学高等研究院副研究员；2011年9月至今任中国科学院计算技术研究所研究员。主要研究方向是社会网络与博弈论相关的算法研究、量子计算、通信复杂性、判定树复杂度、组合数学。2013年获中国密码学会优秀青年奖，2012年获首批国家自然科学基金优秀青年基金资助，入选中组部首批青年拔尖人才支持计划。之前还曾获清华大学“学术新人奖”、“青年教师教学优秀奖”、清华大学优秀博士论文一等奖、微软学者等荣誉。

会议简介

复旦量子信息与计算暑期学校于2019年7月8日至7月21日在上海复旦大学举办。今年涉及的研究方向包括：量子模拟、量子精密测量与量子计算。暑期学校的教师均为活跃在学术前沿并有丰富教学经验的国际知名学者共7人，包括Stephen Bartlett, Renbao Liu, Zhengfeng Ji, Dieter Suter, Xiao-Gang Wen, Li You, Anthony Zee，授课语言为英文。

主办方：复旦大学

—— ——往期精彩回顾—— ——

END

扫描二维码，关注微信公众号

戳这里，观看精彩视频哟！