量子可逆電路的研究現(xiàn)狀

張黎明 郭玲

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

關鍵詞： 量子門量子可逆電路量子多值邏輯通用門庫

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

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

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

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

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

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

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

參考文獻：

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

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

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

［4］吳楠，宋方敏.量子計算與量子計算機［J］.計算機科學與探索，2007，vol.1-1：1-16.