報告人：邱道文

時間：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的布爾函數都遵循這個條件。