报告人：邱道文
时间：2020年11月24日 15:00
地点：腾讯会议（会议号：447403914）
邱道文，中山大学数据科学与计算机学院的教授，博士生导师，量子计算与计算机理论研究所所长，主要从事量子与经典计算相互融合方面的研究，成果涉及量子计算、量子信息、模糊与概率自动机、及模糊与概率离散事件系统等领域，解决了量子自动机中的等价性判定和状态最小化问题，建立了模糊离散事件系统的监督控制和诊断理论，提出了半量子安全直接通信理论和基于非经典逻辑的自动机理论，在国际知名学术期刊发表了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的布尔函数都遵循这个条件。
