《量子有窮自動機的時空複雜度優勢及相關問題》是依託中山大學，由鄭盛根擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：量子有窮自動機的時空複雜度優勢及相關問題
- 項目類別：青年科學基金項目
- 項目負責人：鄭盛根
- 依託單位：中山大學
中文摘要,結題摘要,
中文摘要
量子有窮自動機作為量子計算最簡單的模型，對它的研究有利於對量子計算本質的理解。 迄今量子有窮自動機在時間、狀態複雜度（空間複雜度）方面都有許多的工作，但是學者們都是單獨考慮其時間複雜度或者空間複雜度。本項目主要研究：（1）從一個新的角度即時空複雜度的角度去研究雙向量子有窮自動機。嘗試去證明在識別一些語言時，雙向量子有窮自動機相對於雙向經典有窮自動機有優勢。（2）早在2000年，Klauck(STOC’00)就證明了精確（沒有誤差）單向量子有窮自動機在識別語言時相對於單向經典有窮自動機沒有任何的優勢，而精確雙向量子有窮自動機跟雙向經典有窮自動機比是否有優勢，一直是這個領域公開的問題。本項目將從時空複雜度去證明其優勢，致力於解決這一公開問題。（3）時空複雜度往往跟通信複雜度有聯繫，而量子通信複雜跟量子查詢複雜度有關係，所以本項目也開展這兩方面相關的研究，為證明時空複雜度作準備。
結題摘要
量子有窮自動機作為量子計算最簡單的模型，對它的研究有利於對量子計算本質的理解。 迄今量子有窮自動機的時間、狀態複雜度（空間複雜度）都有許多的工作，但是學者們都是 單獨考慮其時間複雜度或者空間複雜度。本項目主要研究：主要研究量子有窮自動的時空複雜度優勢和與量子通信複雜跟量子查詢複雜度的關係。本項目的主要成果如下：（1）證明了雙向量子有窮自動機與雙向機率自動機相比在時空複雜度上是有優勢的。結果發表在國際權威SCI期刊Theoretical Computer Science，（2）推廣了知名的Deutsch-Jozsa約束性問題的結論，提出和研究漢明權重區別問題。在Deutsch-Jozsa約束性問題中，討論的是區分輸入的漢明權重是{0,n}還是{n/2}. 本項目將結論推廣到區分輸入的漢明權重是{0,1,...,k, n-k,…,n}還是{n/2}，並給出了最優的精確查詢量子算法。同時，本人還將該結果推廣到量子查詢複雜度和自動機狀態複雜度的對應問題上。部分的論文成果發表在Physical Review A上。（3）證明精確單向量子有窮自動機在解決約束性問題上有狀態複雜性的優勢，並在光學實驗室上驗證該結論, 論文成果發表在npj Quantum Information上。（4）刻畫了一次精確量子查詢算法能解決的所有對稱偏函式。相關結果我們也在17th Asian Quantum Information Science Conference的國際會議上做了口頭報告。本項目一共發表SCI論文12篇，參加會議14次。
