《基於絕熱演化的量子搜尋算法研究》是依託華中科技大學，由路松峰擔任項目負責人的面上項目。
基本介紹
- 中文名：基於絕熱演化的量子搜尋算法研究
- 項目類別：面上項目
- 項目負責人：路松峰
- 依託單位：華中科技大學
中文摘要,結題摘要,
中文摘要
量子計算是基於量子力學的計算方法，絕熱量子計算模型是解決NP完全問題的潛在計算模型，本項目基於絕熱演化思想來研究具有廣泛套用的計算機領域的基礎問題- - 量子搜尋算法。通過增加系統調整哈密頓量、修改插值方法及參數等來研究演化路徑與絕熱量子搜尋算法性能之間的關係；通過分析現有的全局、局部和部分絕熱量子搜尋算法的特點來尋找施加絕熱條件的規律。然後利用演化路徑選取方法與絕熱條件的施加機理來指導相關內容研究，通過在部分絕熱區間上進行局部絕熱演化來設計微局部絕熱量子搜尋算法，並尋找該問題的下界；同時通過研究絕熱量子計算模型與量子線路模型的相互轉換來深刻理解這兩個模型之間的關係；項目還將通過研究絕熱量子傅立葉變換來設計絕熱量子計數算法。量子搜尋算法具有廣泛的套用，其可加速從P類到NP完全問題的大部分算法，項目的研究對理解絕熱量子計算乃至量子計算的本質，促進量子計算和量子計算機的實用化具有重要意義。
結題摘要
絕熱量子計算是基於連續時間變化的量子計算模型，該計算模型與基於量子線路的離散計算模型不同。對於一個量子系統可以用薛丁格方程來進行描述，在薛丁格方程中，系統的Hamilton量是關鍵，如果知道了系統的初態和系統Hamilton量，則系統任意時刻的狀態都可以得到，如果系統的變化比較緩慢，則絕熱定理可以保證，在以後任意時刻系統的狀態將接近系統的臨時基態，這樣如果我們把一個問題按薛丁格方程進行編碼，我們在系統演化完成後測量系統的狀態即可得到問題的解。課題在此背景下特別對絕熱量子搜尋算法進行深入研究，主要研究了如下內容：（1）絕熱演化方式對絕熱量子算法性能的影響； （2）絕熱量子搜尋算法演化路徑選取方法的研究； （3）基於微局部絕熱演化的量子搜尋算法研究； （4）絕熱量子搜尋算法與量子線路模型的關係研究； （5）量子計算的套用研究。 詳細成果如下： 絕熱量子算法可以分為全局絕熱量子算法、局部絕熱量子算法和部分絕熱量子算法，如果系統的初態和終態正交，則三種算法都會引起計算失敗，可以通過增加一個驅動Hamilton量來修正失敗的演化算法。基於部分絕熱的局部演化搜尋算法具有相同的時間複雜度，進而證明局部絕熱演化算法是最優的。微局部絕熱搜尋算法的性能要嚴格小於局部絕熱量子搜尋算法和部分絕熱量子搜尋算法，但是在算法複雜度上是它們具有相同的數量級。 課題分析了增加驅動哈密頓量、線形插值路徑，一類特殊的非線性演化路徑對絕熱量子搜尋算法性能的影響。 絕熱量子算法具有與量子電路具有相同的性能，但在解決某些問題時更方便，特別是具有抗噪聲能力。課題研究了在如何在絕熱量子計算模型下模擬量子線路問題，同時可以構造多種最基本的量子線路門電路。 此外，還研究了量子計算來解決Deutsch–Jozsa問題，帶輔助記憶體的無序資料庫搜尋問題，具有不同機率分布的絕熱量子計算問題，採用絕熱量子算法來進行布爾運算問題，量子機器學習問題等。 課題共在多種國際期刊和會議上發表論文22篇，其中SCI收錄18篇。 課題的研究具有廣泛的套用，其可加速從P 類到NP 完全問題的大部分算法，項目的研究對理解絕熱量子計算乃至量子計算的本質，促進量子計算機的實用化具有重要意義。
