報告人：邱道文

時間：2020年11月24日 15:00

地點：騰訊會議（會議號：447403914）

邱道文，中山大學(xué)數(shù)據(jù)科學(xué)與計算機學(xué)院的教授，博士生導(dǎo)師，量子計算與計算機理論研究所所長，主要從事量子與經(jīng)典計算相互融合方面的研究，成果涉及量子計算、量子信息、模糊與概率自動機、及模糊與概率離散事件系統(tǒng)等領(lǐng)域，解決了量子自動機中的等價性判定和狀態(tài)最小化問題，建立了模糊離散事件系統(tǒng)的監(jiān)督控制和診斷理論，提出了半量子安全直接通信理論和基于非經(jīng)典邏輯的自動機理論，在國際知名學(xué)術(shù)期刊發(fā)表了130余篇學(xué)術(shù)論文，SCI收錄110余篇，SCI他人引用2000次以上。擔(dān)任國際著名學(xué)術(shù)期刊Theoretical Computer Science和Quantum Reports的編委，并擔(dān)任國際學(xué)術(shù)期刊Artificial Intelligence Evolution副主編。

報告摘要：Deutsch-Jozsa算法開創(chuàng)了量子查詢算法的研究，它表明量子計算比經(jīng)典計算在一些問題的解決上存在著優(yōu)勢。此外，它還為Simon算法、Shor算法和Grover算法提供了靈感。眾所周知，Deutsch-Jozsa算法只需要一個查詢來計算Deutsch問題，但經(jīng)典確定性算法需要(n/2+1)查詢來計算它。一個自然的問題是，1次量子查詢算法到底能計算出哪些問題呢？本次報告，首先證明所有精確量子查詢復(fù)雜度為1的偏對稱布爾函數(shù)都可以被Deutsch-Jozsa算法精確計算，進而給出描述偏布爾函數(shù)的充分和必要條件，其中所有精確量子查詢復(fù)雜度為1的布爾函數(shù)都遵循這個條件。