量子信息学交叉学科系列讲座

报告题目： 从Deutsch-Jozsa算法出发

报告人：邱道文

时间：2020年11月24日下午3点钟

地点：腾讯会议（会议号：447403914）

主办单位：太阳成集团tyc4633 计算智能与量子信息学研究团队

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