報(bào)告人：邱道文

時(shí)間：2020年11月24日 15:00

地點(diǎn)：騰訊會(huì)議（會(huì)議號(hào)：447403914）

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

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