量子電路快速綜合算法研究.pdf

1、量子電路是構(gòu)建量子計算機的基本單元，也是描述復(fù)雜量子計算的高級語言。量子電路是可逆的，可逆邏輯因其在量子技術(shù)中的重要應(yīng)用而引起人們的廣泛關(guān)注。目前，可逆電路還廣泛應(yīng)用在低功耗CMOS電路、納米技術(shù)、光計算、加密技術(shù)等領(lǐng)域。通過量子門的級聯(lián)與組合可構(gòu)成量子電路，為根據(jù)要求自動設(shè)計出最優(yōu)或較優(yōu)的量子電路，需研究量子門的級聯(lián)規(guī)則與量子電路的自動生成與優(yōu)化技術(shù)，即研究量子電路的綜合算法，這在相關(guān)研究領(lǐng)域中是至關(guān)重要的。
　　 為用量子計

2、算解決經(jīng)典計算問題，本文主要研究量子電路中的可逆邏輯電路，量子可逆邏輯電路按量子門類型可分兩種：一種是僅使用量子邏輯門構(gòu)成的量子電路；另一種是使用量子邏輯門與量子非邏輯門構(gòu)成的量子電路。
　　 在實現(xiàn)量子計算的眾多方案中，量子電路中的垃圾位數(shù)增多已成為技術(shù)實現(xiàn)的主要障礙，因此我們以使用理論上最少的垃圾位數(shù)和最小或較小的量子代價為規(guī)則，對兩種量子電路的快速綜合算法及相關(guān)理論進行了深入探討，主要研究成果包括：
　　 (1)提

3、出了一種基于RM(Reed-Muller)的新型量子可逆電路快速綜合算法，自動構(gòu)造正極性RM展開式，并給出了構(gòu)造算法的證明，在生成量子可逆邏輯電路的解空間樹上，采用總體層次遍歷，局部深度搜索，借鑒模板優(yōu)化技術(shù)，構(gòu)造限界函數(shù)快速剪去無解或非最優(yōu)解的分枝，優(yōu)先探測RM中的因子，以極高的效率生成最優(yōu)電路。以國際公認的3變量可逆函數(shù)測試標(biāo)準，該算法不僅能夠生成全部最優(yōu)電路，而且運行速度遠遠超過同類算法。
　　 (2)提出了兩種基于Has

4、h函數(shù)的量子電路快速綜合算法?？墒褂枚喾N量子門，采用任意量子代價標(biāo)準，以極高的效率生成最優(yōu)的量子可逆邏輯電路。為實現(xiàn)量子電路綜合的自動化，提出了利用量子線的置換自動構(gòu)造各種量子門庫的通用算法。以國際同行認可的3變量可逆函數(shù)測試標(biāo)準，該算法不僅能夠生成全部最優(yōu)電路，而且運行速度遠遠超過其他算法，我們巧妙構(gòu)造了兩種Hash函數(shù)，即最小完備的Hash函數(shù)與基于位運算的Hash函數(shù)，實驗結(jié)果表明，基于這兩種Hash函數(shù)的綜合算法按最小長度、最小

5、代價標(biāo)準綜合電路的平均速度分別是目前最好結(jié)果的49.15倍、365.13倍與69.8倍、472.5倍。
　　 (3)提出了一種新穎高效的四量子可逆邏輯電路快速綜合算法。算法巧妙構(gòu)造置換的最短編碼，通過對量子電路進行特定的拓撲變換，無損壓縮n量子最優(yōu)電路占用的存儲空間近2×n!倍，通過對已生成的最優(yōu)電路的雙向級聯(lián)，可使用多種量子門，采用最小長度標(biāo)準，以極高效率生成較長的4量子電路，如率先生成了基于量子控制非門、非門、Toffoli

6、門(Quantum Controlled-NOT gate，NOT gate, Toffoligate，CNT)量子門庫的全部前8層共3120218828個電路，還可快速綜合任意長度不超過16的最優(yōu)電路，并對4量子標(biāo)準測試電路進行快速且全面的優(yōu)化，而目前其他算法中最多只能綜合最優(yōu)電路至12層。
　　 (4)提出了基于新型量子邏輯門庫的最優(yōu)NCV三量子電路快速綜合算法。這為解決第二種量子電路綜合問題提出了通用高效的方法。目前許多量

7、子電路綜合算法由于指數(shù)級時間、空間復(fù)雜度，僅能綜合3量子邏輯電路，只有少數(shù)算法實現(xiàn)用量子非門、控制非門、控制V門與控制V+門(Quantum NOT gate，Controlled-NOT gate，Controlled-V gate，Controlled-V+ gate，NCV)綜合3量子邏輯電路，主要方法是將量子電路綜合問題簡化為四值邏輯綜合問題。我們提出了用NCV門構(gòu)造新型量子邏輯門庫，該庫與NCV門庫在綜合最優(yōu)的3量子邏輯電路上