若干新的量子算法及相關問題

《若干新的量子算法及相關問題》是依託中山大學，由邱道文擔任項目負責人的面上項目。

基本介紹

• 中文名：若干新的量子算法及相關問題
• 項目類別：面上項目
• 項目負責人：邱道文
• 依託單位：中山大學

中文摘要

計算中一些基本而重要的問題用傳統的算法求解時要求較高的時間和空間複雜度。目前已經有學者發現了比經典計算有指數級加速的量子算法來解決科學計算的一些基本問題（如求解線性方程組）。半代數集問題是科學計算中基本而重要的問題之一；解線性和非線性方程組是半代數集的一類特殊情形。但是目前所知道的經典算法對求解半代數集問題的時間和空間複雜度比較高。因此，本項目試圖設計量子算法來求解半代數集問題，包括設計量子算法判斷一個半代數集是否為空；若一個半代數集非空，設計量子算法從中找到一個元素。進一步，我們也在量子計算的意義下考慮厄米特半正定矩陣的對角化問題。另一方面，由於目前所知道的計算布爾函式的超線性優勢的精確量子算法比較少，所以本項目尋找新的計算一些布爾函式的超線性優勢的精確量子算法 (精確是指輸出結果沒有誤差)。設計這些算法需要新的思路，所以這些算法對解決計算中的相關問題可能具有較好的借鑑作用。

結題摘要

計算中一些基本而重要的問題用傳統的算法求解時要求較高的時間和空間複雜度。目前已經有學者發現了比經典計算有指數級加速的量子算法來解決科學計算的一些基本問題。發現比經典算法更快的量子算法解決問題是的量子計算的核心。例如半代數集問題是科學計算中基本問題之一；解線性和非線性方程組是半代數集的一類特殊情形。但是目前所知道的經典算法對求解半代數集問題的時間和空間複雜度比較高。因此，本項目試圖設計量子算法來求解一些基本問題（包括半代數集問題），設計量子算法判斷一個半代數集是否為空；若一個半代數集非空，設計量子算法從中找到一個元素。進一步，我們也在量子計算的意義下考慮厄米特半正定矩陣的對角化問題。同時，由於目前所知道的計算布爾函式的超線性優勢的精確量子算法比較少，所以本項目尋找新的計算一些布爾函式的超線性優勢的精確量子算法(精確是指輸出結果沒有誤差)。設計這些算法需要新的思路，所以這些算法對解決計算中的相關問題可能具有較好的借鑑作用。