引言
普适门集 是一小组基本操作;借助它们,可以精确地或以任意精度构造任何量子计算。本文自洽地讲解其中一个基础问题。
配套的单量子比特文章证明了门 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 将 A A A 作用于量子比特 1,将 B B B 作用于量子比特 2。它的矩阵是 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 ⟩ 时,将 W W W 作用于量子比特 t t t ;
当量子比特 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 交换控制位的两个值:在整个操作之前的“控制值 = 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 :此时目标元素已经为零,无须操作。特别地,整个过程中都不会除以零,也无需在两能级操作之外交换行。
消元定理
将 4 × 4 4\times4 4 × 4 矩阵的行和列编号为 0 , 1 , 2 , 3 0,1,2,3 0 , 1 , 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). ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 3 ) .
对于有序对 ( k , j ) (k,j) ( k , j ) ,其中 k < j k\lt 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 ,其中 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 ) ,( k i , j i ) (k_i,j_i) ( k i , j i ) 是上述顺序中的第 i i 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 ) 。在第 i i i 步,设 ( k , j ) = ( k i , j i ) (k,j)=(k_i,j_i) ( k , j ) = ( k i , j 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\text{ 行}=m_{11}\,(\text{第 }k\text{ 行})+m_{12}\,(\text{第 }j\text{ 行}),\qquad
\text{新第 }j\text{ 行}=m_{21}\,(\text{第 }k\text{ 行})+m_{22}\,(\text{第 }j\text{ 行}). 新第 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 ′ 列先前已经全部处理完毕,该列在第 k k k 和 j j j 行的两个元素均已为 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 ,且第 ℓ \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\text{ 列}\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 行 ) = ( 0 , 0 , − 1 , 0 ) -(\text{第 }1\text{ 行})=(0,0,-1,0) − ( 第 1 行 ) = ( 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 ⟩) 将 W W W 作用于量子比特 t t t 。若 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 时将 R R R 作用于量子比特 2。具体地,
∣ 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 . 对角因子。 由对角构造命题综合 D D D ,使用 2 2 2 个 CNOT 和 3 3 3 个单量子比特门。
两能级因子。 按前表实现每个 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 ,对其余三个标号作用为三轮换 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 是一般的模为一的对角矩阵,并不是 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 判断何时为恒等算子
它等于 I ⊗ I I\otimes I I ⊗ I 当且仅当 e i χ = 1 e^{i\chi}=1 e i χ = 1 。对于其他 χ \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 量子比特定理。