基于閑置比特使用的量子傅里葉線路優化

摘 要：通過使用閑置比特取代引入輔助比特，在閑置比特真正工作之前，它們代替輔助比特工作，可以大大提高量子比特的使用效率，減少操作時間。該方法可以進一步推廣到其他量子線路。

關鍵詞：量子線路；傅里葉變換；閑置比特

中圖分類號：O413;TP13文獻標志碼：A

文章編號：1001-3695(2007)06-0251-02

0 引言

自從Shor［1］在1994年發現了大數分解的有效算法之后，量子計算領域出現了一系列的研究成果［2，3］。因為使用量子疊加態，量子算法可以大大縮短某些問題的計算時間，可能據此解決經典計算無法解決的問題。然而，任何量子算法都涉及到一批聯合量子比特從初試態開始演化的一系列矩陣，因此需要尋找能夠有效實現任何給定量子算法的方案。與經典計算線路類似，量子算法也通常使用量子線路來實現［4］。

為了滿足在設計其物理實現對量子信息相干性的嚴格要求，人們在各個方面均作出了很多努力［5－7] 。 

理論上量子計算機的工作效率可以遠遠超過經典計算機，能夠完成經典計算機不能完成的工作。在量子計算機的整個體系結構中，量子邏輯計算線路是其中的研究重點之一。微觀世界形態是用量子力學所描述的，其動力學過程遵循薛定鄂方程，但是其哈密爾頓量容易受到環境的影響，從而使得量子計算的信息單元即量子比特所攜帶的相干信息遭到破壞。在物理學上這個過程稱為“退相干”。由于這個問題的存在，就促使了要在 “退相干”的時間內，完成量子計算［8，9］。

與經典傅里葉變換相對應，存在著量子傅里葉變換。它在量子計算中占據很重要的位置，如在Shor大數分解算法和Grover搜索算法中就必須利用量子傅里葉變換。

本文通過使用閑置比特的方法來節省操作時間。在閑置比特真正工作之前，它們代替輔助比特工作。充分利用態為｜0〉的閑置比特，可以大大提高量子比特的使用效率，節省操作時間，同時避免引入輔助比特而使系統信息更容

易受到環境的干擾。

1 若干概念

一個量子比特（即量子位）就是一個二維Hibert空間。在量子計算中通常可以引進基矢:

定義1（工作比特） 酉操作所涉及到的量子比特稱之為工作比特。

定義2（閑置比特） 酉操作一直都沒有涉及到的比特稱為閑置比特。這里強調 “一直”在某一酉操作的時候，沒有涉及到的比特可能在此之前的酉操作已經涉及到了，所以不能認為是閑置比特，閑置比特必須是未曾涉及過的；并且考慮到“量子克隆”的特殊性，這些閑置比特的狀態必須是｜0〉。

考慮如下所示的一個控制酉矩陣：

在控制酉矩陣的工作模式中，存在兩類不同的比特，即控制比特和目標比特。

定義3（控制比特） 當控制酉矩陣作用在兩個比特上時，其中一位始終保持不變，并且它的狀態決定了另外一位的狀態是否改變。那么這一位稱之為控制比特。

定義4（目標比特） 控制酉矩陣涉及到的除了控制比特之外的另一位。由控制比特的狀態來決定對其的作用，即如果控制比特的狀態是｜0〉，則保持不變，否則由酉矩陣對其加以作用。

2 建立在使用閑置比特基礎上的量子傅里葉線路

根據并行準則可以把標準的量子傅里葉線路變換為如圖1所示［8］。

圖1 經過并行操作后的量子傅立葉線路形式

Grover搜索算法的第一步，需要首先從｜0，0，…0〉經過量子傅立葉變換得到一個等重疊加態，文中則以此線路為例給予說明。

為了更好地利用并行性能，可以將其中一個輸入制作出若干個“copy”。而Controlled－not 門則可以通過一個非破壞性的測量將其中的一位“拷貝”到一個純態是｜0〉的輔助位：

注意到末態不是兩個分離的態的直積而是完全糾纏的。然而經典的”非克隆原理”則要求在計算的最后把輔助態分離出來而回歸到其初始態｜0〉，這也是這種量子線路當中十分重要的一個環節。

定理1針對一個固定的控制比特而不同的目標比特所進行的n個連續的控制酉矩陣操作可以并行到O（log n)時間序列完成［8］。

圖2中，雖然引進的輔助比特可以使線路的執行時間縮短，但是更多比特的量子系統受環境影響更大，系統的相干信息更易丟失。本文采用的方法則能有效解決這個問題，把閑置比特當作工作比特來使用，就可以對量子傅里葉線路進行系統優化。

可以觀察到2k比特的量子傅立葉線路，如果在只涉及到至多k個量子比特的酉操作時存在至少k個狀態｜0〉的比特是閑置比特，那么就可以把這k個比特視為輔助比特加以利用。

本文以2k比特的量子傅里葉變換為例進行并行操作。2k比特的該線路可以分為兩個部分：把存在至少k個閑置比特的前半部分量子線路稱為第一部分，把剩下的后半部分線路稱為第二部分。

第一部分中，可將閑置比特視為輔助比特。例如，在第一部分如果第i個比特作為控制比特，那么就有i-1個控制酉矩陣作用在從第一個至第i-1個目標比特上。 

首先利用控制非門把第i個比特的狀態“拷貝”到剩下的i-1閑置比特，這個操作共需要「log(i)個時序。

然后可以同時進行這個i-1控制酉門操作。

對于量子傅里葉變換線路優化前后總的步長數目作的比較如圖4所示。

3 結束語

量子傅里葉變換在量子Shor算法中有很重要的作用，如何實現是個必須探索的問題。

本文提出了一個減少操作時序的有效的方法：充分利用態為｜0〉的閑置比特。由于量子信息處理系統和環境之間存在糾纏，越多的比特會使環境對系統的影響更加明顯。這種利用閑置比特取代引入新的輔助比特的方法可盡量減弱環境的干擾。

類似地，這種方法還可以推廣到其他的線路。事實上，除了對量子傅立葉線路的前部分進行優化之外，對后半部分也可以利用閑置比特盡可能地得到較好的結果。然而，網絡的第二部分可以利用的閑置比特個數越來越少，因此必然有一個在此范圍內利用效率最高的閑置比特個數下界。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。