作用於 個基態的傅立葉(Fourier)變換,矩陣看似有指數級大小。它特殊的相位結構卻允許用二次數量級的基本旋轉構造電路。要理解這一點,必須追蹤哪個位承載輸入的哪個小數部分:除非重新解釋輸出,否則顛倒這些位會改變酉算子。
分解傅立葉和
定義 2.3.1
(n 個量子比特上的量子傅立葉變換)
設 、。量子傅立葉變換是 個量子比特上的酉算子 ,滿足
寫 、,所以 是最低有效位。對 ,定義二進制小數 。
矩陣有 個元素,但每個輸出位可以分別求和。
定理 2.3.2
(傅立葉變換的乘積形式)
在上述記號下,
各因子由最高有效輸出位排到最低有效輸出位。
證明
(逐個輸出位求和)
展開 ,其中 。則
對所有 求和就是對互相獨立的各位 求和,而分別依賴不同變量的函數之積的和,等於各自求和後再相乘。因此
權重為 的輸出位所對應因子的相位只依賴 模 的值。滿足 的項 貢獻整數,可以捨去。其餘各項給出 。 時是 , 時是 ,即上面顯示的次序。
上述張量順序中,最高有效輸出位在前。因此二進制小數的順序與輸入線路相反。
構造電路
定義 2.3.3
(相位門與受控相位門)
對整數 ,令 。受控 將 乘以 ,並保持這兩條線路的其他三個計算基態不變。
線路按輸入位的權重編號,依次執行:
- 對 ,在第 條線路施加 Hadamard 門。
- 緊接該門,對每個 ,施加以第 條線路為控制、第 條線路為目標的受控 。
- 所有這些塊完成後,用 個交換門反轉線路順序。
定理 2.3.4
(傅立葉變換的精確電路)
上述電路含 個 Hadamard 門、 個受控旋轉和 個交換門;在定義所採用的正指數約定下,它作為酉映射等於 。
證明
(對基態輸入逐條線路計算)
對一個基態輸入處理線路 時,較低編號的控制線路尚未改變。Hadamard 門使 項獲得相位 ;各旋轉貢獻 。於是該線路的因子為
交換前,這些因子按 遞減排列,與 的乘積順序相反。交換門把它們放回上述順序。由於電路和 在每個計算基向量上都相同,線性性保證它們在任何輸入態上相同,包括糾纏態或疊加態。證明使用上述正指數約定;逆變換將門的次序反轉並把每個門替換為其伴隨。
證明透視
電路證明的各個假設用在哪裏
這個論證有三個運作部分。第一,次序 使每條控制線路 在被使用時仍處於輸入態 ,所以旋轉角度只依賴輸入位,而不依賴已被變換的線路。第二,角度 的選取使控制位 恰好加上二進制小數的 一項。第三,交換門只修正乘積的排列次序,並不改變任何相位。
計算是對基態輸入進行的,證明的是兩個線性映射相等,而不是假定輸入已知為某個基態。一旦它們在一組基上的作用相同,線性性就決定了它們在任意疊加態上的作用。關於尚未改變的控制位的描述屬於基態計算;不應把它理解為對這些位作測量。
例題 2.3.5
(三個位的相位)
當 、 時,輸入為 。反轉之前,從最高到最低有效位的線路因子分別帶有相位 、 和 。反轉之後,
相對相位 是 的相反數;替換它會改變狀態,而不只是改變整體相位。若省略輸出交換門,上式的張量因子順序反轉,因而必須相應解釋位標號。
例題 2.3.6
(兩個位的追蹤)
取 、,即 。先處理線路 。它的 Hadamard 門給出 ,而以處於 的線路 為控制的受控 把 項乘以 。該線路的因子是 ,與相位 吻合。線路 其後只受一個 Hadamard 門作用,成為 。交換前的狀態是 ;交換後
直接計算, 對 的係數為 ,兩者一致。
例題 2.3.7
(最小情形 )
時沒有受控旋轉,因為對 不可能有 ;交換門數為 。電路只是一個 Hadamard 門。乘積形式給出 ,所以單個量子比特上的量子傅立葉變換就是 Hadamard 門。
概念視角結構
把循環移位變成相位的變換
設 ,。由定義得 ,其中 ,即 。傅立葉變換就是使循環移位對角化的基變換,這也是它對週期結構敏感的原因。
每個基態輸入的輸出都是乘積形式,容易令人以為所有輸出都是乘積態;輸入一旦是疊加態,這個推斷就不成立。
反例模式
乘積態之和不一定是乘積態
命題:既然對每個基態輸入 都是乘積態,那麼對每個輸入 , 也都是乘積態。當 時,基態輸入 確實產生上面的乘積態。但輸入 的輸出,在 順序下的係數為 ,這是因為 、。其 係數矩陣的行列式 非零,故輸出是糾纏態。線性性並不意味著乘積態的和仍是乘積態;該命題只對基態輸入成立。
常見錯誤
(忘記位反轉)
沒有最後的交換門,上述電路並不實現 。當 、 時,正確的輸出是 ,而不加交換門的電路輸出 。這是兩個不同的狀態,並非只差一個整體相位。不加交換門的電路是位反轉的傅立葉變換,只有在後續步驟重新標記線路時才可以接受。
門數與近似旋轉
共有 個 Hadamard 門、 個受控旋轉和 個交換門。把每個旋轉和交換門各算作一個理想門,得到 門;交換門也可分解為三個 CNOT 門。這是電路大小的計數,不意味著固定有限門集中的任意旋轉都可以零代價合成。
命題 2.3.8
(省略小旋轉)
設 為整數。省略所有滿足 的受控 ,保留其他門和最後的交換門,將所得酉算子記為 。對算子範數 ,
證明
(對省略的門裂項求和)
逐個把省略的門替換為恆等門。裂項求和與算子範數的酉不變性把總差值限制在各門差值之和以內。受控 的差值為 。每條目標線路對每個 至多省略一個旋轉,而無限尾和為 。對至多 條目標線路求和即得所述界。
對任何歸一化輸入,兩個輸出態向量之差的歐氏(Euclidean)範數也不超過同一數值。保留下來的受控旋轉至多 個。取 ,就使此界不超過 。該估計假設保留的門是理想門;用固定門集近似它們會增加額外誤差,必須另行計入。
測量不是經典傅立葉表
對計算基輸入 ,在計算基中測量 ,得到每個 的概率均為 ,因為各振幅的模均為 。任意輸入不一定具有這種均勻性: 將均勻疊加態 映為 ,測量結果必為零。相位資訊需要後續干涉才能發揮作用;一次測量不能揭示整個複數傅立葉振幅向量。這並不是說該變換無用,而是說明外圍算法必須如何利用它。
常見錯誤
(把輸出當成傅立葉係數表)
對未知態施加電路後,一次測量只返回一個以概率 抽得的下標 ,並不返回 個複數 。要得到這張表,需要大量重複製備,而且相位仍會丟失。因此二次數量級的門數並不給出快速的經典傅立葉變換。
練習與解答
快速檢查
(當 、 時,按輸出順序寫出 的兩個因子。)
解答 · 答案
此時 、。第一個因子的相位是 ,第二個是 ,所以 。
快速檢查
(當 時,精確電路使用多少個受控旋轉和交換門?)
解答 · 答案
受控旋轉有 個,交換門有 個。
快速檢查
(為甚麼在同一線路約定下,省略最後交換門的電路嚴格來說不是上述 ?)
解答 · 答案
輸出線路中的傅立葉因子順序相反;需要交換門或明確重新解釋位標號。
快速檢查
(當 、 時,給出上面的一般算子範數誤差界。)
解答 · 答案
。這個界是空泛的:任意兩個酉算子之差的算子範數至多為 ,小於 。更大的 可以改善上述估計。