《量子計算複雜性與經典計算複雜性的關係》是依託清華大學，由孫曉明擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：量子計算複雜性與經典計算複雜性的關係
- 依託單位：清華大學
- 項目負責人：孫曉明
- 項目類別：青年科學基金項目
- 批准號：60603005
- 負責人職稱：研究員
- 申請代碼：F0201
- 研究期限：2007-01-01 至 2009-12-31
- 支持經費：25（萬元）
項目摘要
自1980年以來，量子信息學已經發展成為一個具有相當規模和科學基礎的交叉學科。特別是1994年Shor提出的大數分解的量子多項式時間算法，使得量子計算成為當今理論計算機科學中最熱門的方向之一。探索量子算法的優勢極限，是當今亟待解決的重大科學問題。我們計畫對量子複雜性和經典複雜性之間的關係進行研究。在量子查詢複雜性模型中，已經證明Grover搜尋算法(運行時間sqrt(n))是最優的，也就是說量子資料庫查找算法最多能夠比經典算法有平方量級的加速。學者普遍認為這一結論對於任何total function都成立。這一猜想需要我們能提出新的證明量子查詢複雜性下限的方法。我們計畫從一些具體的函式例子出發，例如我們計畫研究：在格線上的local search的量子算法下限。通信複雜性是另外一個重要的模型，我們也將研究這一模型下量子複雜性和經典複雜性的關係。
