張黎明 郭玲

摘要： 隨著量子技術(shù)的發(fā)展，量子可逆電路構(gòu)造方法的應(yīng)用越來(lái)越多。本文通過(guò)描述對(duì)其發(fā)展做了概括說(shuō)明，并提出了現(xiàn)狀研究的不足之處，以及未來(lái)研究的方向，為量子技術(shù)的發(fā)展提供了平臺(tái)。

關(guān)鍵詞： 量子門量子可逆電路量子多值邏輯通用門庫(kù)

近30年來(lái)，人們已提出了多種量子門，如Toffoli門［１］，F(xiàn)redkin門，Peres門等，并給出了量子門的代數(shù)特征。如何使用指定量子門庫(kù)中的量子門自動(dòng)生成量子代價(jià)較小的量子可逆邏輯電路，其本質(zhì)就是量子可逆邏輯電路綜合技巧問(wèn)題。Shende將可逆電路綜合轉(zhuǎn)化為置換問(wèn)題，并提出三量子可逆邏輯電路綜合最優(yōu)算法；Yang在此基礎(chǔ)上利用GAP軟件實(shí)現(xiàn)了三量子最小長(zhǎng)度和最小代價(jià)可逆邏輯電路綜合算法。然而目前大多數(shù)算法只是在綜合三量子電路時(shí)效果很好，隨著綜合量子比特?cái)?shù)的增加，綜合量子可逆邏輯電路的時(shí)空復(fù)雜度將進(jìn)一步增加。在綜合四量子電路時(shí)，Yang等人利用廣度優(yōu)先搜索和雙向綜合技術(shù)，使用CNP量子門庫(kù)可綜合最長(zhǎng)為12的四量子偶置換最優(yōu)電路，這已是較好結(jié)果；李等人使用CNP量子門庫(kù)，在廣度優(yōu)先搜索的基礎(chǔ)上，巧妙構(gòu)造哈希函數(shù)并利用線置換和向變換進(jìn)行無(wú)損壓縮可快速生成最大長(zhǎng)度為16的最優(yōu)四量子偶置換電路，這是目前已知的最好結(jié)果。目前人們還未設(shè)計(jì)出通用高效的多量子電路綜合算法，這是量子電路設(shè)計(jì)中急需解決的重要問(wèn)題之一，因?yàn)樗脑O(shè)計(jì)實(shí)現(xiàn)不僅可以降低制造量子電路的成本，而且能提高多量子可逆電路設(shè)計(jì)的效率。

目前比較有代表性的量子可逆電路構(gòu)造方法有以下幾種［２］。

窮舉法、RM方法、群論分解方法、探索法，通過(guò)比較知窮舉法綜合結(jié)果好，能達(dá)到最優(yōu)，但時(shí)間空間開銷大；真值表和RM方法構(gòu)造巧妙，綜合速度快，但結(jié)果不盡理想，需要輔以優(yōu)化；群論方法新穎高效，算法收斂迅速（有限步結(jié)束），但構(gòu)造復(fù)雜，較為繁瑣，需要的門庫(kù)規(guī)模大；其他方法也均是在綜合的效果和效率之間尋求一個(gè)平衡點(diǎn)，這個(gè)平衡點(diǎn)如何選取，則應(yīng)該以實(shí)踐中的具體需求情況為依據(jù)。

構(gòu)建量子可逆邏輯電路主要有構(gòu)造與優(yōu)化兩個(gè)過(guò)程，有些算法是先構(gòu)造再優(yōu)化，還有一些算法則是構(gòu)造與優(yōu)化同時(shí)進(jìn)行。通常所得到的量子電路并不是最優(yōu)電路，如何有效地優(yōu)化電路，成為量子電路領(lǐng)域的另一個(gè)研究重點(diǎn)。Iwama、Maslov、Maslov等都對(duì)電路優(yōu)化程度作出了杰出貢獻(xiàn)。

