Deutsch–Jozsa 與 Grover 等算法常從預言機 出發。但布爾(Boolean)函數可能丟失資訊:AND 將四個輸入映射為一個輸出位。這樣的函數如何成為酉電路的一部分?方法是保留輸入,並把結果異或到單獨的目標位。接下來的反計算則不經測量地清除臨時結果。
設 是確定性布爾函數。我們使用計算基字串、異或 ,以及 、受控非門和 Toffoli 門。Toffoli 門將 映為 ,保持兩個控制位不變。這些門置換計算基態,因此都是酉的。
為甚麼預言機可逆
定義 9.3.1
(位預言機)
對布爾函數 ,位預言機是作用於 個輸入量子比特和一個目標量子比特的算子,在計算基態上定義為
無論 是否多對一,對每個基態應用 (1) 兩次都會回到原態:。它是置換,因此酉。它不是單獨將 映為 。若兩個不同輸入有相同輸出,即使把輸出填充回 個量子比特,後一個映射也會把正交輸入態變成同一個態,因而不可能酉。
命題 9.3.2
(位預言機是酉的並產生相位回踢)
對每個布爾函數 , 都是酉的,且 。令 ,則
證明
(置換,以及目標位翻轉的特徵向量)
映射 是自身的逆,因此是計算基態的置換, 是置換矩陣,從而酉。對 (2),展開 。若 ,這就是 ;若 ,它是 。
由線性性,這個相位作用於疊加態的每個分支。這是相位回踢,不是對所有 值的測量。
從布爾電路構造預言機
假設給定一個計算 的無環經典電路,按拓撲順序有 個 AND 或 NOT 門以及一個指定輸出線。輸入和先前門的輸出可反覆用作控制。為每個門預留一個初始為零的乾淨工作位。要把兩條不同的先前線路的 AND 寫入新工作位,使用 Toffoli 門。若兩個輸入來自同一線路,則用受控非門,因為 。要把 NOT 寫入新工作位,先以 為控制施加受控非門,再對工作位施加 。兩種情況下控制位不變,新位都保存所需門值。
定理 9.3.3
(由含乾淨工作空間的經典電路構造預言機)
設一個含 個 AND 或 NOT 門的無環經典電路計算 。則存在一個由 中至多 個門和 個工作位組成的電路,對每個 有
所以只要工作位初始為乾淨狀態,它就實現 ,並使工作位恢復乾淨。
證明
(計算、複製、反計算)
所有門計算後,可逆電路 的作用為
其中 保存全部門值;指定輸出是這些值之一或某條輸入線。同一電路對疊加態按線性性作用。電路 只作用於輸入和工作寄存器;單獨的目標位 在 和 期間不參與。現在從輸出線向 施加受控非門,再按相反門序運行 。對每個基態輸入 得到
不作用於目標位,因此複製出的結果保留下來。(4) 由線性性推廣到任意疊加,並在乾淨工作空間子空間上實現 (1)。反計算不是通過測量擦除,而是已知可逆計算的逆操作。
每個經典 AND 或 NOT 門至多使用兩個上述可逆門計算其值。因此 至多用 個門, 至多用 個門,再加一個輸出受控非門及 個乾淨工作位:總計至多 個所列門。
這是在將 Toffoli 視為一個門的門集下的上界;若使用不同的量子基本門集,還需考慮其分解。它也假設經典電路已經給出。 作為置換的存在本身並不使任意 的預言機廉價。
證明透視
計算、複製、反計算每一步用到甚麼
緊接 運行 ,會同時清除工作空間和已計算的答案,因為 。不顯然的一步是中間那個受控非門:它作用於目標位,而 和 都不碰目標位,所以它把 記錄在一個能熬過反計算的寄存器上。這裏用到兩個假設。第一,工作寄存器初始為 ,所以 恰好產生 , 又恰好把它撤銷。第二, 中每個門都不改變其控制位,所以複製發生時輸出線仍保存 。線性性再把基態上的計算推廣到疊加態。若工作寄存器不乾淨,(3) 就不成立,見下面的反例。
AND 例題
例題 9.3.4
(只用一個工作位的 AND)
對 ,一個工作位 即可。令 ,先對 用 Toffoli,再由 到 使用受控非門,最後再次對 用 Toffoli。變換為
當 時目標位翻轉,其餘三個基態輸入則不翻轉。若 ,誘導的相位映射為對角映射,僅 帶負號,而工作位返回 。輸入含有其他分支時,此符號是可觀測的相對相位;單獨作用於 時,它是全局相位。
例題 9.3.5
(用兩個工作位的 NAND)
取 ,共 個門。先用 Toffoli 對 把 寫入 。再把 NOT 寫入 :由 到 施加受控非門,然後對 施加 。接著由 到 施加受控非門複製結果,再按相反順序運行前面三個門。當 :,,所以 不變,而 。當 :,,所以 翻轉,而 。兩種情況下反計算都使 。電路共用 個門,不超過上界 。
例題 9.3.6
(邊界情形:AND 的兩個輸入是同一條線)
對 ,Toffoli 規則需要兩個不同的控制位,所以改用受控非門。先由 到工作位 施加受控非門,把 寫入 ;再由 到 施加受控非門複製;最後撤銷第一步。於是 ,即 ,工作位乾淨。
常見錯誤
反例模式
工作寄存器不乾淨會破壞預言機
看似合理的說法:不論工作位原來是甚麼,計算—複製—反計算電路都實現 。對 AND 電路,取 和輸入 (即 、)。第一個 Toffoli 使 ;由 到 的受控非門令 ;第二個 Toffoli 令 保持為 。輸出為 ,但 要求 。髒工作位雖返回一,其值卻錯誤地影響了目標位。保證 (4) 要求工作寄存器初始為 。
常見錯誤
(丟棄工作空間不等於反計算)
對 施加受控非門,得到 。對第二個量子比特取偏跡後,第一個為 ,而不是 。此時在 基上測量第一個量子比特,得到 的概率只有 ,而不是一。這個簡單複製類似於依賴輸入的垃圾 :丟棄糾纏的工作寄存器可能移除相干性,並改變後續干涉計算。
常見錯誤
(把線路多次用作控制並不克隆量子態)
同一線路多次用作控制,也不會克隆任意未知量子態。受控非門可以把計算基位複製到乾淨目標位,但作用於疊加態時可能使寄存器糾纏,正如上一個例子所示。
練習與解答
快速檢查
(即使 ,為甚麼 仍酉?)
看輸入寄存器發生了甚麼。
解答 · 答案
二元組 保留了 ,而異或是自身的逆;(1) 是基態置換。
快速檢查
(在 AND 例子中, 會怎樣變化?)
追蹤工作位和目標位經過三個門的變化。
解答 · 答案
目標位 翻轉為 ,得到 :第一個 Toffoli 令 ,受控非門令 ,第二個 Toffoli 令 。
快速檢查
(儘管 、受控非門和 Toffoli 都是自身的逆,為甚麼 仍須按相反門序運行?)
回想 。
解答 · 答案
門的乘積取逆時需要反轉因子順序;每個因子自身可逆,並不使它們彼此對易。
快速檢查
( 的門數界是否意味著每個布爾函數都有關於 的多項式規模預言機?)
想想 是甚麼。
解答 · 答案
不能。該界以已給出的規模為 的電路為條件; 本身可能關於 指數增長。