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

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

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

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

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

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

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

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