目前對(duì)量子二值邏輯可逆電路綜合算法的研究較多，但對(duì)于多值邏輯量子電路綜合技術(shù)的研究較少［３］。其中的原因主要有：第一，人們已習(xí)慣于經(jīng)典計(jì)算中的二值邏輯，利用多值邏輯進(jìn)行計(jì)算不符合人們常規(guī)的思維和計(jì)算方式；第二，對(duì)于多值邏輯的理解與應(yīng)用本身就是困難的，涉及多值邏輯理論及群、環(huán)、域等代數(shù)理論，量子可逆電路的設(shè)計(jì)又具有相當(dāng)難度，規(guī)模較大，復(fù)雜性較高，其中又要解決量子的自然屬性（如消相干現(xiàn)象等）對(duì)計(jì)算的負(fù)面影響。所以將多值邏輯應(yīng)用于量子電路，設(shè)計(jì)具有相當(dāng)復(fù)雜性的多值邏輯量子電路也是困難的。然而，量子具有多種可觀測(cè)的屬性，例如光子的偏振方向，電子的自旋方向，電子所處于的能級(jí)等，因而具有多個(gè)復(fù)雜的自由度，利用多能級(jí)描述量子位也更自然。由于量子實(shí)驗(yàn)物理的發(fā)展進(jìn)步及測(cè)量技術(shù)的不斷完善，對(duì)于量子在各個(gè)屬性上的測(cè)量的精準(zhǔn)度大大提高，使得量子高維基態(tài)（即多值邏輯量子態(tài)）的應(yīng)用成為可能。另一方面，量子多值邏輯的應(yīng)用能夠極大提高量子并行計(jì)算的能力（理論上比二值邏輯更強(qiáng)大），并可在存儲(chǔ)和處理量子信息時(shí)提供更大的靈活性，又可以無(wú)輔助位的方式用兩位量子門和一位量子門建立多量子電路，使得多量子電路的物理實(shí)現(xiàn)成為可能。對(duì)多值量子可逆邏輯電路綜合的研究正在興起。

量子可逆電路本質(zhì)上是置換電路［４］，在此基礎(chǔ)上可根據(jù)一些特定功能構(gòu)造量子專用電路，專用電路的設(shè)計(jì)實(shí)現(xiàn)及應(yīng)用可加速運(yùn)行算法，并對(duì)量子寄存器或量子芯片等的設(shè)計(jì)作出一些貢獻(xiàn)。目前已設(shè)計(jì)出量子全加器、量子全減器及受控集成量子加減電路，它們是構(gòu)建量子計(jì)算機(jī)的基本單元。在量子糾錯(cuò)編碼和容錯(cuò)計(jì)算中可根據(jù)糾錯(cuò)碼的生成矩陣和校驗(yàn)矩陣，分別生成編碼電路和解碼電路。2005年何等人通過(guò)分解蝴蝶矩陣和轉(zhuǎn)置矩陣獨(dú)立實(shí)現(xiàn)了基于Haar小波多尺度分析的完整量子電路。2006年Cheng等人用Bitonic方法快速構(gòu)造大規(guī)模的量子排序電路，給出的線路模型清晰地反映出算法消耗資源的情況。2007年Khan等人給出了利用三值邏輯Feynman和Toffoli門實(shí)現(xiàn)的三值邏輯全加器，基于此又實(shí)現(xiàn)了帶有部分前瞻的三值邏輯并行加法器，并展示了將此電路用作并行減法器的方法。2008年Khan提出綜合量子四值邏輯加法/減法器的遞歸電路。之后Khan又提出量子四值邏輯比較器，比較器是著名的Grover量子搜索算法的關(guān)鍵功能模塊—Oracle的組成部分，也是基于比較的各種算法及控制器的基本模塊。當(dāng)然，由于量子電路設(shè)計(jì)的復(fù)雜性，目前綜合出的專用電路還不多，并且給出的大多數(shù)的電路并非最簡(jiǎn)形式。

盡管對(duì)于量子可逆電路的研究已取得了一些成果，但目前對(duì)于構(gòu)建量子可逆電路的量子門及通用門庫(kù)的研究還不深入，對(duì)于量子可逆電路的生成方法和優(yōu)化方法的研究還處于起步階段。對(duì)其中的一些問(wèn)題，如多值邏輯的嵌入與應(yīng)用，電路優(yōu)化策略，綜合算法復(fù)雜性的深入分析與證明等，只是進(jìn)行了初步的探索。雖出現(xiàn)了一些解決方案，但并不十分成熟，還有一些領(lǐng)域未曾涉及，所以需要進(jìn)一步深入研究。

參考文獻(xiàn)：

［1］李志強(qiáng)，陳漢武，徐寶文等.基于Hash表的量子可逆邏輯電路綜合的快速算法［J］.計(jì)算機(jī)研究與發(fā)展，2008，vol.45-2：2162-2171.

［2］何雨果，孫吉貴.基于Haar小波的多尺度分析量子電路［J］.科學(xué)通報(bào)，2005，vol.50-20：2314-2316.

［3］蘇汝鏗.量子力學(xué)［M］.北京：高等教育出版社，2002.

［4］吳楠，宋方敏.量子計(jì)算與量子計(jì)算機(jī)［J］.計(jì)算機(jī)科學(xué)與探索，2007，vol.1-1：1-16.