引言
普適門集 是一小組基本操作,能用來精確構造任何量子計算,或以任意所需精度近似它。本文自成一體地討論這個課題的一項基礎內容。
相關的單量子比特筆記證明了 H H H 和 T T T 門所生成的單量子比特操作集合是稠密的,並陳述了 Solovay–Kitaev 定理,但沒有證明該定理。那篇筆記留下另一個更基本的問題:單量子比特門加上一個糾纏門,能否精確地 產生雙量子比特上的每一個 操作?
本文回答雙量子比特的情況。我們會證明:
每個 4 × 4 4\times 4 4 × 4 酉矩陣 U U U 都等於單量子比特酉門(作用於任一量子比特的任意 U ( 2 ) U(2) U ( 2 ) 元素)與 CNOT 門的有限乘積。等式完全精確,包括全局相位,而且不使用輔助量子比特。此構造最多使用 18 18 18 個 CNOT 門及 39 39 39 個單量子比特門。
這些數目是此特定構造所保證的上界;我們不 聲稱它們是最優的。文獻中有更精簡的構造,但本文既不使用也不推導那些構造。
證明分為五步,每一步都是有獨立證明的陳述。
消元。 在左側乘上最多六個二能級 酉操作,可把任何 U ∈ U ( 4 ) U\in U(4) U ∈ U ( 4 ) 化為對角酉矩陣。這是 QR 分解的酉矩陣版本。
重新標記。 四個計算基底向量上的任何二能級酉操作,都是一個受控單量子比特門,可能還需用一個 CNOT 作共軛。
受控相位。 門 diag ( 1 , 1 , 1 , e i φ ) \operatorname{diag}(1,1,1,e^{i\varphi}) diag ( 1 , 1 , 1 , e i φ ) 可由兩個 CNOT 和三個相位門構成。
受控 U ( 2 ) U(2) U ( 2 ) 。 任何單一控制的 U ∈ U ( 2 ) U\in U(2) U ∈ U ( 2 ) 可由兩個 CNOT 和四個單量子比特門構成。這需要在控制量子比特上正確選擇一個相位門。
對角矩陣。 任何雙量子比特對角酉操作,包括其全局相位,都可由兩個 CNOT 和三個單量子比特門構成。
把這些結果組合起來後,我們會解釋:若把任意角度的單量子比特門換成有限集合 { H , T } \{H,T\} { H , T } ,結論會有甚麼改變。最後,我們會陳述原始文獻中的 n n n 量子比特推廣,但不加證明。
約定
本文每條公式都依賴以下約定。門合成中的大多數錯誤,都是因為在沒有說明的情況下轉換了其中某個約定。
基底與張量順序
我們有兩個量子比特,分別稱為量子比特 1 和量子比特 2 。計算基底態寫作
∣ a b ⟩ = ∣ a ⟩ ⊗ ∣ b ⟩ , a , b ∈ { 0 , 1 } , \lvert ab\rangle = \lvert a\rangle\otimes\lvert b\rangle,\qquad a,b\in\{0,1\}, ∣ ab ⟩ = ∣ a ⟩ ⊗ ∣ b ⟩ , a , b ∈ { 0 , 1 } ,
其中 a a a 是量子比特 1 的值(左邊的張量因子),b b b 是量子比特 2 的值。基底的次序為
e 0 = ∣ 00 ⟩ , e 1 = ∣ 01 ⟩ , e 2 = ∣ 10 ⟩ , e 3 = ∣ 11 ⟩ , e_0=\lvert 00\rangle,\quad e_1=\lvert 01\rangle,\quad e_2=\lvert 10\rangle,\quad e_3=\lvert 11\rangle, e 0 = ∣ 00 ⟩ , e 1 = ∣ 01 ⟩ , e 2 = ∣ 10 ⟩ , e 3 = ∣ 11 ⟩ ,
所以 ∣ a b ⟩ \lvert ab\rangle ∣ ab ⟩ 是編號 2 a + b 2a+b 2 a + b 的基底向量。下文所有 4 × 4 4\times 4 4 × 4 矩陣都按這個有序基底書寫。對單量子比特矩陣 A A A 和 B B B ,算子 A ⊗ B A\otimes B A ⊗ B 在量子比特 1 上作用 A A A ,在量子比特 2 上作用 B B B 。它的矩陣是 Kronecker 分塊矩陣 ( a i j B ) i , j \big(a_{ij}B\big)_{i,j} ( a ij B ) i , j 。
對作用於量子比特 1 或量子比特 2 的單量子比特門 W W W ,我們分別簡記為 W 1 = W ⊗ I W_1 = W\otimes I W 1 = W ⊗ I 和 W 2 = I ⊗ W W_2 = I\otimes W W 2 = I ⊗ W 。
電路順序與乘積順序
電路按時間順序施加門 g 1 , g 2 , … , g m g_1, g_2, \dots, g_m g 1 , g 2 , … , g m 。第一個門最先作用於狀態,因此電路實現的算子是
g m g m − 1 ⋯ g 2 g 1 . g_m\, g_{m-1}\cdots g_2\, g_1 . g m g m − 1 ⋯ g 2 g 1 .
所以算子乘積要由右向左 讀。當構造以乘積形式給出,而且可能引起混淆時,我們也會明確列出時間順序。
單量子比特門
單量子比特門集包含整個 U ( 2 ) U(2) U ( 2 ) ,各門可作用於任一量子比特。以下是一些有名稱的元素:
X = ( 0 1 1 0 ) , H = 1 2 ( 1 1 1 − 1 ) , P ( θ ) = ( 1 0 0 e i θ ) ( θ ∈ R ) , X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad
H=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad
P(\theta)=\begin{pmatrix}1&0\\0&e^{i\theta}\end{pmatrix}\ (\theta\in\mathbb R), X = ( 0 1 1 0 ) , H = 2 1 ( 1 1 1 − 1 ) , P ( θ ) = ( 1 0 0 e i θ ) ( θ ∈ R ) ,
Z = P ( π ) , S = P ( π / 2 ) , T = P ( π / 4 ) . Z=P(\pi),\qquad S=P(\pi/2),\qquad T=P(\pi/4). Z = P ( π ) , S = P ( π /2 ) , T = P ( π /4 ) .
純量門 e i χ I ∈ U ( 2 ) e^{i\chi}I\in U(2) e i χ I ∈ U ( 2 ) 是一個合法的單量子比特門。把它作用於任一量子比特,便會令整個雙量子比特算子乘上 e i χ e^{i\chi} e i χ 。正因如此,在這個門集中才可能做到包括全局相位的精確 合成。
CNOT 與受控門
給定單量子比特門 W W W 、控制量子比特 s s s 、目標量子比特 t ≠ s t\neq s t = s 及控制值 c ∈ { 0 , 1 } c\in\{0,1\} c ∈ { 0 , 1 } ,定義 Λ c s → t ( W ) \Lambda^{s\to t}_c(W) Λ c s → t ( W ) 為以下的門:
當量子比特 s s s 處於狀態 ∣ c ⟩ \lvert c\rangle ∣ c ⟩ 時,在量子比特 t t t 上作用 W W W ;
當量子比特 s s s 處於狀態 ∣ 1 − c ⟩ \lvert 1-c\rangle ∣ 1 − c ⟩ 時,不作任何操作。
正控制 指 c = 1 c=1 c = 1 ;負控制 指 c = 0 c=0 c = 0 。以量子比特 1 為控制時,
Λ 1 1 → 2 ( W ) = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ W = ( I 0 0 W ) , Λ 0 1 → 2 ( W ) = ( W 0 0 I ) . \Lambda^{1\to2}_1(W)=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes W=\begin{pmatrix}I&0\\0&W\end{pmatrix},
\qquad
\Lambda^{1\to2}_0(W)=\begin{pmatrix}W&0\\0&I\end{pmatrix}. Λ 1 1 → 2 ( W ) = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ W = ( I 0 0 W ) , Λ 0 1 → 2 ( W ) = ( W 0 0 I ) . 以量子比特 2 為控制時,
Λ 1 2 → 1 ( W ) = I ⊗ ∣ 0 ⟩ ⟨ 0 ∣ + W ⊗ ∣ 1 ⟩ ⟨ 1 ∣ . \Lambda^{2\to1}_1(W)=I\otimes\lvert0\rangle\langle0\rvert+W\otimes\lvert1\rangle\langle1\rvert . Λ 1 2 → 1 ( W ) = I ⊗ ∣ 0 ⟩ ⟨ 0 ∣ + W ⊗ ∣ 1 ⟩ ⟨ 1 ∣ . 最後這個門在基底向量對 ( e 1 , e 3 ) = ( ∣ 01 ⟩ , ∣ 11 ⟩ ) (e_1,e_3)=(\lvert01\rangle,\lvert11\rangle) ( e 1 , e 3 ) = (∣ 01 ⟩ , ∣ 11 ⟩) 上按 W W W 作用,並固定 e 0 e_0 e 0 和 e 2 e_2 e 2 。
在控制量子比特上於受控門前後各施加一個 X X X 門,便可把負控制化為正控制:
Λ 0 s → t ( W ) = X s Λ 1 s → t ( W ) X s . \Lambda^{s\to t}_0(W)=X_s\,\Lambda^{s\to t}_1(W)\,X_s . Λ 0 s → t ( W ) = X s Λ 1 s → t ( W ) X s .
原因是 X s X_s X s 交換控制量子比特的兩個值,所以夾在兩個 X s X_s X s 之間時,原先「控制值 = 0 =0 = 0 」的分支會變成「控制值 = 1 =1 = 1 」的分支。
兩個 CNOT 門分別是 C N O T 1 → 2 = Λ 1 1 → 2 ( X ) \mathrm{CNOT}_{1\to2}=\Lambda^{1\to2}_1(X) CNOT 1 → 2 = Λ 1 1 → 2 ( X ) 和 C N O T 2 → 1 = Λ 1 2 → 1 ( X ) \mathrm{CNOT}_{2\to1}=\Lambda^{2\to1}_1(X) CNOT 2 → 1 = Λ 1 2 → 1 ( X ) 。它們的矩陣為
C N O T 1 → 2 = ( 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ) , C N O T 2 → 1 = ( 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 ) . \mathrm{CNOT}_{1\to2}=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix},
\qquad
\mathrm{CNOT}_{2\to1}=\begin{pmatrix}1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0\end{pmatrix}. CNOT 1 → 2 = 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 , CNOT 2 → 1 = 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 .
把它們看成基底標記的置換:
C N O T 1 → 2 \mathrm{CNOT}_{1\to2} CNOT 1 → 2 交換 10 ↔ 11 10\leftrightarrow 11 10 ↔ 11 。
C N O T 2 → 1 \mathrm{CNOT}_{2\to1} CNOT 2 → 1 交換 01 ↔ 11 01\leftrightarrow 11 01 ↔ 11 。
負控制版本 X 1 C N O T 1 → 2 X 1 X_1\mathrm{CNOT}_{1\to2}X_1 X 1 CNOT 1 → 2 X 1 和 X 2 C N O T 2 → 1 X 2 X_2\mathrm{CNOT}_{2\to1}X_2 X 2 CNOT 2 → 1 X 2 分別交換 00 ↔ 01 00\leftrightarrow01 00 ↔ 01 和 00 ↔ 10 00\leftrightarrow10 00 ↔ 10 。
每個 CNOT,不論是正控制還是負控制,都是自身的逆。
我們允許兩個方向的 CNOT。後面的習題表明 C N O T 2 → 1 = ( H ⊗ H ) C N O T 1 → 2 ( H ⊗ H ) \mathrm{CNOT}_{2\to1}=(H\otimes H)\,\mathrm{CNOT}_{1\to2}\,(H\otimes H) CNOT 2 → 1 = ( H ⊗ H ) CNOT 1 → 2 ( H ⊗ H ) 。因此只使用一個方向亦足夠,代價是需要額外的 Hadamard 門;CNOT 數目則不變。
二能級酉操作
令 x ≠ y x\neq y x = y 為兩個基底標記,並視之為一個有序 對,另令
M = ( m 11 m 12 m 21 m 22 ) ∈ U ( 2 ) . M=\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}\in U(2). M = ( m 11 m 21 m 12 m 22 ) ∈ U ( 2 ) . 二能級酉操作 T x , y ( M ) T_{x,y}(M) T x , y ( M ) 是由下式定義的線性映射:
T x , y ( M ) ∣ x ⟩ = m 11 ∣ x ⟩ + m 21 ∣ y ⟩ , T x , y ( M ) ∣ y ⟩ = m 12 ∣ x ⟩ + m 22 ∣ y ⟩ , T_{x,y}(M)\lvert x\rangle=m_{11}\lvert x\rangle+m_{21}\lvert y\rangle,\qquad
T_{x,y}(M)\lvert y\rangle=m_{12}\lvert x\rangle+m_{22}\lvert y\rangle, T x , y ( M ) ∣ x ⟩ = m 11 ∣ x ⟩ + m 21 ∣ y ⟩ , T x , y ( M ) ∣ y ⟩ = m 12 ∣ x ⟩ + m 22 ∣ y ⟩ , 其餘基底向量均保持不變。換言之,T x , y ( M ) T_{x,y}(M) T x , y ( M ) 在 span ( ∣ x ⟩ , ∣ y ⟩ ) \operatorname{span}(\lvert x\rangle,\lvert y\rangle) span (∣ x ⟩ , ∣ y ⟩) 上按 M M M 作用,其中 ∣ x ⟩ \lvert x\rangle ∣ x ⟩ 擔當第一個座標的角色;在正交補空間上則按恆等算子作用。它是酉算子,因為它是兩個酉算子的直和。由定義直接可得:
T x , y ( M ) † = T x , y ( M † ) , T y , x ( M ) = T x , y ( X M X ) . T_{x,y}(M)^\dagger=T_{x,y}(M^\dagger),\qquad T_{y,x}(M)=T_{x,y}(XMX). T x , y ( M ) † = T x , y ( M † ) , T y , x ( M ) = T x , y ( X M X ) .
對第二個等式,把一對標記由 ( x , y ) (x,y) ( x , y ) 改按 ( y , x ) (y,x) ( y , x ) 排列,便會同時置換該 2 × 2 2\times 2 2 × 2 分塊的列與行;這個置換恰好相當於用 X X X 共軛。只要 M M M 在這個交換下並非不變,標記對的次序便有影響 。
「精確」的意思
若一個電路的門矩陣乘積作為 4 × 4 4\times4 4 × 4 矩陣恰好等於 U U U ,我們便說它精確實現 U U U 。若只要求兩者相差一個全局相位 e i χ e^{i\chi} e i χ ,則是嚴格較弱的要求。一旦考慮受控門,我們便會看到為甚麼較強的要求很重要。
消元至對角酉矩陣
基本的 2 × 2 2\times 2 2 × 2 消零操作
引理 9.2.4
(用 2 × 2 2\times2 2 × 2 酉矩陣消去一個元素)
令 ( a , b ) ∈ C 2 (a,b)\in\mathbb C^2 ( a , b ) ∈ C 2 。
若 b = 0 b=0 b = 0 ,則 M = I M=I M = I 滿足 M ( a , b ) T = ( a , 0 ) T M(a,b)^{\mathsf T}=(a,0)^{\mathsf T} M ( a , b ) T = ( a , 0 ) T 。
若 b ≠ 0 b\neq 0 b = 0 ,設 r = ∣ a ∣ 2 + ∣ b ∣ 2 > 0 r=\sqrt{|a|^2+|b|^2}>0 r = ∣ a ∣ 2 + ∣ b ∣ 2 > 0 ,並令
M = 1 r ( a ˉ b ˉ − b a ) . M=\frac1r\begin{pmatrix}\bar a&\bar b\\-b&a\end{pmatrix}. M = r 1 ( a ˉ − b b ˉ a ) . 則 M ∈ U ( 2 ) M\in U(2) M ∈ U ( 2 ) 、det M = 1 \det M=1 det M = 1 ,而且 M ( a , b ) T = ( r , 0 ) T M(a,b)^{\mathsf T}=(r,0)^{\mathsf T} M ( a , b ) T = ( r , 0 ) T 。
b = 0 b=0 b = 0 的情況是直接的。假設 b ≠ 0 b\neq0 b = 0 ,則
M M † = 1 r 2 ( a ˉ b ˉ − b a ) ( a − b ˉ b a ˉ ) = 1 r 2 ( ∣ a ∣ 2 + ∣ b ∣ 2 − a ˉ b ˉ + b ˉ a ˉ − a b + a b ∣ b ∣ 2 + ∣ a ∣ 2 ) = I . MM^\dagger=\frac1{r^2}\begin{pmatrix}\bar a&\bar b\\-b&a\end{pmatrix}\begin{pmatrix}a&-\bar b\\b&\bar a\end{pmatrix}
=\frac1{r^2}\begin{pmatrix}|a|^2+|b|^2&-\bar a\bar b+\bar b\bar a\\-ab+ab&|b|^2+|a|^2\end{pmatrix}=I . M M † = r 2 1 ( a ˉ − b b ˉ a ) ( a b − b ˉ a ˉ ) = r 2 1 ( ∣ a ∣ 2 + ∣ b ∣ 2 − ab + ab − a ˉ b ˉ + b ˉ a ˉ ∣ b ∣ 2 + ∣ a ∣ 2 ) = I . 接著,det M = ( ∣ a ∣ 2 + ∣ b ∣ 2 ) / r 2 = 1 \det M=(|a|^2+|b|^2)/r^2=1 det M = ( ∣ a ∣ 2 + ∣ b ∣ 2 ) / r 2 = 1 。最後,
M ( a b ) = 1 r ( ∣ a ∣ 2 + ∣ b ∣ 2 − a b + a b ) = ( r 0 ) . ■ M\begin{pmatrix}a\\b\end{pmatrix}=\frac1r\begin{pmatrix}|a|^2+|b|^2\\-ab+ab\end{pmatrix}=\begin{pmatrix}r\\0\end{pmatrix}. \qquad\blacksquare M ( a b ) = r 1 ( ∣ a ∣ 2 + ∣ b ∣ 2 − ab + ab ) = ( r 0 ) . ■
零主元。 當原本要用作主元的 a a a 是零時,此公式不需要特別處理。若 a = 0 a=0 a = 0 且 b ≠ 0 b\neq0 b = 0 ,則 r = ∣ b ∣ r=|b| r = ∣ b ∣ ,而且
M = ( 0 b ˉ / ∣ b ∣ − b / ∣ b ∣ 0 ) , M=\begin{pmatrix}0&\bar b/|b|\\-b/|b|&0\end{pmatrix}, M = ( 0 − b /∣ b ∣ b ˉ /∣ b ∣ 0 ) ,
這是一個把非零元素移到主元位置的「帶相位交換」。唯一需要分開處理的是 b = 0 b=0 b = 0 :此時該元素已是零,無須做任何操作。特別地,這裏不會出現除以零的情況,也不需要在二能級操作框架之外交換行。
消元定理
以 0 , 1 , 2 , 3 0,1,2,3 0 , 1 , 2 , 3 為 4 × 4 4\times4 4 × 4 矩陣的行和列編號。固定以下由六個有序對組成的消元次序:
( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 3 ) . (0,1),\ (0,2),\ (0,3),\ (1,2),\ (1,3),\ (2,3). ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 3 ) .
處理滿足 k < j k\lt j k < j 的一對 ( k , j ) (k,j) ( k , j ) 時,以第 k k k 行為主元行,消去第 j j j 行、第 k k k 列的元素。
令 U ∈ U ( 4 ) U\in U(4) U ∈ U ( 4 ) 。存在二能級酉操作 G 1 , … , G 6 G_1,\dots,G_6 G 1 , … , G 6 ,其中對消元次序中第 i i i 個有序對 ( k i , j i ) (k_i,j_i) ( k i , j i ) ,有 G i = T k i , j i ( M i ) G_i=T_{k_i,j_i}(M_i) G i = T k i , j i ( M i ) ;也存在對角酉矩陣 D = diag ( d 0 , d 1 , d 2 , d 3 ) D=\operatorname{diag}(d_0,d_1,d_2,d_3) D = diag ( d 0 , d 1 , d 2 , d 3 ) ,其中 ∣ d ℓ ∣ = 1 |d_\ell|=1 ∣ d ℓ ∣ = 1 ,使得
G 6 G 5 G 4 G 3 G 2 G 1 U = D . G_6G_5G_4G_3G_2G_1\,U=D . G 6 G 5 G 4 G 3 G 2 G 1 U = D . 某些 G i G_i G i 可以是恆等算子,這恰好對應目標元素已經為零的步驟。
設 U ( 0 ) = U U^{(0)}=U U ( 0 ) = U 及 U ( i ) = G i U ( i − 1 ) U^{(i)}=G_iU^{(i-1)} U ( i ) = G i U ( i − 1 ) 。在處理 ( k , j ) = ( k i , j i ) (k,j)=(k_i,j_i) ( k , j ) = ( k i , j i ) 的第 i i i 步,令 a = U k , k ( i − 1 ) a=U^{(i-1)}_{k,k} a = U k , k ( i − 1 ) 及 b = U j , k ( i − 1 ) b=U^{(i-1)}_{j,k} b = U j , k ( i − 1 ) 。按照消零引理對 ( a , b ) (a,b) ( a , b ) 選取 M i M_i M i ,並設 G i = T k , j ( M i ) G_i=T_{k,j}(M_i) G i = T k , j ( M i ) 。
左乘 T k , j ( M ) T_{k,j}(M) T k , j ( M ) 只會改變第 k k k 行和第 j j j 行:
新行 k = m 11 ( 行 k ) + m 12 ( 行 j ) , 新行 j = m 21 ( 行 k ) + m 22 ( 行 j ) . \text{新行 }k=m_{11}\,(\text{行 }k)+m_{12}\,(\text{行 }j),\qquad
\text{新行 }j=m_{21}\,(\text{行 }k)+m_{22}\,(\text{行 }j). 新行 k = m 11 ( 行 k ) + m 12 ( 行 j ) , 新行 j = m 21 ( 行 k ) + m 22 ( 行 j ) . 在第 k k k 列,元素對 ( a , b ) (a,b) ( a , b ) 變成 M i ( a , b ) T M_i(a,b)^{\mathsf T} M i ( a , b ) T ;根據消零引理,其第二個元素是 0 0 0 。因此第 i i i 步把位置 ( j , k ) (j,k) ( j , k ) 的元素化為零。
我們還要檢查先前產生的零會否保留。每個先前產生的零都位於某個位置 ( j ′ , k ′ ) (j',k') ( j ′ , k ′ ) ,而且符合以下其中一種情況:
k ′ < k k'\lt k k ′ < k 且 j ′ > k ′ j'\gt k' j ′ > k ′ ;或
k ′ = k k'=k k ′ = k 且 k < j ′ < j k\lt j'\lt j k < j ′ < j 。
在第一種情況,考慮第 k ′ < k k'\lt k k ′ < k 列。第 k k k 行及第 j j j 行的編號均大於 k ′ k' k ′ ,而第 k ′ k' k ′ 列先前已完全處理,所以該列在這兩行的元素均已是 0 0 0 。它們的任何線性組合仍是 0 0 0 。在第二種情況,第 j ′ j' j ′ 行既非第 k k k 行亦非第 j j j 行,故不受影響。
因此,完成六步後,W : = U ( 6 ) W:=U^{(6)} W := U ( 6 ) 的對角線下方所有元素均為零,即 W W W 是上三角矩陣。由於它是酉矩陣的乘積,W W W 也是酉矩陣。下面的上三角引理表明,上三角酉矩陣必為對角矩陣,且對角元素的模均為 1 1 1 。令 D = W D=W D = W 即可。■ \blacksquare ■
若 W ∈ U ( N ) W\in U(N) W ∈ U ( N ) 是上三角矩陣,則 W W W 是對角矩陣,且對每個 ℓ \ell ℓ 均有 ∣ w ℓ ℓ ∣ = 1 |w_{\ell\ell}|=1 ∣ w ℓℓ ∣ = 1 。
我們以 ℓ \ell ℓ 作歸納,證明 W W W 的第 ℓ \ell ℓ 列等於 w ℓ ℓ e ℓ w_{\ell\ell}e_\ell w ℓℓ e ℓ 、∣ w ℓ ℓ ∣ = 1 |w_{\ell\ell}|=1 ∣ w ℓℓ ∣ = 1 ,以及 W W W 的第 ℓ \ell ℓ 行等於 w ℓ ℓ e ℓ T w_{\ell\ell}e_\ell^{\mathsf T} w ℓℓ e ℓ T 。
假設對所有小於 ℓ \ell ℓ 的指標均已成立。由於 W W W 是上三角矩陣,第 ℓ \ell ℓ 列在對角線以下的元素均為零。它在對角線以上的元素也為零,因為每一行 ℓ ′ < ℓ \ell'\lt\ell ℓ ′ < ℓ 都是 w ℓ ′ ℓ ′ e ℓ ′ T w_{\ell'\ell'}e_{\ell'}^{\mathsf T} w ℓ ′ ℓ ′ e ℓ ′ T ,故 w ℓ ′ ℓ = 0 w_{\ell'\ell}=0 w ℓ ′ ℓ = 0 。因此第 ℓ \ell ℓ 列是 w ℓ ℓ e ℓ w_{\ell\ell}e_\ell w ℓℓ e ℓ 。酉矩陣各列的範數為 1 1 1 ,所以 ∣ w ℓ ℓ ∣ = 1 |w_{\ell\ell}|=1 ∣ w ℓℓ ∣ = 1 。
當 m > ℓ m\gt\ell m > ℓ 時,第 ℓ \ell ℓ 列與第 m m m 列正交,因而
0 = ⟨ w ℓ ℓ e ℓ , 列 m ⟩ = w ℓ ℓ ‾ w ℓ m . 0=\langle w_{\ell\ell}e_\ell,\ \text{列}_m\rangle=\overline{w_{\ell\ell}}\,w_{\ell m}. 0 = ⟨ w ℓℓ e ℓ , 列 m ⟩ = w ℓℓ w ℓ m . 由於 w ℓ ℓ ≠ 0 w_{\ell\ell}\neq0 w ℓℓ = 0 ,可得 w ℓ m = 0 w_{\ell m}=0 w ℓ m = 0 ,所以第 ℓ \ell ℓ 行是 w ℓ ℓ e ℓ T w_{\ell\ell}e_\ell^{\mathsf T} w ℓℓ e ℓ T 。基礎情況 ℓ = 0 \ell=0 ℓ = 0 使用相同論證,只是沒有先前的行。■ \blacksquare ■
D D D 的對角元素模均為 1 1 1 ,但不一定等於 1 1 1 。例如,若 U U U 原本已是對角矩陣,整個消元次序中的每一步都是恆等操作,因而 D = U D=U D = U 。所以我們保留一般的對角酉矩陣 D D D ,並在對角雙量子比特酉算子一節另行合成它。
重構:逆向次序
由 G 6 ⋯ G 1 U = D G_6\cdots G_1U=D G 6 ⋯ G 1 U = D 出發,先在左側乘 G 6 † G_6^\dagger G 6 † ,再乘 G 5 † G_5^\dagger G 5 † ,如此類推,可得
U = G 1 † G 2 † G 3 † G 4 † G 5 † G 6 † D . U=G_1^\dagger\,G_2^\dagger\,G_3^\dagger\,G_4^\dagger\,G_5^\dagger\,G_6^\dagger\,D . U = G 1 † G 2 † G 3 † G 4 † G 5 † G 6 † D .
每個 G i † = T k i , j i ( M i † ) G_i^\dagger=T_{k_i,j_i}(M_i^\dagger) G i † = T k i , j i ( M i † ) 仍是作用於同一標記對上的二能級酉操作。把乘積由右向左讀成電路,其時間順序是
D , G 6 † , G 5 † , G 4 † , G 3 † , G 2 † , G 1 † . D,\ G_6^\dagger,\ G_5^\dagger,\ G_4^\dagger,\ G_3^\dagger,\ G_2^\dagger,\ G_1^\dagger . D , G 6 † , G 5 † , G 4 † , G 3 † , G 2 † , G 1 † .
最後一個消元步驟最先被還原,而第一個消元步驟最後才被還原。
這個次序不可任意調換。作用於有重疊的標記對上的二能級酉操作,一般並不交換。例如,T 0 , 1 ( X ) T_{0,1}(X) T 0 , 1 ( X ) 和 T 1 , 2 ( X ) T_{1,2}(X) T 1 , 2 ( X ) 分別是基底向量的換位 ( 0 1 ) (0\,1) ( 0 1 ) 和 ( 1 2 ) (1\,2) ( 1 2 ) ;以兩種次序相乘會得到兩個不同的 3 3 3 -循環。因此,一般而言寫成 U = G 6 † ⋯ G 1 † D U=G_6^\dagger\cdots G_1^\dagger D U = G 6 † ⋯ G 1 † D 是錯的。
假設 U ∈ U ( 4 ) U\in U(4) U ∈ U ( 4 ) 的第一列為 1 2 ( 1 , 1 , 1 , 1 ) T \tfrac12(1,1,1,1)^{\mathsf T} 2 1 ( 1 , 1 , 1 , 1 ) T 。對第 0 列的三個消去步驟如下,並列出每個 M i M_i M i 及每一步後的列向量。
配對 ( 0 , 1 ) (0,1) ( 0 , 1 ) 。 這裏 a = b = 1 2 a=b=\tfrac12 a = b = 2 1 ,所以 r = 1 2 r=\tfrac1{\sqrt2} r = 2 1 ,而
M 1 = 1 2 ( 1 1 − 1 1 ) . M_1=\tfrac1{\sqrt2}\begin{pmatrix}1&1\\-1&1\end{pmatrix}. M 1 = 2 1 ( 1 − 1 1 1 ) . 列向量變成 ( 1 2 , 0 , 1 2 , 1 2 ) T (\tfrac1{\sqrt2},0,\tfrac12,\tfrac12)^{\mathsf T} ( 2 1 , 0 , 2 1 , 2 1 ) T 。
配對 ( 0 , 2 ) (0,2) ( 0 , 2 ) 。 這裏 a = 1 2 a=\tfrac1{\sqrt2} a = 2 1 ,b = 1 2 b=\tfrac12 b = 2 1 ,所以 r = 1 2 + 1 4 = 3 2 r=\sqrt{\tfrac12+\tfrac14}=\tfrac{\sqrt3}2 r = 2 1 + 4 1 = 2 3 ,而
M 2 = ( 2 / 3 1 / 3 − 1 / 3 2 / 3 ) . M_2=\begin{pmatrix}\sqrt{2/3}&1/\sqrt3\\-1/\sqrt3&\sqrt{2/3}\end{pmatrix}. M 2 = ( 2/3 − 1/ 3 1/ 3 2/3 ) . 列向量變成 ( 3 2 , 0 , 0 , 1 2 ) T (\tfrac{\sqrt3}2,0,0,\tfrac12)^{\mathsf T} ( 2 3 , 0 , 0 , 2 1 ) T 。
配對 ( 0 , 3 ) (0,3) ( 0 , 3 ) 。 這裏 a = 3 2 a=\tfrac{\sqrt3}2 a = 2 3 ,b = 1 2 b=\tfrac12 b = 2 1 ,所以 r = 1 r=1 r = 1 ,而
M 3 = ( 3 / 2 1 / 2 − 1 / 2 3 / 2 ) . M_3=\begin{pmatrix}\sqrt3/2&1/2\\-1/2&\sqrt3/2\end{pmatrix}. M 3 = ( 3 /2 − 1/2 1/2 3 /2 ) . 列向量變成 ( 1 , 0 , 0 , 0 ) T (1,0,0,0)^{\mathsf T} ( 1 , 0 , 0 , 0 ) T 。
每個 M i M_i M i 的行均為標準正交,確認它是酉矩陣。最後的主元必須等於 1 1 1 ,因為原來的列是單位向量,而每一步均保持其範數。
令 S W A P ∣ a b ⟩ = ∣ b a ⟩ \mathrm{SWAP}\lvert ab\rangle=\lvert ba\rangle SWAP ∣ ab ⟩ = ∣ ba ⟩ 。其矩陣的各列依次為 e 0 , e 2 , e 1 , e 3 e_0,e_2,e_1,e_3 e 0 , e 2 , e 1 , e 3 :
S W A P = ( 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 ) . \mathrm{SWAP}=\begin{pmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{pmatrix}. SWAP = 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 . 第 0 列。 此列是 e 0 e_0 e 0 ,故第 1 , 2 , 3 1,2,3 1 , 2 , 3 行的元素均已為零。步驟 ( 0 , 1 ) (0,1) ( 0 , 1 ) 、( 0 , 2 ) (0,2) ( 0 , 2 ) 和 ( 0 , 3 ) (0,3) ( 0 , 3 ) 均有 b = 0 b=0 b = 0 ,所以 G 1 = G 2 = G 3 = I G_1=G_2=G_3=I G 1 = G 2 = G 3 = I 。
第 1 列,標記對 ( 1 , 2 ) (1,2) ( 1 , 2 ) 。 這裏 a = S W A P 1 , 1 = 0 a=\mathrm{SWAP}_{1,1}=0 a = SWAP 1 , 1 = 0 、b = S W A P 2 , 1 = 1 b=\mathrm{SWAP}_{2,1}=1 b = SWAP 2 , 1 = 1 ,因此主元是零。消零引理給出 r = 1 r=1 r = 1 及
M 4 = ( 0 1 − 1 0 ) . M_4=\begin{pmatrix}0&1\\-1&0\end{pmatrix}. M 4 = ( 0 − 1 1 0 ) . 左乘 G 4 = T 1 , 2 ( M 4 ) G_4=T_{1,2}(M_4) G 4 = T 1 , 2 ( M 4 ) 會把第 1 1 1 行替換為第 2 2 2 行,即 ( 0 , 1 , 0 , 0 ) (0,1,0,0) ( 0 , 1 , 0 , 0 ) ;並把第 2 2 2 行替換為原第 1 1 1 行的負數,即 ( 0 , 0 , − 1 , 0 ) (0,0,-1,0) ( 0 , 0 , − 1 , 0 ) 。結果是
G 4 S W A P = diag ( 1 , 1 , − 1 , 1 ) . G_4\,\mathrm{SWAP}=\operatorname{diag}(1,1,-1,1). G 4 SWAP = diag ( 1 , 1 , − 1 , 1 ) . 餘下步驟。 標記對 ( 1 , 3 ) (1,3) ( 1 , 3 ) 和 ( 2 , 3 ) (2,3) ( 2 , 3 ) 此時都有 b = 0 b=0 b = 0 ,所以 G 5 = G 6 = I G_5=G_6=I G 5 = G 6 = I ,而 D = diag ( 1 , 1 , − 1 , 1 ) D=\operatorname{diag}(1,1,-1,1) D = diag ( 1 , 1 , − 1 , 1 ) 。
重構。 我們得到 S W A P = G 4 † D \mathrm{SWAP}=G_4^\dagger D SWAP = G 4 † D ,其中 G 4 † = T 1 , 2 ( ( 0 − 1 1 0 ) ) G_4^\dagger=T_{1,2}\!\left(\begin{pmatrix}0&-1\\1&0\end{pmatrix}\right) G 4 † = T 1 , 2 ( ( 0 1 − 1 0 ) ) 。驗算時先作用 D D D :
e 0 ↦ e 0 e_0\mapsto e_0 e 0 ↦ e 0 、e 1 ↦ e 1 e_1\mapsto e_1 e 1 ↦ e 1 、e 2 ↦ − e 2 e_2\mapsto -e_2 e 2 ↦ − e 2 、e 3 ↦ e 3 e_3\mapsto e_3 e 3 ↦ e 3 。
然後作用 G 4 † G_4^\dagger G 4 † :
e 1 ↦ e 2 e_1\mapsto e_2 e 1 ↦ e 2 (分塊的第一列);
− e 2 ↦ − ( − e 1 ) = e 1 -e_2\mapsto -(-e_1)=e_1 − e 2 ↦ − ( − e 1 ) = e 1 (分塊的第二列)。
合起來得到 e 0 ↦ e 0 e_0\mapsto e_0 e 0 ↦ e 0 、e 1 ↦ e 2 e_1\mapsto e_2 e 1 ↦ e 2 、e 2 ↦ e 1 e_2\mapsto e_1 e 2 ↦ e 1 、e 3 ↦ e 3 e_3\mapsto e_3 e 3 ↦ e 3 ,正是 SWAP。D D D 裏的負號不可或缺;若沒有它,重構後便會得到 e 2 ↦ − e 1 e_2\mapsto -e_1 e 2 ↦ − e 1 。
把二能級酉操作表示成受控門
相鄰標記對
把四個標記 00 , 01 , 10 , 11 00,01,10,11 00 , 01 , 10 , 11 視為一個正方形的頂點。當兩個標記恰好有一個比特不同,即它們的漢明(Hamming)距離 為 1 1 1 時,便以一條邊連接。這個正方形是以下 4 4 4 -循環
00 − 01 − 11 − 10 − 00. 00\ -\ 01\ -\ 11\ -\ 10\ -\ 00 . 00 − 01 − 11 − 10 − 00.
任意兩個不同的標籤不是相鄰(距離為 1 1 1 ),就是位於相對頂點(距離為 2 2 2 )。一對相對頂點之間恰有兩條沿正方形邊走的最短路徑,每條都經過一個中間頂點。
設 x x x 和 y y y 恰好在量子比特 t t t 上不同,而 s s s 是另一個量子比特,在兩個標籤中的共同值為 c c c 。
如果 x x x 的量子比特 t t t 為 0 0 0 (因而 y y y 的該比特為 1 1 1 ),則 T x , y ( M ) = Λ c s → t ( M ) T_{x,y}(M)=\Lambda^{s\to t}_c(M) T x , y ( M ) = Λ c s → t ( M ) 。
如果 x x x 的量子比特 t t t 為 1 1 1 ,則 T x , y ( M ) = Λ c s → t ( X M X ) T_{x,y}(M)=\Lambda^{s\to t}_c(XMX) T x , y ( M ) = Λ c s → t ( X M X ) 。
量子比特 s s s 等於 1 − c 1-c 1 − c 的基向量,在等式兩邊都保持不變。量子比特 s s s 等於 c c c 的基向量恰好是 ∣ x ⟩ \lvert x\rangle ∣ x ⟩ 和 ∣ y ⟩ \lvert y\rangle ∣ y ⟩ 。在這兩個向量上,Λ c s → t ( W ) \Lambda^{s\to t}_c(W) Λ c s → t ( W ) 依照有序基底 ( ∣ 0 ⟩ , ∣ 1 ⟩ ) (\lvert0\rangle,\lvert1\rangle) (∣ 0 ⟩ , ∣ 1 ⟩) 對量子比特 t t t 施加 W W W 。如果 x x x 的目標比特值為 0 0 0 ,這個有序基底便與有序對 ( x , y ) (x,y) ( x , y ) 一致,因此 W = M W=M W = M 。否則順序相反,故 T x , y ( M ) = T y , x ( X M X ) = Λ c s → t ( X M X ) T_{x,y}(M)=T_{y,x}(XMX)=\Lambda^{s\to t}_c(XMX) T x , y ( M ) = T y , x ( X M X ) = Λ c s → t ( X M X ) 。■ \blacksquare ■
相對頂點對:以置換重新標記
設 Q Q Q 是作用於基向量的置換矩陣,並記 Q ∣ x ⟩ = ∣ Q x ⟩ Q\lvert x\rangle=\lvert Qx\rangle Q ∣ x ⟩ = ∣ Q x ⟩ 。對每個 M ∈ U ( 2 ) M\in U(2) M ∈ U ( 2 ) ,
Q T x , y ( M ) Q − 1 = T Q x , Q y ( M ) . Q\,T_{x,y}(M)\,Q^{-1}=T_{Qx,\,Qy}(M). Q T x , y ( M ) Q − 1 = T Q x , Q y ( M ) .
我們把等式兩邊作用於每個基向量。
對 ∣ Q x ⟩ \lvert Qx\rangle ∣ Q x ⟩ :Q T x , y ( M ) Q − 1 ∣ Q x ⟩ = Q T x , y ( M ) ∣ x ⟩ = Q ( m 11 ∣ x ⟩ + m 21 ∣ y ⟩ ) = m 11 ∣ Q x ⟩ + m 21 ∣ Q y ⟩ Q\,T_{x,y}(M)\,Q^{-1}\lvert Qx\rangle=Q\,T_{x,y}(M)\lvert x\rangle=Q\big(m_{11}\lvert x\rangle+m_{21}\lvert y\rangle\big)=m_{11}\lvert Qx\rangle+m_{21}\lvert Qy\rangle Q T x , y ( M ) Q − 1 ∣ Q x ⟩ = Q T x , y ( M ) ∣ x ⟩ = Q ( m 11 ∣ x ⟩ + m 21 ∣ y ⟩ ) = m 11 ∣ Q x ⟩ + m 21 ∣ Q y ⟩ ,與右邊一致。
對 ∣ Q y ⟩ \lvert Qy\rangle ∣ Q y ⟩ :計算方法相同。
對任何其他 ∣ w ⟩ \lvert w\rangle ∣ w ⟩ :標籤 Q − 1 w Q^{-1}w Q − 1 w 不屬於 { x , y } \{x,y\} { x , y } ,因為 Q − 1 Q^{-1} Q − 1 把 { Q x , Q y } \{Qx,Qy\} { Q x , Q y } 雙射至 { x , y } \{x,y\} { x , y } ,因而把補集映入補集。所以 T x , y ( M ) T_{x,y}(M) T x , y ( M ) 固定 ∣ Q − 1 w ⟩ \lvert Q^{-1}w\rangle ∣ Q − 1 w ⟩ ,左邊便得到 ∣ w ⟩ \lvert w\rangle ∣ w ⟩ 。■ \blacksquare ■
移動哪個端點,以及移動方向。 要為一對相對頂點實現 T x , y ( M ) T_{x,y}(M) T x , y ( M ) ,選擇一個要移動的端點,例如 y y y ,以及一個同時與 x x x 和 y y y 相鄰的中間標籤 z z z 。然後找出置換 Q Q Q ,使得
Q x = x 且 Q z = y . Qx=x\qquad\text{且}\qquad Qz=y . Q x = x 且 Q z = y .
這裏 Q Q Q 把輔助 標籤 z z z 送到原本的 端點 y y y 。由共軛引理,
T x , y ( M ) = Q T x , z ( M ) Q − 1 . T_{x,y}(M)=Q\,T_{x,z}(M)\,Q^{-1}. T x , y ( M ) = Q T x , z ( M ) Q − 1 .
按時間順序,先施加 Q − 1 Q^{-1} Q − 1 ,再施加相鄰門 T x , z ( M ) T_{x,z}(M) T x , z ( M ) ,最後施加 Q Q Q 。
反方向的共軛 Q − 1 T x , z ( M ) Q Q^{-1}T_{x,z}(M)\,Q Q − 1 T x , z ( M ) Q 等於 T Q − 1 x , Q − 1 z ( M ) T_{Q^{-1}x,\,Q^{-1}z}(M) T Q − 1 x , Q − 1 z ( M ) 。只有當 Q − 1 z = y Q^{-1}z=y Q − 1 z = y 時,它才是所需的門。當 Q Q Q 是單個 CNOT 時,Q = Q − 1 Q=Q^{-1} Q = Q − 1 ,兩種約定一致;對複合置換,兩者確實可以不同。稍後關於共軛方向一節的反例會具體說明。
移動端點也會改變有序對中的標籤次序,因而影響相鄰對引理中應使用 M M M 還是 X M X XMX X M X 。在上述的 ( x , z ) (x,z) ( x , z ) 中,x x x 仍排在第一,所以區塊仍是 M M M 。然後須對 ( x , z ) (x,z) ( x , z ) 應用相鄰對引理,留意 x x x 和 z z z 哪一個的目標比特是 0 0 0 。
用電路實現消元次序
對消元次序中的六對,將標籤寫成比特:0 = 00 0=00 0 = 00 、1 = 01 1=01 1 = 01 、2 = 10 2=10 2 = 10 、3 = 11 3=11 3 = 11 。對相鄰對直接應用相鄰對引理,對兩對相對頂點則應用共軛引理,使用單個正控制 CNOT。
CNOT 數目一列已包括實現每個受控 U ( 2 ) U(2) U ( 2 ) 門所需的兩個 CNOT;這點會在精確構造單控制 U ( 2 ) U(2) U ( 2 ) 門一節證明。
兩個相對頂點的情況如下。
數字對 ( 0 , 3 ) (0,3) ( 0 , 3 ) 。 用 Q = C N O T 2 → 1 Q=\mathrm{CNOT}_{2\to1} Q = CNOT 2 → 1 把 y = 11 y=11 y = 11 移到 z = 01 z=01 z = 01 。這個 Q Q Q 固定 00 00 00 ,並把 01 ↦ 11 01\mapsto11 01 ↦ 11 。相鄰門是 T 00 , 01 ( M ) T_{00,01}(M) T 00 , 01 ( M ) ;由於 00 00 00 的量子比特 2 2 2 為 0 0 0 ,相鄰對引理給出它等於 Λ 0 1 → 2 ( M ) \Lambda^{1\to2}_0(M) Λ 0 1 → 2 ( M ) 。
數字對 ( 1 , 2 ) (1,2) ( 1 , 2 ) 。 用 Q = C N O T 1 → 2 Q=\mathrm{CNOT}_{1\to2} Q = CNOT 1 → 2 把 y = 10 y=10 y = 10 移到 z = 11 z=11 z = 11 。這個 Q Q Q 固定 01 01 01 ,並把 11 ↦ 10 11\mapsto10 11 ↦ 10 。相鄰門是 T 01 , 11 ( M ) T_{01,11}(M) T 01 , 11 ( M ) ;由於 01 01 01 的量子比特 1 1 1 為 0 0 0 ,它等於 Λ 1 2 → 1 ( M ) \Lambda^{2\to1}_1(M) Λ 1 2 → 1 ( M ) 。
每一行的第一個標籤,其目標比特都是 0 0 0 ,所以區塊就是 M M M ,而不是 X M X XMX X M X 。這是這個特定次序和這些特定選擇的性質,並非一般事實;後面關於相對頂點對的習題會說明這點。
對逆因子 G i † G_i^\dagger G i † ,只需在相同電路中把 M M M 換成 M † M^\dagger M † 。
例題 9.2.11
(在 |00⟩ 和 |11⟩ 上的二能級旋轉)
設
R = 1 2 ( 1 − 1 1 1 ) . R=\frac1{\sqrt2}\begin{pmatrix}1&-1\\1&1\end{pmatrix}. R = 2 1 ( 1 1 − 1 1 ) . 這個區塊特意選成對交換不對稱:X R X = 1 2 ( 1 1 − 1 1 ) ≠ R XRX=\tfrac1{\sqrt2}\begin{pmatrix}1&1\\-1&1\end{pmatrix}\neq R X R X = 2 1 ( 1 − 1 1 1 ) = R 。我們要實現 T 00 , 11 ( R ) T_{00,11}(R) T 00 , 11 ( R ) ,其定義作用為
∣ 00 ⟩ ↦ 1 2 ( ∣ 00 ⟩ + ∣ 11 ⟩ ) , ∣ 11 ⟩ ↦ 1 2 ( − ∣ 00 ⟩ + ∣ 11 ⟩ ) , \lvert00\rangle\mapsto\tfrac1{\sqrt2}\big(\lvert00\rangle+\lvert11\rangle\big),\qquad
\lvert11\rangle\mapsto\tfrac1{\sqrt2}\big(-\lvert00\rangle+\lvert11\rangle\big), ∣ 00 ⟩ ↦ 2 1 ( ∣ 00 ⟩ + ∣ 11 ⟩ ) , ∣ 11 ⟩ ↦ 2 1 ( − ∣ 00 ⟩ + ∣ 11 ⟩ ) , 並固定 ∣ 01 ⟩ \lvert01\rangle ∣ 01 ⟩ 和 ∣ 10 ⟩ \lvert10\rangle ∣ 10 ⟩ 。它的矩陣是
T 00 , 11 ( R ) = ( 1 2 0 0 − 1 2 0 1 0 0 0 0 1 0 1 2 0 0 1 2 ) . T_{00,11}(R)=\begin{pmatrix}\tfrac1{\sqrt2}&0&0&-\tfrac1{\sqrt2}\\0&1&0&0\\0&0&1&0\\\tfrac1{\sqrt2}&0&0&\tfrac1{\sqrt2}\end{pmatrix}. T 00 , 11 ( R ) = 2 1 0 0 2 1 0 1 0 0 0 0 1 0 − 2 1 0 0 2 1 . 電路。 取 Q = C N O T 2 → 1 Q=\mathrm{CNOT}_{2\to1} Q = CNOT 2 → 1 ,它交換 01 ↔ 11 01\leftrightarrow11 01 ↔ 11 ,並固定 00 00 00 和 10 10 10 。那麼
T 00 , 11 ( R ) = Q Λ 0 1 → 2 ( R ) Q , T_{00,11}(R)=Q\,\Lambda^{1\to2}_0(R)\,Q, T 00 , 11 ( R ) = Q Λ 0 1 → 2 ( R ) Q , 時間順序為 Q Q Q 、Λ 0 1 → 2 ( R ) \Lambda^{1\to2}_0(R) Λ 0 1 → 2 ( R ) 、Q Q Q 。中間的門恰好在量子比特 1 為 0 0 0 時對量子比特 2 施加 R R R 。具體來說,
∣ 00 ⟩ ↦ 1 2 ( ∣ 00 ⟩ + ∣ 01 ⟩ ) , ∣ 01 ⟩ ↦ 1 2 ( − ∣ 00 ⟩ + ∣ 01 ⟩ ) , \lvert00\rangle\mapsto\tfrac1{\sqrt2}\big(\lvert00\rangle+\lvert01\rangle\big),\qquad
\lvert01\rangle\mapsto\tfrac1{\sqrt2}\big(-\lvert00\rangle+\lvert01\rangle\big), ∣ 00 ⟩ ↦ 2 1 ( ∣ 00 ⟩ + ∣ 01 ⟩ ) , ∣ 01 ⟩ ↦ 2 1 ( − ∣ 00 ⟩ + ∣ 01 ⟩ ) , 而 ∣ 10 ⟩ \lvert10\rangle ∣ 10 ⟩ 和 ∣ 11 ⟩ \lvert11\rangle ∣ 11 ⟩ 保持不變。
追蹤全部四個基底輸入 經過電路的結果:
∣ 00 ⟩ → Q ∣ 00 ⟩ → Λ 1 2 ( ∣ 00 ⟩ + ∣ 01 ⟩ ) → Q 1 2 ( ∣ 00 ⟩ + ∣ 11 ⟩ ) \lvert00\rangle\xrightarrow{Q}\lvert00\rangle\xrightarrow{\Lambda}\tfrac1{\sqrt2}(\lvert00\rangle+\lvert01\rangle)\xrightarrow{Q}\tfrac1{\sqrt2}(\lvert00\rangle+\lvert11\rangle) ∣ 00 ⟩ Q ∣ 00 ⟩ Λ 2 1 (∣ 00 ⟩ + ∣ 01 ⟩) Q 2 1 (∣ 00 ⟩ + ∣ 11 ⟩) . ✓
∣ 01 ⟩ → Q ∣ 11 ⟩ → Λ ∣ 11 ⟩ → Q ∣ 01 ⟩ \lvert01\rangle\xrightarrow{Q}\lvert11\rangle\xrightarrow{\Lambda}\lvert11\rangle\xrightarrow{Q}\lvert01\rangle ∣ 01 ⟩ Q ∣ 11 ⟩ Λ ∣ 11 ⟩ Q ∣ 01 ⟩ . ✓
∣ 10 ⟩ → Q ∣ 10 ⟩ → Λ ∣ 10 ⟩ → Q ∣ 10 ⟩ \lvert10\rangle\xrightarrow{Q}\lvert10\rangle\xrightarrow{\Lambda}\lvert10\rangle\xrightarrow{Q}\lvert10\rangle ∣ 10 ⟩ Q ∣ 10 ⟩ Λ ∣ 10 ⟩ Q ∣ 10 ⟩ . ✓
∣ 11 ⟩ → Q ∣ 01 ⟩ → Λ 1 2 ( − ∣ 00 ⟩ + ∣ 01 ⟩ ) → Q 1 2 ( − ∣ 00 ⟩ + ∣ 11 ⟩ ) \lvert11\rangle\xrightarrow{Q}\lvert01\rangle\xrightarrow{\Lambda}\tfrac1{\sqrt2}(-\lvert00\rangle+\lvert01\rangle)\xrightarrow{Q}\tfrac1{\sqrt2}(-\lvert00\rangle+\lvert11\rangle) ∣ 11 ⟩ Q ∣ 01 ⟩ Λ 2 1 ( − ∣ 00 ⟩ + ∣ 01 ⟩) Q 2 1 ( − ∣ 00 ⟩ + ∣ 11 ⟩) . ✓
輸出列向量依次為 ( 1 2 , 0 , 0 , 1 2 ) T (\tfrac1{\sqrt2},0,0,\tfrac1{\sqrt2})^{\mathsf T} ( 2 1 , 0 , 0 , 2 1 ) T 、e 1 e_1 e 1 、e 2 e_2 e 2 和 ( − 1 2 , 0 , 0 , 1 2 ) T (-\tfrac1{\sqrt2},0,0,\tfrac1{\sqrt2})^{\mathsf T} ( − 2 1 , 0 , 0 , 2 1 ) T ,恰好是上面矩陣的各列。
檢查區塊次序。 假如錯誤地在中間使用 Λ 0 1 → 2 ( X R X ) \Lambda^{1\to2}_0(XRX) Λ 0 1 → 2 ( X R X ) ,則 ∣ 00 ⟩ \lvert00\rangle ∣ 00 ⟩ 會映到 1 2 ( ∣ 00 ⟩ − ∣ 11 ⟩ ) \tfrac1{\sqrt2}(\lvert00\rangle-\lvert11\rangle) 2 1 (∣ 00 ⟩ − ∣ 11 ⟩) ,得到不同的門。區塊的次序不是表面細節。
餘下步驟。 負控制門為 Λ 0 1 → 2 ( R ) = X 1 Λ 1 1 → 2 ( R ) X 1 \Lambda^{1\to2}_0(R)=X_1\Lambda^{1\to2}_1(R)X_1 Λ 0 1 → 2 ( R ) = X 1 Λ 1 1 → 2 ( R ) X 1 。精確構造單控制門一節會用兩個 CNOT 和單量子比特門實現 Λ 1 1 → 2 ( R ) \Lambda^{1\to2}_1(R) Λ 1 1 → 2 ( R ) ,所以整個二能級門共用四個 CNOT。
受控相位門
定義受控相位門
C P ( φ ) = diag ( 1 , 1 , 1 , e i φ ) , 使得 C P ( φ ) ∣ a b ⟩ = e i φ a b ∣ a b ⟩ . \mathrm{CP}(\varphi)=\operatorname{diag}(1,1,1,e^{i\varphi}),\qquad\text{使得}\qquad \mathrm{CP}(\varphi)\lvert ab\rangle=e^{i\varphi ab}\lvert ab\rangle . CP ( φ ) = diag ( 1 , 1 , 1 , e i φ ) , 使得 CP ( φ ) ∣ ab ⟩ = e i φ ab ∣ ab ⟩ .
它對兩個量子比特是對稱的:C P ( φ ) = Λ 1 1 → 2 ( P ( φ ) ) = Λ 1 2 → 1 ( P ( φ ) ) \mathrm{CP}(\varphi)=\Lambda^{1\to2}_1(P(\varphi))=\Lambda^{2\to1}_1(P(\varphi)) CP ( φ ) = Λ 1 1 → 2 ( P ( φ )) = Λ 1 2 → 1 ( P ( φ )) 。
命題 9.2.12
(由兩個 CNOT 構造受控相位門)
對每個實數 φ \varphi φ ,
C P ( φ ) = ( P ( φ 2 ) ⊗ P ( φ 2 ) ) C N O T 1 → 2 ( I ⊗ P ( − φ 2 ) ) C N O T 1 → 2 . \mathrm{CP}(\varphi)=\big(P(\tfrac\varphi2)\otimes P(\tfrac\varphi2)\big)\ \mathrm{CNOT}_{1\to2}\ \big(I\otimes P(-\tfrac\varphi2)\big)\ \mathrm{CNOT}_{1\to2}. CP ( φ ) = ( P ( 2 φ ) ⊗ P ( 2 φ ) ) CNOT 1 → 2 ( I ⊗ P ( − 2 φ ) ) CNOT 1 → 2 . 這是精確等式,沒有全局相位的差異。
對比特 a , b a,b a , b ,整數恆等式 a + b = ( a ⊕ b ) + 2 a b a+b=(a\oplus b)+2ab a + b = ( a ⊕ b ) + 2 ab 給出
a b = 1 2 ( a + b − ( a ⊕ b ) ) , 因此 e i φ a b = e i φ a / 2 e i φ b / 2 e − i φ ( a ⊕ b ) / 2 . ab=\tfrac12\big(a+b-(a\oplus b)\big),
\qquad\text{因此}\qquad
e^{i\varphi ab}=e^{i\varphi a/2}\,e^{i\varphi b/2}\,e^{-i\varphi(a\oplus b)/2}. ab = 2 1 ( a + b − ( a ⊕ b ) ) , 因此 e i φ ab = e i φ a /2 e i φ b /2 e − i φ ( a ⊕ b ) /2 . 從右邊開始追蹤電路。
第一個 CNOT 把 ∣ a , b ⟩ ↦ ∣ a , a ⊕ b ⟩ \lvert a,b\rangle\mapsto\lvert a,a\oplus b\rangle ∣ a , b ⟩ ↦ ∣ a , a ⊕ b ⟩ 。
量子比特 2 上的 P ( − φ / 2 ) P(-\varphi/2) P ( − φ /2 ) 乘上 e − i φ ( a ⊕ b ) / 2 e^{-i\varphi(a\oplus b)/2} e − i φ ( a ⊕ b ) /2 。
第二個 CNOT 還原 ∣ a , b ⟩ \lvert a,b\rangle ∣ a , b ⟩ 。
最後,P ( φ / 2 ) ⊗ P ( φ / 2 ) P(\varphi/2)\otimes P(\varphi/2) P ( φ /2 ) ⊗ P ( φ /2 ) 乘上 e i φ a / 2 e i φ b / 2 e^{i\varphi a/2}e^{i\varphi b/2} e i φ a /2 e i φ b /2 。
總因子為 e i φ a b e^{i\varphi ab} e i φ ab 。明確地說,對 ∣ 00 ⟩ , ∣ 01 ⟩ , ∣ 10 ⟩ , ∣ 11 ⟩ \lvert00\rangle,\lvert01\rangle,\lvert10\rangle,\lvert11\rangle ∣ 00 ⟩ , ∣ 01 ⟩ , ∣ 10 ⟩ , ∣ 11 ⟩ ,因子依次為
1 , e i φ / 2 e − i φ / 2 = 1 , e i φ / 2 e − i φ / 2 = 1 , e i φ e 0 = e i φ . ■ 1,\qquad e^{i\varphi/2}e^{-i\varphi/2}=1,\qquad e^{i\varphi/2}e^{-i\varphi/2}=1,\qquad e^{i\varphi}e^{0}=e^{i\varphi}. \qquad\blacksquare 1 , e i φ /2 e − i φ /2 = 1 , e i φ /2 e − i φ /2 = 1 , e i φ e 0 = e i φ . ■
公式中的三個單量子比特門分別是量子比特 1 上的 P ( φ / 2 ) P(\varphi/2) P ( φ /2 ) 、量子比特 2 上的 P ( φ / 2 ) P(\varphi/2) P ( φ /2 ) ,以及量子比特 2 上的 P ( − φ / 2 ) P(-\varphi/2) P ( − φ /2 ) 。
精確構造單控制 U ( 2 ) U(2) U ( 2 ) 門
設 U ∈ U ( 2 ) U\in U(2) U ∈ U ( 2 ) 。由於 U U U 是正規矩陣,譜定理給出酉矩陣 V ∈ U ( 2 ) V\in U(2) V ∈ U ( 2 ) 和實數 α , β \alpha,\beta α , β ,使得
U = V diag ( e i α , e i β ) V † . U=V\,\operatorname{diag}(e^{i\alpha},e^{i\beta})\,V^\dagger . U = V diag ( e i α , e i β ) V † .
V V V 和代表角 α , β \alpha,\beta α , β 均不唯一。任何選擇都可行,但以下各處必須使用相同 的實數 α , β \alpha,\beta α , β 。若只把其中一處的角度模 2 π 2\pi 2 π 化簡,卻沒有一致地處理其他位置,半角便可能改變 π \pi π 的奇數倍,從而破壞恆等式。
定理 9.2.13
(以兩個 CNOT 精確構造受控 U)
按上述分解 U = V diag ( e i α , e i β ) V † U=V\operatorname{diag}(e^{i\alpha},e^{i\beta})V^\dagger U = V diag ( e i α , e i β ) V † ,有
Λ 1 1 → 2 ( U ) = ( P ( α + β 2 ) ⊗ V P ( β − α 2 ) ) C N O T 1 → 2 ( I ⊗ P ( α − β 2 ) ) C N O T 1 → 2 ( I ⊗ V † ) . \Lambda^{1\to2}_1(U)=\Big(P\big(\tfrac{\alpha+\beta}2\big)\otimes V P\big(\tfrac{\beta-\alpha}2\big)\Big)\ \mathrm{CNOT}_{1\to2}\ \Big(I\otimes P\big(\tfrac{\alpha-\beta}2\big)\Big)\ \mathrm{CNOT}_{1\to2}\ \big(I\otimes V^\dagger\big). Λ 1 1 → 2 ( U ) = ( P ( 2 α + β ) ⊗ V P ( 2 β − α ) ) CNOT 1 → 2 ( I ⊗ P ( 2 α − β ) ) CNOT 1 → 2 ( I ⊗ V † ) . 按時間順序:
在量子比特 2 上施加 V † V^\dagger V † ;
施加 C N O T 1 → 2 \mathrm{CNOT}_{1\to2} CNOT 1 → 2 ;
在量子比特 2 上施加 P ( α − β 2 ) P\big(\tfrac{\alpha-\beta}2\big) P ( 2 α − β ) ;
施加 C N O T 1 → 2 \mathrm{CNOT}_{1\to2} CNOT 1 → 2 ;
在量子比特 1 上施加 P ( α + β 2 ) P\big(\tfrac{\alpha+\beta}2\big) P ( 2 α + β ) ,同時在量子比特 2 上施加 V P ( β − α 2 ) VP\big(\tfrac{\beta-\alpha}2\big) V P ( 2 β − α ) 。
電路用了兩個 CNOT 和四個單量子比特門:控制比特上一個,目標比特上三個。
記 Δ = diag ( e i α , e i β ) \Delta=\operatorname{diag}(e^{i\alpha},e^{i\beta}) Δ = diag ( e i α , e i β ) 。首先,在目標比特上用 V V V 共軛,等於共軛受控操作中的目標算子:
( I ⊗ V ) ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ Δ ) ( I ⊗ V † ) = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ V Δ V † . (I\otimes V)\big(\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes\Delta\big)(I\otimes V^\dagger)=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes V\Delta V^\dagger . ( I ⊗ V ) ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ Δ ) ( I ⊗ V † ) = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ V Δ V † . 因此 Λ 1 1 → 2 ( U ) = ( I ⊗ V ) Λ 1 1 → 2 ( Δ ) ( I ⊗ V † ) \Lambda^{1\to2}_1(U)=(I\otimes V)\,\Lambda^{1\to2}_1(\Delta)\,(I\otimes V^\dagger) Λ 1 1 → 2 ( U ) = ( I ⊗ V ) Λ 1 1 → 2 ( Δ ) ( I ⊗ V † ) 。接著,Λ 1 1 → 2 ( Δ ) \Lambda^{1\to2}_1(\Delta) Λ 1 1 → 2 ( Δ ) 是對角算子,可拆成控制比特上的相位和一個受控相位門:
Λ 1 1 → 2 ( Δ ) = diag ( 1 , 1 , e i α , e i β ) = ( P ( α ) ⊗ I ) C P ( β − α ) . \Lambda^{1\to2}_1(\Delta)=\operatorname{diag}(1,1,e^{i\alpha},e^{i\beta})=\big(P(\alpha)\otimes I\big)\,\mathrm{CP}(\beta-\alpha). Λ 1 1 → 2 ( Δ ) = diag ( 1 , 1 , e i α , e i β ) = ( P ( α ) ⊗ I ) CP ( β − α ) . 為了驗證,右邊是 diag ( 1 , 1 , e i α , e i α ) ⋅ diag ( 1 , 1 , 1 , e i ( β − α ) ) \operatorname{diag}(1,1,e^{i\alpha},e^{i\alpha})\cdot\operatorname{diag}(1,1,1,e^{i(\beta-\alpha)}) diag ( 1 , 1 , e i α , e i α ) ⋅ diag ( 1 , 1 , 1 , e i ( β − α ) ) 。
現在以 φ = β − α \varphi=\beta-\alpha φ = β − α 代入受控相位命題。因子 P ( α ) ⊗ I P(\alpha)\otimes I P ( α ) ⊗ I 和 P ( φ / 2 ) ⊗ P ( φ / 2 ) P(\varphi/2)\otimes P(\varphi/2) P ( φ /2 ) ⊗ P ( φ /2 ) 與最左邊的 I ⊗ V I\otimes V I ⊗ V 合併成
P ( α + φ 2 ) ⊗ V P ( φ 2 ) , P\big(\alpha+\tfrac\varphi2\big)\otimes VP\big(\tfrac\varphi2\big), P ( α + 2 φ ) ⊗ V P ( 2 φ ) , 因為量子比特 1 上的門與量子比特 2 上的門可交換。由於 α + φ 2 = α + β 2 \alpha+\tfrac\varphi2=\tfrac{\alpha+\beta}2 α + 2 φ = 2 α + β 和 φ 2 = β − α 2 \tfrac\varphi2=\tfrac{\beta-\alpha}2 2 φ = 2 β − α ,這正是所聲稱的公式。■ \blacksquare ■
證明透視
半角與純量從何而來 推導有三個運作部分,每一部分都可以單獨審核。對 U = V Δ V † U=V\Delta V^\dagger U = V Δ V † 作對角化只用了一次,目的是把所有非對角結構移到目標比特上:控制比特只決定是否施加目標算子,所以在目標比特上用 V V V 共軛,就等於共軛受控門。關鍵一步是拆分 diag ( 1 , 1 , e i α , e i β ) = ( P ( α ) ⊗ I ) C P ( β − α ) \operatorname{diag}(1,1,e^{i\alpha},e^{i\beta})=(P(\alpha)\otimes I)\,\mathrm{CP}(\beta-\alpha) diag ( 1 , 1 , e i α , e i β ) = ( P ( α ) ⊗ I ) CP ( β − α ) ,使受控相位成為唯一真正涉及兩個量子比特的因子。
純量是微妙之處。在控制值為 1 1 1 的分支,兩個 CNOT 都對目標比特施加 X X X ,而 X P ( θ ) X = diag ( e i θ , 1 ) = e i θ P ( − θ ) XP(\theta)X=\operatorname{diag}(e^{i\theta},1)=e^{i\theta}P(-\theta) X P ( θ ) X = diag ( e i θ , 1 ) = e i θ P ( − θ ) 。目標比特上的純量單獨看不會顯現,但這裏它只出現在其中一個控制分支,所以是相對相位。取 θ = ( α − β ) / 2 \theta=(\alpha-\beta)/2 θ = ( α − β ) /2 ,它貢獻 e i ( α − β ) / 2 e^{i(\alpha-\beta)/2} e i ( α − β ) /2 ;量子比特 1 上的門 P ( α + β 2 ) P(\tfrac{\alpha+\beta}2) P ( 2 α + β ) 貢獻 e i ( α + β ) / 2 e^{i(\alpha+\beta)/2} e i ( α + β ) /2 。兩者合起來恰好是 e i α e^{i\alpha} e i α 。
兩個分支隨後閉合。控制值為 0 0 0 時,CNOT 不起作用,目標比特受到 V P ( β − α 2 ) P ( α − β 2 ) V † = I VP(\tfrac{\beta-\alpha}2)P(\tfrac{\alpha-\beta}2)V^\dagger=I V P ( 2 β − α ) P ( 2 α − β ) V † = I 的作用。控制值為 1 1 1 時,它受到
e i α V diag ( 1 , e i ( β − α ) ) V † = U e^{i\alpha}\,V\operatorname{diag}\big(1,e^{i(\beta-\alpha)}\big)V^\dagger=U e i α V diag ( 1 , e i ( β − α ) ) V † = U 的作用。若省去控制比特上的門,或在不同因子中使用 α , β \alpha,\beta α , β 的不同代表元,便可能把控制值為 1 1 1 的分支變成 e i χ U e^{i\chi}U e i χ U ,其中 χ ≢ 0 \chi\not\equiv0 χ ≡ 0 ,下面的反例會說明這一點。
變式
控制比特為量子比特 2,目標為量子比特 1。 在整個構造中交換兩個量子比特的角色,並使用 C N O T 2 → 1 \mathrm{CNOT}_{2\to1} CNOT 2 → 1 。證明完全相同。
負控制。 使用 Λ 0 s → t ( U ) = X s Λ 1 s → t ( U ) X s \Lambda^{s\to t}_0(U)=X_s\Lambda^{s\to t}_1(U)X_s Λ 0 s → t ( U ) = X s Λ 1 s → t ( U ) X s 。這在控制比特上增加兩個單量子比特門,沒有增加 CNOT。
任意二能級區塊。 依相鄰對引理,受控門可以是 Λ ( M ) \Lambda(M) Λ ( M ) 或 Λ ( X M X ) \Lambda(XMX) Λ ( X M X ) 。M M M 和 X M X XMX X M X 都是 U ( 2 ) U(2) U ( 2 ) 的元素,因此受控 U 定理對兩種受控門均適用。
反例模式
忽略條件化的全局相位 一個誘人的捷徑是:「單量子比特門只需考慮到全局相位,所以要控制 U U U ,控制任何滿足 W = e i χ U W=e^{i\chi}U W = e i χ U 的 W W W 就夠了。」這是錯誤的。
取 U = − I = e i π I U=-I=e^{i\pi}I U = − I = e iπ I 。粗心的構造會認為 U U U 「除相位外就是恆等算子」,於是實現 Λ 1 1 → 2 ( I ) = I ⊗ I \Lambda^{1\to2}_1(I)=I\otimes I Λ 1 1 → 2 ( I ) = I ⊗ I ,即甚麼門也不施加。真正的受控門是
Λ 1 1 → 2 ( − I ) = diag ( 1 , 1 , − 1 , − 1 ) = Z ⊗ I . \Lambda^{1\to2}_1(-I)=\operatorname{diag}(1,1,-1,-1)=Z\otimes I . Λ 1 1 → 2 ( − I ) = diag ( 1 , 1 , − 1 , − 1 ) = Z ⊗ I . 對輸入 ∣ + ⟩ ∣ 0 ⟩ \lvert+\rangle\lvert0\rangle ∣ + ⟩ ∣ 0 ⟩ ,其中 ∣ + ⟩ = 1 2 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) \lvert+\rangle=\tfrac1{\sqrt2}(\lvert0\rangle+\lvert1\rangle) ∣ + ⟩ = 2 1 (∣ 0 ⟩ + ∣ 1 ⟩) :
粗心構造的電路輸出 ∣ + ⟩ ∣ 0 ⟩ \lvert+\rangle\lvert0\rangle ∣ + ⟩ ∣ 0 ⟩ ;
正確的門輸出 ∣ − ⟩ ∣ 0 ⟩ \lvert-\rangle\lvert0\rangle ∣ − ⟩ ∣ 0 ⟩ ,其中 ∣ − ⟩ = 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) \lvert-\rangle=\tfrac1{\sqrt2}(\lvert0\rangle-\lvert1\rangle) ∣ − ⟩ = 2 1 (∣ 0 ⟩ − ∣ 1 ⟩) 。
這兩個狀態是正交 的。以 ∣ ± ⟩ \lvert\pm\rangle ∣ ± ⟩ 基底測量量子比特 1,便能確定地區分兩者。U U U 的「全局」相位已變成控制比特兩個分支之間的相對 相位。
同樣的錯誤也會出現在受控 U 定理中。把控制比特上的門 P ( α + β 2 ) P(\tfrac{\alpha+\beta}2) P ( 2 α + β ) 換成 P ( β − α 2 ) P(\tfrac{\beta-\alpha}2) P ( 2 β − α ) ,相當於在推導中漏掉因子 P ( α ) ⊗ I P(\alpha)\otimes I P ( α ) ⊗ I 。這時控制值為 1 1 1 的分支得到的是 e − i α U e^{-i\alpha}U e − i α U ,而非 U U U ,電路實現的是 Λ 1 1 → 2 ( e − i α U ) \Lambda^{1\to2}_1(e^{-i\alpha}U) Λ 1 1 → 2 ( e − i α U ) 。只有當 e i α = 1 e^{i\alpha}=1 e i α = 1 時,它才與所需的門精確相等。
對角雙量子比特酉算子
設 D = diag ( e i θ 0 , e i θ 1 , e i θ 2 , e i θ 3 ) D=\operatorname{diag}(e^{i\theta_0},e^{i\theta_1},e^{i\theta_2},e^{i\theta_3}) D = diag ( e i θ 0 , e i θ 1 , e i θ 2 , e i θ 3 ) ,其中 θ ℓ \theta_\ell θ ℓ 為實數。提出第一個對角元素,寫成
D = e i θ 0 diag ( 1 , e i β 1 , e i β 2 , e i β 3 ) , β ℓ = θ ℓ − θ 0 . D=e^{i\theta_0}\operatorname{diag}\big(1,e^{i\beta_1},e^{i\beta_2},e^{i\beta_3}\big),\qquad \beta_\ell=\theta_\ell-\theta_0 . D = e i θ 0 diag ( 1 , e i β 1 , e i β 2 , e i β 3 ) , β ℓ = θ ℓ − θ 0 .
令 γ = β 3 − β 1 − β 2 \gamma=\beta_3-\beta_1-\beta_2 γ = β 3 − β 1 − β 2 ,則
D = ( e i θ 0 P ( β 2 ) ⊗ P ( β 1 ) ) C P ( γ ) . D=\big(e^{i\theta_0}P(\beta_2)\otimes P(\beta_1)\big)\ \mathrm{CP}(\gamma). D = ( e i θ 0 P ( β 2 ) ⊗ P ( β 1 ) ) CP ( γ ) . 利用受控相位命題,並合併可交換的因子,得到
D = ( e i θ 0 P ( β 2 + γ 2 ) ⊗ P ( β 1 + γ 2 ) ) C N O T 1 → 2 ( I ⊗ P ( − γ 2 ) ) C N O T 1 → 2 . D=\Big(e^{i\theta_0}P\big(\beta_2+\tfrac\gamma2\big)\otimes P\big(\beta_1+\tfrac\gamma2\big)\Big)\ \mathrm{CNOT}_{1\to2}\ \big(I\otimes P(-\tfrac\gamma2)\big)\ \mathrm{CNOT}_{1\to2}. D = ( e i θ 0 P ( β 2 + 2 γ ) ⊗ P ( β 1 + 2 γ ) ) CNOT 1 → 2 ( I ⊗ P ( − 2 γ ) ) CNOT 1 → 2 . 此電路使用兩個 CNOT 和三個單量子比特門;等式精確成立,包括全局相位。
比較對角元素。因子 P ( β 2 ) ⊗ P ( β 1 ) P(\beta_2)\otimes P(\beta_1) P ( β 2 ) ⊗ P ( β 1 ) 在 ∣ a b ⟩ \lvert ab\rangle ∣ ab ⟩ 上貢獻 e i ( a β 2 + b β 1 ) e^{i(a\beta_2+b\beta_1)} e i ( a β 2 + b β 1 ) ,而 C P ( γ ) \mathrm{CP}(\gamma) CP ( γ ) 貢獻 e i γ a b e^{i\gamma ab} e iγ ab 。所得元素如下:
∣ 00 ⟩ \lvert00\rangle ∣ 00 ⟩ : e i θ 0 e^{i\theta_0} e i θ 0 ;
∣ 01 ⟩ \lvert01\rangle ∣ 01 ⟩ : e i θ 0 e i β 1 = e i θ 1 e^{i\theta_0}e^{i\beta_1}=e^{i\theta_1} e i θ 0 e i β 1 = e i θ 1 ;
∣ 10 ⟩ \lvert10\rangle ∣ 10 ⟩ : e i θ 0 e i β 2 = e i θ 2 e^{i\theta_0}e^{i\beta_2}=e^{i\theta_2} e i θ 0 e i β 2 = e i θ 2 ;
∣ 11 ⟩ \lvert11\rangle ∣ 11 ⟩ : e i θ 0 e i ( β 1 + β 2 + γ ) = e i θ 0 e i β 3 = e i θ 3 e^{i\theta_0}e^{i(\beta_1+\beta_2+\gamma)}=e^{i\theta_0}e^{i\beta_3}=e^{i\theta_3} e i θ 0 e i ( β 1 + β 2 + γ ) = e i θ 0 e i β 3 = e i θ 3 。
把純量 e i θ 0 e^{i\theta_0} e i θ 0 併入作用於量子比特 1 的單量子比特門後,該門仍屬於 U ( 2 ) U(2) U ( 2 ) 。■ \blacksquare ■
同一個想法解釋了所有對角雙量子比特酉算子的結構。∣ a b ⟩ \lvert ab\rangle ∣ ab ⟩ 上的相角是兩個比特的函數,因此可寫成
θ 0 + β 2 a + β 1 b + γ a b . \theta_0+\beta_2a+\beta_1b+\gamma ab . θ 0 + β 2 a + β 1 b + γ ab .
常數項、線性項和乘積項分別由全局相位、單量子比特相位門及一個受控相位提供。
組合各步:主定理
每個 U ∈ U ( 4 ) U\in U(4) U ∈ U ( 4 ) 都精確等於至多 18 18 18 個 CNOT 門和至多 39 39 39 個來自 U ( 2 ) U(2) U ( 2 ) 的單量子比特門的乘積,包括全局相位;這些門只作用於給定的兩個量子比特。
由消元定理和重構公式,
U = G 1 † G 2 † G 3 † G 4 † G 5 † G 6 † D . U=G_1^\dagger G_2^\dagger G_3^\dagger G_4^\dagger G_5^\dagger G_6^\dagger D . U = G 1 † G 2 † G 3 † G 4 † G 5 † G 6 † D . 對角因子。 根據對角構造命題,用 2 2 2 個 CNOT 及 3 3 3 個單量子比特門合成 D D D 。
二能級因子。 每個 G i † = T k i , j i ( M i † ) G_i^\dagger=T_{k_i,j_i}(M_i^\dagger) G i † = T k i , j i ( M i † ) 均按步驟表中的電路實現,其中受控門由受控 U 定理提供。
每個正控制的 Λ 1 ( ⋅ ) \Lambda_1(\cdot) Λ 1 ( ⋅ ) 需要 2 2 2 個 CNOT 和 4 4 4 個單量子比特門。
每個負控制的 Λ 0 ( ⋅ ) \Lambda_0(\cdot) Λ 0 ( ⋅ ) 需要 2 2 2 個 CNOT 和至多 6 6 6 個單量子比特門。
對頂配對另需 2 2 2 個正控制的 CNOT,無須額外單量子比特門。
因此每個二能級因子至多需要 6 6 6 個單量子比特門。四個相鄰配對各需 2 2 2 個 CNOT,兩個對頂配對各需 4 4 4 個。
總數。
CNOT 數目 ≤ 2 + 2 + 4 + 4 + 2 + 2 + 2 = 18 , 單量子比特閘 ≤ 6 ⋅ 6 + 3 = 39. \text{CNOT 數目}\le 2+2+4+4+2+2+2=18,\qquad \text{單量子比特閘}\le 6\cdot 6+3=39 . CNOT 數目 ≤ 2 + 2 + 4 + 4 + 2 + 2 + 2 = 18 , 單量子比特閘 ≤ 6 ⋅ 6 + 3 = 39. 以上每個等式都是精確的,所以乘積精確等於 U U U 。任何等於恆等算子的 G i G_i G i 都可省略,這只會減少門的數目。■ \blacksquare ■
關於數目的說明。
這些上界對每個 U U U 都成立;它們是此構造所保證的數目,並非下界,更不聲稱是最優值。
組合後電路中的相鄰 CNOT 和單量子比特門經常可以合併或抵消。我們不進一步作這些簡化,因此只聲稱上述上界。
如果只能使用 C N O T 1 → 2 \mathrm{CNOT}_{1\to2} CNOT 1 → 2 ,每個 C N O T 2 → 1 \mathrm{CNOT}_{2\to1} CNOT 2 → 1 可由 ( H ⊗ H ) C N O T 1 → 2 ( H ⊗ H ) (H\otimes H)\mathrm{CNOT}_{1\to2}(H\otimes H) ( H ⊗ H ) CNOT 1 → 2 ( H ⊗ H ) 取代(見後面以 Hadamard 門共軛 CNOT 的習題)。CNOT 的上界仍是 18 18 18 ,每次取代則使單量子比特門的數目最多增加 4 4 4 個 Hadamard 門。
複合置換的共軛方向
對兩個量子比特,把二能級酉操作表示成受控門一節中的重新標記總可用一個 CNOT 完成,而且單個 CNOT 是對合。在較大的寄存器中,沿較長漢明路徑移動端點的置換是若干 CNOT 類門的乘積 ,而這些乘積一般不是對合。以下雙量子比特例子說明,此時選擇 Q G Q − 1 QGQ^{-1} QG Q − 1 還是 Q − 1 G Q Q^{-1}GQ Q − 1 GQ 有多重要。
反例模式
P G P⁻¹ 與 P⁻¹ G P 令 Q = C N O T 1 → 2 C N O T 2 → 1 Q=\mathrm{CNOT}_{1\to2}\,\mathrm{CNOT}_{2\to1} Q = CNOT 1 → 2 CNOT 2 → 1 。按時間順序,先作用的是 C N O T 2 → 1 \mathrm{CNOT}_{2\to1} CNOT 2 → 1 ,然後是 C N O T 1 → 2 \mathrm{CNOT}_{1\to2} CNOT 1 → 2 。標籤的變化為
00 ↦ 00 , 01 ↦ 11 ↦ 10 , 10 ↦ 10 ↦ 11 , 11 ↦ 01 ↦ 01. 00\mapsto00,\quad 01\mapsto11\mapsto10,\quad 10\mapsto10\mapsto11,\quad 11\mapsto01\mapsto01 . 00 ↦ 00 , 01 ↦ 11 ↦ 10 , 10 ↦ 10 ↦ 11 , 11 ↦ 01 ↦ 01. 因此 Q Q Q 固定 00 00 00 ,並在其他三個標籤上作 3 3 3 -循環 01 → 10 → 11 → 01 01\to10\to11\to01 01 → 10 → 11 → 01 ;Q − 1 Q^{-1} Q − 1 則是反方向的循環。令 G = T 00 , 01 ( M ) G=T_{00,01}(M) G = T 00 , 01 ( M ) 。由共軛引理,
Q G Q − 1 = T Q 00 , Q 01 ( M ) = T 00 , 10 ( M ) , Q − 1 G Q = T Q − 1 00 , Q − 1 01 ( M ) = T 00 , 11 ( M ) . QGQ^{-1}=T_{Q00,\,Q01}(M)=T_{00,10}(M),\qquad
Q^{-1}GQ=T_{Q^{-1}00,\,Q^{-1}01}(M)=T_{00,11}(M). QG Q − 1 = T Q 00 , Q 01 ( M ) = T 00 , 10 ( M ) , Q − 1 GQ = T Q − 1 00 , Q − 1 01 ( M ) = T 00 , 11 ( M ) . 這兩個共軛算子作用於不同的基向量配對。若要用這個 Q Q Q 從 G G G 實現作用於 ( 00 , 11 ) (00,11) ( 00 , 11 ) 的二能級門,就必須使用 Q − 1 G Q Q^{-1}GQ Q − 1 GQ 。按時間順序,即先施加 Q Q Q ,再施加 G G G ,最後施加 Q − 1 = C N O T 2 → 1 C N O T 1 → 2 Q^{-1}=\mathrm{CNOT}_{2\to1}\mathrm{CNOT}_{1\to2} Q − 1 = CNOT 2 → 1 CNOT 1 → 2 。
可靠的規則就是共軛引理:選用把輔助標籤送到原來端點的置換來作共軛,並把該置換放在 G G G 的左邊 ,其逆放在右邊。
從任意角度到有限門集
普適性定理使用任意 U ( 2 ) U(2) U ( 2 ) 元素,即精確指定的任意實數角度。這是數學上的理想化;容錯或編譯後的環境通常只提供例如 { H , T , C N O T } \{H,T,\mathrm{CNOT}\} { H , T , CNOT } 這樣的有限門集,因而改變了我們能夠聲稱的結果。
不再能要求精確實現
有限門集只能組成可數多個有限電路,而 U ( 4 ) U(4) U ( 4 ) 不可數。即使把只相差全局相位的酉算子視為同一類,所得的類仍不可數。因此,除了可數多個例外,雙量子比特酉算子不能 由 H H H 、T T T 和 CNOT 精確實現。使用有限門集時,合適的目標是近似。
所需的稠密性結果
我們使用配套筆記中以下形式的稠密性:對每個 W ∈ U ( 2 ) W\in U(2) W ∈ U ( 2 ) 和每個 δ > 0 \delta\gt0 δ > 0 ,存在一個由 H H H 和 T T T 組成的有限字 w w w 及一個實數 χ \chi χ ,使得
∥ w − e i χ W ∥ ≤ δ . \lVert w-e^{i\chi}W\rVert\le\delta . ∥ w − e i χ W ∥ ≤ δ .
這裏 ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ 表示算子範數。相位 e i χ e^{i\chi} e i χ 出現是因為稠密性的陳述是模全局相位而言;CNOT 無須近似。
誤差最多線性相加
設 V 1 , … , V m V_1,\dots,V_m V 1 , … , V m 及 V ~ 1 , … , V ~ m \tilde V_1,\dots,\tilde V_m V ~ 1 , … , V ~ m 為同一空間上的酉算子,且對每個 j j j 均有 ∥ V ~ j − V j ∥ ≤ ε j \lVert\tilde V_j-V_j\rVert\le\varepsilon_j ∥ V ~ j − V j ∥ ≤ ε j 。則
∥ V ~ m ⋯ V ~ 1 − V m ⋯ V 1 ∥ ≤ ∑ j = 1 m ε j . \big\lVert\tilde V_m\cdots\tilde V_1-V_m\cdots V_1\big\rVert\le\sum_{j=1}^m\varepsilon_j . V ~ m ⋯ V ~ 1 − V m ⋯ V 1 ≤ j = 1 ∑ m ε j .
差可展開成望遠鏡和:
V ~ m ⋯ V ~ 1 − V m ⋯ V 1 = ∑ j = 1 m V m ⋯ V j + 1 ( V ~ j − V j ) V ~ j − 1 ⋯ V ~ 1 . \tilde V_m\cdots\tilde V_1-V_m\cdots V_1=\sum_{j=1}^m V_m\cdots V_{j+1}\,(\tilde V_j-V_j)\,\tilde V_{j-1}\cdots\tilde V_1 . V ~ m ⋯ V ~ 1 − V m ⋯ V 1 = j = 1 ∑ m V m ⋯ V j + 1 ( V ~ j − V j ) V ~ j − 1 ⋯ V ~ 1 . 注意相鄰項會互相抵消:第 j j j 項等於 A j − A j − 1 A_j-A_{j-1} A j − A j − 1 ,其中 A j = V m ⋯ V j + 1 V ~ j ⋯ V ~ 1 A_j=V_m\cdots V_{j+1}\tilde V_j\cdots\tilde V_1 A j = V m ⋯ V j + 1 V ~ j ⋯ V ~ 1 ,而 A m A_m A m 是完全近似的乘積,A 0 A_0 A 0 是精確乘積。在算子的任何一側乘以酉算子都不改變其算子範數,因此第 j j j 項的範數至多是 ε j \varepsilon_j ε j ;最後使用三角不等式即得結論。■ \blacksquare ■
兩點說明。
嵌入雙量子比特空間的單量子比特門滿足 ∥ ( W ~ − W ) ⊗ I ∥ = ∥ W ~ − W ∥ \lVert(\tilde W-W)\otimes I\rVert=\lVert\tilde W-W\rVert ∥( W ~ − W ) ⊗ I ∥ = ∥ W ~ − W ∥ ,所以單量子比特誤差在雙量子比特空間中保持不變。
若 ∥ V ~ j − e i χ j V j ∥ ≤ ε j \lVert\tilde V_j-e^{i\chi_j}V_j\rVert\le\varepsilon_j ∥ V ~ j − e i χ j V j ∥ ≤ ε j ,便對酉算子 e i χ j V j e^{i\chi_j}V_j e i χ j V j 應用望遠鏡引理。結論變為 ∥ U ~ − e i χ U ∥ ≤ ∑ j ε j \lVert\tilde U-e^{i\chi}U\rVert\le\sum\limits_j\varepsilon_j ∥ U ~ − e i χ U ∥ ≤ j ∑ ε j ,其中 χ = ∑ j χ j \chi=\sum\limits_j\chi_j χ = j ∑ χ j 。
對普適性定理的推論。 固定 ε > 0 \varepsilon\gt0 ε > 0 。把至多 39 39 39 個單量子比特門各自換成一個 { H , T } \{H,T\} { H , T } 字,其與原門相差某個相位後的距離至多為 δ = ε / 39 \delta=\varepsilon/39 δ = ε /39 ,並保留精確的 CNOT。所得電路 U ~ \tilde U U ~ 滿足
∥ U ~ − e i χ U ∥ ≤ ε \lVert\tilde U-e^{i\chi}U\rVert\le\varepsilon ∥ U ~ − e i χ U ∥ ≤ ε
其中 χ \chi χ 是某個實數。
對測量統計的影響。 設 Π \Pi Π 為正交投影算子,對單位向量 ψ \psi ψ 令 u = e i χ U ψ u=e^{i\chi}U\psi u = e i χ U ψ 、v = U ~ ψ v=\tilde U\psi v = U ~ ψ 。則 ∥ u − v ∥ ≤ ε \lVert u-v\rVert\le\varepsilon ∥ u − v ∥ ≤ ε 。由於 ∥ Π u ∥ , ∥ Π v ∥ ≤ 1 \lVert\Pi u\rVert,\lVert\Pi v\rVert\le1 ∥ Π u ∥ , ∥ Π v ∥ ≤ 1 ,而反三角不等式給出 ∣ ∥ Π u ∥ − ∥ Π v ∥ ∣ ≤ ∥ Π ( u − v ) ∥ ≤ ε \big|\lVert\Pi u\rVert-\lVert\Pi v\rVert\big|\le\lVert\Pi(u-v)\rVert\le\varepsilon ∥ Π u ∥ − ∥ Π v ∥ ≤ ∥ Π ( u − v )∥ ≤ ε ,所以
∣ ∥ Π u ∥ 2 − ∥ Π v ∥ 2 ∣ = ∣ ∥ Π u ∥ − ∥ Π v ∥ ∣ ⋅ ( ∥ Π u ∥ + ∥ Π v ∥ ) ≤ 2 ε . \big|\lVert\Pi u\rVert^2-\lVert\Pi v\rVert^2\big|
=\big|\lVert\Pi u\rVert-\lVert\Pi v\rVert\big|\cdot\big(\lVert\Pi u\rVert+\lVert\Pi v\rVert\big)\le2\varepsilon . ∥ Π u ∥ 2 − ∥ Π v ∥ 2 = ∥ Π u ∥ − ∥ Π v ∥ ⋅ ( ∥ Π u ∥ + ∥ Π v ∥ ) ≤ 2 ε .
因此每個結果的概率最多相差 2 ε 2\varepsilon 2 ε 。全局相位 e i χ e^{i\chi} e i χ 不影響這些概率。
兩個注意事項
被忽略的相位可能再次出現。 此近似只在相差全局相位 e i χ e^{i\chi} e i χ 的意義下成立。對獨立使用的電路,這並無影響;但若日後把近似電路用作受控操作的目標,精確構造單控制門一節中的反例顯示 e i χ e^{i\chi} e i χ 會變成相對相位。此時必須記錄並修正相位,或直接近似受控操作。
稠密性沒有給出長度上界。 稠密性保證合適的字存在,卻沒有說明它們有多長。配套筆記陳述但沒有證明 Solovay–Kitaev 定理;該定理指出字長可控制在 1 / δ 1/\delta 1/ δ 的多對數量級。本筆記的論證並不依賴該定理。
超過兩個量子比特的情況(只陳述,不證明)
消元定理的消去論證可原封不動地用於 U ∈ U ( N ) U\in U(N) U ∈ U ( N ) 。取 N = 2 n N=2^n N = 2 n ,便得到至多 N ( N − 1 ) / 2 N(N-1)/2 N ( N − 1 ) /2 個二能級因子及其後一個對角酉算子。上三角引理亦適用於任何維度。
本筆記未能 直接推廣的是在 n > 2 n\gt2 n > 2 個量子比特上實現二能級酉算子的步驟。那需要多個控制位的門,以及用多重受控 NOT 沿 Gray 碼重新標記;要在不用輔助量子比特的情況下,以 CNOT 和單量子比特門建構它們,還需本筆記沒有證明的其他構造。
已知定理(Barenco 等人,1995;只陳述,不證明)。 對每個 n ≥ 1 n\ge1 n ≥ 1 ,每個 n n n 量子比特上的酉算子都可精確寫成有限個 CNOT 門和單量子比特酉門的乘積。
存在性本身沒有說明效率。尤其是,它不 意味著一般的 n n n 量子比特酉算子都有大小為 n n n 的多項式的電路。單是消去法產生的二能級因子數目已按 4 n 4^n 4 n 的量級增長。普適性說明可以建構甚麼,卻沒有說明哪些建構的成本低。
常見錯誤和細節
先後施加 g 1 g_1 g 1 、g 2 g_2 g 2 的電路實現的是 g 2 g 1 g_2g_1 g 2 g 1 ,而不是 g 1 g 2 g_1g_2 g 1 g 2 。重構時也要同樣小心:正確公式是 U = G 1 † ⋯ G 6 † D U=G_1^\dagger\cdots G_6^\dagger D U = G 1 † ⋯ G 6 † D ,因為作用於有重疊配對的二能級因子未必交換。此外,消元後留下的對角因子 D D D 是一般的模長為 1 1 1 的對角矩陣,並不是 I I I ,必須另行合成。
一般而言 T x , y ( M ) ≠ T y , x ( M ) T_{x,y}(M)\neq T_{y,x}(M) T x , y ( M ) = T y , x ( M ) :若第一個標籤的目標比特是 1 1 1 ,相鄰對引理便需要 X M X XMX X M X 。同樣,規則是 Q T x , z Q − 1 = T Q x , Q z QT_{x,z}Q^{-1}=T_{Qx,Qz} Q T x , z Q − 1 = T Q x , Q z ;對非對合的 Q Q Q ,兩個共軛次序會給出不同的門。
受控 e i χ U e^{i\chi}U e i χ U 與受控 U U U 相比,在控制比特上多了 P ( χ ) P(\chi) P ( χ ) 。受控 U U U 定理與受控相位命題中的半角也必須全程使用同一組實數 α , β , φ \alpha,\beta,\varphi α , β , φ ,因為只對其中一處取模 2 π 2\pi 2 π 而不對另一處取,會破壞恆等式。
習題
練習 9.2.17
(證明 C N O T 2 → 1 = ( H ⊗ H ) C N O T 1 → 2 ( H ⊗ H ) \mathrm{CNOT}_{2\to1}=(H\otimes H)\,\mathrm{CNOT}_{1\to2}\,(H\otimes H) CNOT 2 → 1 = ( H ⊗ H ) CNOT 1 → 2 ( H ⊗ H ) 。)
核心 證明
解答 (3) 1 對 CNOT 的投影算子形式作共軛
寫成
C N O T 1 → 2 = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ X . \mathrm{CNOT}_{1\to2}=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes X . CNOT 1 → 2 = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I + ∣ 1 ⟩ ⟨ 1 ∣ ⊗ X . 利用 H ∣ 0 ⟩ ⟨ 0 ∣ H = ∣ + ⟩ ⟨ + ∣ H\lvert0\rangle\langle0\rvert H=\lvert+\rangle\langle+\rvert H ∣ 0 ⟩ ⟨ 0 ∣ H = ∣ + ⟩ ⟨ + ∣ 、H ∣ 1 ⟩ ⟨ 1 ∣ H = ∣ − ⟩ ⟨ − ∣ H\lvert1\rangle\langle1\rvert H=\lvert-\rangle\langle-\rvert H ∣ 1 ⟩ ⟨ 1 ∣ H = ∣ − ⟩ ⟨ − ∣ 、H I H = I HIH=I H I H = I 和 H X H = Z HXH=Z H X H = Z 。以 H ⊗ H H\otimes H H ⊗ H 共軛後得
∣ + ⟩ ⟨ + ∣ ⊗ I + ∣ − ⟩ ⟨ − ∣ ⊗ Z . \lvert+\rangle\langle+\rvert\otimes I+\lvert-\rangle\langle-\rvert\otimes Z . ∣ + ⟩ ⟨ + ∣ ⊗ I + ∣ − ⟩ ⟨ − ∣ ⊗ Z . 2 按量子比特 2 的投影算子合併各項
展開 I = ∣ 0 ⟩ ⟨ 0 ∣ + ∣ 1 ⟩ ⟨ 1 ∣ I=\lvert0\rangle\langle0\rvert+\lvert1\rangle\langle1\rvert I = ∣ 0 ⟩ ⟨ 0 ∣ + ∣ 1 ⟩ ⟨ 1 ∣ 和 Z = ∣ 0 ⟩ ⟨ 0 ∣ − ∣ 1 ⟩ ⟨ 1 ∣ Z=\lvert0\rangle\langle0\rvert-\lvert1\rangle\langle1\rvert Z = ∣ 0 ⟩ ⟨ 0 ∣ − ∣ 1 ⟩ ⟨ 1 ∣ ,按量子比特 2 的投影算子合併各項:
( ∣ + ⟩ ⟨ + ∣ + ∣ − ⟩ ⟨ − ∣ ) ⊗ ∣ 0 ⟩ ⟨ 0 ∣ + ( ∣ + ⟩ ⟨ + ∣ − ∣ − ⟩ ⟨ − ∣ ) ⊗ ∣ 1 ⟩ ⟨ 1 ∣ = I ⊗ ∣ 0 ⟩ ⟨ 0 ∣ + X ⊗ ∣ 1 ⟩ ⟨ 1 ∣ . \big(\lvert+\rangle\langle+\rvert+\lvert-\rangle\langle-\rvert\big)\otimes\lvert0\rangle\langle0\rvert+\big(\lvert+\rangle\langle+\rvert-\lvert-\rangle\langle-\rvert\big)\otimes\lvert1\rangle\langle1\rvert
=I\otimes\lvert0\rangle\langle0\rvert+X\otimes\lvert1\rangle\langle1\rvert . ( ∣ + ⟩ ⟨ + ∣ + ∣ − ⟩ ⟨ − ∣ ) ⊗ ∣ 0 ⟩ ⟨ 0 ∣ + ( ∣ + ⟩ ⟨ + ∣ − ∣ − ⟩ ⟨ − ∣ ) ⊗ ∣ 1 ⟩ ⟨ 1 ∣ = I ⊗ ∣ 0 ⟩ ⟨ 0 ∣ + X ⊗ ∣ 1 ⟩ ⟨ 1 ∣ . 3 認出方向相反的 CNOT
這正是 Λ 1 2 → 1 ( X ) = C N O T 2 → 1 \Lambda^{2\to1}_1(X)=\mathrm{CNOT}_{2\to1} Λ 1 2 → 1 ( X ) = CNOT 2 → 1 。
∎ 看下一步 (2/3) 全部展開
練習 9.2.18
(利用受控相位命題,以兩個 CNOT 寫出 C Z = diag ( 1 , 1 , 1 , − 1 ) \mathrm{CZ}=\operatorname{diag}(1,1,1,-1) CZ = diag ( 1 , 1 , 1 , − 1 ) ,並在四個基態上驗證。)
基礎
解答 (2) 1 把受控相位公式取 φ = π \varphi=\pi φ = π
取 φ = π \varphi=\pi φ = π ,則
C Z = ( S ⊗ S ) C N O T 1 → 2 ( I ⊗ S † ) C N O T 1 → 2 . \mathrm{CZ}=(S\otimes S)\,\mathrm{CNOT}_{1\to2}\,(I\otimes S^\dagger)\,\mathrm{CNOT}_{1\to2}. CZ = ( S ⊗ S ) CNOT 1 → 2 ( I ⊗ S † ) CNOT 1 → 2 . 2 檢查四個基態
∣ a b ⟩ \lvert ab\rangle ∣ ab ⟩ 上的因子為 i a i b ( − i ) a ⊕ b i^{a}\,i^{b}\,(-i)^{a\oplus b} i a i b ( − i ) a ⊕ b :
∣ 00 ⟩ \lvert00\rangle ∣ 00 ⟩ :1 1 1 ;
∣ 01 ⟩ \lvert01\rangle ∣ 01 ⟩ :i ⋅ ( − i ) = 1 i\cdot(-i)=1 i ⋅ ( − i ) = 1 ;
∣ 10 ⟩ \lvert10\rangle ∣ 10 ⟩ :i ⋅ ( − i ) = 1 i\cdot(-i)=1 i ⋅ ( − i ) = 1 ;
∣ 11 ⟩ \lvert11\rangle ∣ 11 ⟩ :i ⋅ i ⋅ 1 = − 1 i\cdot i\cdot1=-1 i ⋅ i ⋅ 1 = − 1 。
看下一步 (2/2) 全部展開
練習 9.2.19
(對任意 M ∈ U ( 2 ) M\in U(2) M ∈ U ( 2 ) ,使用一個重新標記的 CNOT 和一個受控門來實現 T 01 , 10 ( M ) T_{01,10}(M) T 01 , 10 ( M ) ,並驗證四個基態的輸出。然後說明 T 10 , 01 ( M ) T_{10,01}(M) T 10 , 01 ( M ) 有甚麼不同。)
綜合
解答 (3) 1 用一個 CNOT 移動端點
用 Q = C N O T 1 → 2 Q=\mathrm{CNOT}_{1\to2} Q = CNOT 1 → 2 把 y = 10 y=10 y = 10 移至 z = 11 z=11 z = 11 。這個 Q Q Q 固定 01 01 01 ,並使 11 ↦ 10 11\mapsto10 11 ↦ 10 。由共軛引理,
T 01 , 10 ( M ) = Q T 01 , 11 ( M ) Q . T_{01,10}(M)=Q\,T_{01,11}(M)\,Q . T 01 , 10 ( M ) = Q T 01 , 11 ( M ) Q . 2 追蹤四個基態輸入
標籤 01 01 01 和 11 11 11 只在量子比特 1 不同,量子比特 2 均為 1 1 1 ,而 01 01 01 的量子比特 1 為 0 0 0 。因此相鄰對引理給出 T 01 , 11 ( M ) = Λ 1 2 → 1 ( M ) T_{01,11}(M)=\Lambda^{2\to1}_1(M) T 01 , 11 ( M ) = Λ 1 2 → 1 ( M ) 。逐一追蹤基態輸入:
∣ 01 ⟩ → Q ∣ 01 ⟩ → Λ m 11 ∣ 01 ⟩ + m 21 ∣ 11 ⟩ → Q m 11 ∣ 01 ⟩ + m 21 ∣ 10 ⟩ \lvert01\rangle\xrightarrow{Q}\lvert01\rangle\xrightarrow{\Lambda}m_{11}\lvert01\rangle+m_{21}\lvert11\rangle\xrightarrow{Q}m_{11}\lvert01\rangle+m_{21}\lvert10\rangle ∣ 01 ⟩ Q ∣ 01 ⟩ Λ m 11 ∣ 01 ⟩ + m 21 ∣ 11 ⟩ Q m 11 ∣ 01 ⟩ + m 21 ∣ 10 ⟩ ;
∣ 10 ⟩ → Q ∣ 11 ⟩ → Λ m 12 ∣ 01 ⟩ + m 22 ∣ 11 ⟩ → Q m 12 ∣ 01 ⟩ + m 22 ∣ 10 ⟩ \lvert10\rangle\xrightarrow{Q}\lvert11\rangle\xrightarrow{\Lambda}m_{12}\lvert01\rangle+m_{22}\lvert11\rangle\xrightarrow{Q}m_{12}\lvert01\rangle+m_{22}\lvert10\rangle ∣ 10 ⟩ Q ∣ 11 ⟩ Λ m 12 ∣ 01 ⟩ + m 22 ∣ 11 ⟩ Q m 12 ∣ 01 ⟩ + m 22 ∣ 10 ⟩ ;
∣ 00 ⟩ → Q ∣ 00 ⟩ → Λ ∣ 00 ⟩ → Q ∣ 00 ⟩ \lvert00\rangle\xrightarrow{Q}\lvert00\rangle\xrightarrow{\Lambda}\lvert00\rangle\xrightarrow{Q}\lvert00\rangle ∣ 00 ⟩ Q ∣ 00 ⟩ Λ ∣ 00 ⟩ Q ∣ 00 ⟩ ,因為量子比特 2 為 0 0 0 ;
∣ 11 ⟩ → Q ∣ 10 ⟩ → Λ ∣ 10 ⟩ → Q ∣ 11 ⟩ \lvert11\rangle\xrightarrow{Q}\lvert10\rangle\xrightarrow{\Lambda}\lvert10\rangle\xrightarrow{Q}\lvert11\rangle ∣ 11 ⟩ Q ∣ 10 ⟩ Λ ∣ 10 ⟩ Q ∣ 11 ⟩ 。
這些結果符合 T 01 , 10 ( M ) T_{01,10}(M) T 01 , 10 ( M ) 的定義。
3 調換有序對的次序
對 T 10 , 01 ( M ) = T 01 , 10 ( X M X ) T_{10,01}(M)=T_{01,10}(XMX) T 10 , 01 ( M ) = T 01 , 10 ( X M X ) ,同一電路仍適用,只需把中間的門換成 Λ 1 2 → 1 ( X M X ) \Lambda^{2\to1}_1(XMX) Λ 1 2 → 1 ( X M X ) 。等價地,也可把端點 10 10 10 移到 11 11 11 ,並把 11 11 11 視作配對 ( 11 , 01 ) (11,01) ( 11 , 01 ) 的第一個標籤。由於 11 11 11 的目標比特是 1 1 1 ,相鄰對引理同樣要求使用 X M X XMX X M X 。
看下一步 (2/3) 全部展開
練習 9.2.20
(計算 Λ 1 1 → 2 ( e i χ I ) \Lambda^{1\to2}_1(e^{i\chi}I) Λ 1 1 → 2 ( e i χ I ) 。哪些 χ \chi χ 使它等於 I ⊗ I I\otimes I I ⊗ I ?)
基礎
解答 (2) 1 計算受控純量
Λ 1 1 → 2 ( e i χ I ) = diag ( 1 , 1 , e i χ , e i χ ) = P ( χ ) ⊗ I . \Lambda^{1\to2}_1(e^{i\chi}I)=\operatorname{diag}(1,1,e^{i\chi},e^{i\chi})=P(\chi)\otimes I . Λ 1 1 → 2 ( e i χ I ) = diag ( 1 , 1 , e i χ , e i χ ) = P ( χ ) ⊗ I . 2 判斷何時為恆等算子
當且僅當 e i χ = 1 e^{i\chi}=1 e i χ = 1 時,它等於 I ⊗ I I\otimes I I ⊗ I 。對其他任何 χ \chi χ ,目標上的純量都變成控制位上的非平凡相位門。這正是受控 U 定理中控制量子比特上的門所起的作用。
看下一步 (2/2) 全部展開
練習 9.2.21
(利用受控 U 定理,以兩個 CNOT 合成 Λ 1 1 → 2 ( X ) \Lambda^{1\to2}_1(X) Λ 1 1 → 2 ( X ) ,即一個 CNOT。確認即使在這個刻意繞遠的例子中,公式仍然一致。)
核心
解答 (3) 1 選取 V V V 、α \alpha α 和 β \beta β
由 X = H diag ( 1 , − 1 ) H † X=H\operatorname{diag}(1,-1)H^\dagger X = H diag ( 1 , − 1 ) H † ,可取 V = H V=H V = H 、α = 0 \alpha=0 α = 0 、β = π \beta=\pi β = π 。受控 U 定理給出
Λ 1 1 → 2 ( X ) = ( S ⊗ H S ) C N O T 1 → 2 ( I ⊗ S † ) C N O T 1 → 2 ( I ⊗ H ) . \Lambda^{1\to2}_1(X)=\big(S\otimes HS\big)\,\mathrm{CNOT}_{1\to2}\,\big(I\otimes S^\dagger\big)\,\mathrm{CNOT}_{1\to2}\,\big(I\otimes H\big). Λ 1 1 → 2 ( X ) = ( S ⊗ H S ) CNOT 1 → 2 ( I ⊗ S † ) CNOT 1 → 2 ( I ⊗ H ) . 2 檢查控制位為 0 0 0 的分支
控制位為 0 0 0 。 量子比特 2 受到 H S S † H = I HSS^\dagger H=I H S S † H = I 的作用。
3 檢查控制位為 1 1 1 的分支
控制位為 1 1 1 。 量子比特 1 上的相位門提供 e i π / 2 = i e^{i\pi/2}=i e iπ /2 = i ,量子比特 2 則受到 H S X S † X H HS\,XS^\dagger X\,H H S X S † X H 的作用。由於 X S † X = diag ( − i , 1 ) = − i S XS^\dagger X=\operatorname{diag}(-i,1)=-iS X S † X = diag ( − i , 1 ) = − i S ,後者等於
H S ( − i S ) H = − i H Z H = − i X . HS(-iS)H=-iHZH=-iX . H S ( − i S ) H = − i H Z H = − i X . 控制位為 1 1 1 的分支上,總作用是 i ⋅ ( − i X ) = X i\cdot(-iX)=X i ⋅ ( − i X ) = X ,所以公式精確成立。這個構造顯然浪費,也說明我們沒有聲稱它是最優的。
看下一步 (2/3) 全部展開
練習 9.2.22
(普適性定理的一個電路有 39 39 39 個單量子比特門。每個都被一個 { H , T } \{H,T\} { H , T } 字取代,後者與該門相差某個相位後的算子範數距離至多為 10 − 4 10^{-4} 1 0 − 4 。求所得電路的誤差上界,以及任一結果概率的變化上界。)
基礎
解答 (2) 1 用望遠鏡和界定電路誤差
由望遠鏡引理和相位的說明,
∥ U ~ − e i χ U ∥ ≤ 39 ⋅ 10 − 4 = 3.9 × 10 − 3 . \lVert\tilde U-e^{i\chi}U\rVert\le39\cdot10^{-4}=3.9\times10^{-3}. ∥ U ~ − e i χ U ∥ ≤ 39 ⋅ 1 0 − 4 = 3.9 × 1 0 − 3 . 2 界定測量結果的概率變化
由測量界,每個結果的概率最多改變 2 ⋅ 3.9 × 10 − 3 = 7.8 × 10 − 3 2\cdot3.9\times10^{-3}=7.8\times10^{-3} 2 ⋅ 3.9 × 1 0 − 3 = 7.8 × 1 0 − 3 。僅由稠密性得不到這些字的長度上界。
看下一步 (2/2) 全部展開
相關筆記和先備知識
單量子比特門與 { H , T } \{H,T\} { H , T } 的稠密性 (配套筆記)。本筆記使用其稠密性結果,以及其對 Solovay–Kitaev 定理的陳述,而非證明。
先備知識。 線性代數:酉矩陣、正規矩陣的譜定理、算子範數和張量積。
參考文獻
A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, "Elementary gates for quantum computation," Physical Review A 52 , 3457 (1995). arXiv:quant-ph/9503016 . 引用此文是為了提供歷史背景及上面陳述的 n n n 量子比特定理。