量子信息学交叉学科系列讲座
报告题目: 从Deutsch-Jozsa算法出发
报告人:邱道文
时间:2020年11月24日下午3点钟
地点:腾讯会议(会议号:447403914)
主办单位:beat365正版唯一官网 计算智能与量子信息学研究团队
邱道文,中山大学数据科学与beat365正版唯一官网的教授,博士生导师,量子计算与计算机理论研究所所长,主要从事量子与经典计算相互融合方面的研究,成果涉及量子计算、量子信息、模糊与概率自动机、及模糊与概率离散事件系统等领域,解决了量子自动机中的等价性判定和状态最小化问题,建立了模糊离散事件系统的监督控制和诊断理论,提出了半量子安全直接通信理论和基于非经典逻辑的自动机理论,在国际知名学术期刊发表了130余篇学术论文,SCI收录110余篇,SCI他人引用2000次以上。担任国际著名学术期刊Theoretical Computer Science和Quantum Reports的编委,并担任国际学术期刊Artificial Intelligence Evolution副主编。
报告摘要: Deutsch-Jozsa算法开创了量子查询算法的研究,它表明量子计算比经典计算在一些问题的解决上存在着优势。此外,它还为Simon算法、Shor算法和Grover算法提供了灵感。众所周知,Deutsch-Jozsa算法只需要一个查询来计算Deutsch问题,但经典确定性算法需要(n/2+1)查询来计算它。一个自然的问题是,1次量子查询算法到底能计算出哪些问题呢?本次报告,首先证明所有精确量子查询复杂度为1的偏对称布尔函数都可以被Deutsch-Jozsa算法精确计算,进而给出描述偏布尔函数的充分和必要条件,其中所有精确量子查询复杂度为1的布尔函数都遵循这个条件。