量子計算電路模型的自動綜合算法研究

《量子計算電路模型的自動綜合算法研究》是依託揚州大學，由李志強擔任項目負責人的面上項目。

基本介紹

• 中文名：量子計算電路模型的自動綜合算法研究
• 項目類別：面上項目
• 項目負責人：李志強
• 依託單位：揚州大學

項目摘要

量子電路是描述複雜量子計算的通用語言,量子電路是可逆的,可逆電路還廣泛套用於低功耗CMOS電路、納米技術、光計算等領域,如何根據要求自動設計出最優的量子電路,這對描述、實現與最佳化量子算法尤為重要。本課題在長期深入調查研究的基礎上,從基於真值表、模板、Reed-Muller與群論的可逆邏輯電路綜合算法出發,結合量子電路的特點,提出全新的基於Hash表與基於撲拓變換的3量子與4量子電路的快速綜合算法;結合群論,研究量子電路的分解算法,旨在高效設計大規模最佳化的量子電路;提出基於新型量子邏輯門庫的最優NCV量子電路快速綜合算法,為基於量子非邏輯門的綜合算法提出一種通用高效的新方法;研究新型量子門的自動構造算法,以發現更多更優的新型量子門;研究量子計算中與量子通信、量子測量相關複雜量子電路的自動綜合算法。為客觀分析、比較與最佳化各綜合算法,構建綜合算法統一的運行、測試、分析與輔助設計的通用實驗平台。

結題摘要

本項目對量子邏輯電路的綜合算法及相關理論進行了深入研究,主要成果包括： (1) 提出以最小長度綜合四量子電路快速算法。構造置換的最短編碼,拓撲無損壓縮 量子最優電路占用的存儲空間近2*n!倍,對已生成的最優電路雙向級聯,可使用多種量子門,採用最小長度標準,以極高效率生成較長的四量子電路,如率先生成基於NCT量子門庫 (NOT,CNOT和Toffoli)的全部前8層電路,還可快速綜合任意長度不超過16的最優電路。 (2) 提出以最小代價綜合四量子電路的高效算法。構造置換的最短編碼,高效的拓撲壓縮和靈活的數據結構,節省記憶體使用。(1)使用GT量子門庫(NCT 和 Toffoli-4 門)以最小長度綜合全部前8層四量子電路,存儲於Hash表中府祖墊束。(2)對Hash表進行歸併與分拆,生成一個更長的Hash表,以提高算法性能。(3)使用GTP量子門庫 (GT門庫, Peres和Peres逆門),以最小量子代價重新綜合Hash表中全部量子電路。(4)通過各電路量子代價的比較,算法能快速收斂於任一最小代價的四量子可逆邏輯電路。綜合目前相關踏套促測試函式,與已知最優結果比較,運行時間與電路的量子代價平均分別減少了99.95% 和18.2%。 (3) 提出基於新型量子邏輯門籃甩庫的最優NCV(NOT、CNOT、CV和CV+門)三量子電路快速綜合算法。這為解決量子非邏輯門綜合問題提出通用高效的方法。目前僅少數算法能用NCV門庫綜合三量子邏輯電路,方法是將該問題化簡為四值邏輯綜合問題。首次提出用NCV門構造新型量子邏輯門庫,該庫與NCV門庫在綜合最優的三量子邏輯電路上完全等價,因此又將四值埋謎祝主邏輯綜合問題簡化為更易求解的二元格戀值邏輯綜合問題,再使用基於Hash表的綜合算法,生成全部最優三量子邏輯電路,以最小代價綜合電路的平均速度是目前最好結果的127倍。 (4) 以上方法中,用最小的代價構造新型量子邏輯門尤為重要。提出兩種通用方法,分別使用控制非門與控制平方根非門和邀犁連使用控制非門與控制K次方根非門,其中k=4,8,16…,快速直接構造新型最優的量子邏輯門。首次提出了平方根平方根非門的概念,並首次給出其矩陣表示。在4量子電路綜合實驗中,運用該方法構造全部新型量子門,並綜合目前所有相關的測試函式,有近埋故整一半的電路比運用GTP門庫綜合的結果更優。我們給出了兩種方法詳細的數學證明,為當前綜合算法提供了新的思路。