報(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)最小化問題,建立了模糊離散事件系統(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ì)算在一些問題的解決上存在著優(yōu)勢(shì)。此外,它還為Simon算法、Shor算法和Grover算法提供了靈感。眾所周知,Deutsch-Jozsa算法只需要一個(gè)查詢來計(jì)算Deutsch問題,但經(jīng)典確定性算法需要(n/2+1)查詢來計(jì)算它。一個(gè)自然的問題是,1次量子查詢算法到底能計(jì)算出哪些問題呢?本次報(bào)告,首先證明所有精確量子查詢復(fù)雜度為1的偏對(duì)稱布爾函數(shù)都可以被Deutsch-Jozsa算法精確計(jì)算,進(jìn)而給出描述偏布爾函數(shù)的充分和必要條件,其中所有精確量子查詢復(fù)雜度為1的布爾函數(shù)都遵循這個(gè)條件。