# 量子邏輯閘：多 Qubits 操作
本節將介紹在量子計算中常見的多 qubits 量子邏輯閘，這些邏輯閘可以同時操作多個 qubits。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/S1wVMdu3A.svg" alt="two qubit quantum gate" width="70%"/>
<br>第一條橫線代表第一個 qubit（通常標記為 q0），第二條橫線代表第二個 qubit（通常標記為 q1），經過中間 gate 操作後，兩個 qubit 的狀態可能會改變
<p>
</p>
</div>

在介紹量子邏輯閘之前，讓我們先複習如何用一個矩陣表示兩個 qubits 的量子態：

\begin{split}
|00\rangle=
\begin{bmatrix}
1 \\
0 \\
0 \\
0
\end{bmatrix}\quad
|01\rangle=
\begin{bmatrix}
0 \\
1 \\
0 \\
0
\end{bmatrix}\quad
|10\rangle=
\begin{bmatrix}
0 \\
0 \\
1 \\
0
\end{bmatrix} \quad
|11\rangle=
\begin{bmatrix}
0 \\
0 \\
0 \\
1
\end{bmatrix}
\end{split}

## Controlled-U gate
Controlled-U gate （CU gate）的標準架構如下圖所示，圓圈黑點所在的 qubit 稱為 "controlled qubit"，另一個標示為 U 的 qubit 稱為 "target qubit"。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/S1ELzdu3A.svg" alt="CU gate" width="30%"/>
<br>CU gate 的符號
<p>
</p>
</div>

當 controlled qubit 為 $|0\rangle$ 時，什麼操作都不做；當為 $|1\rangle$ 時，對 target qubit 執行 U 操作。這邊的 U 可以是 X, Y, Z, RX, RY, 或 RZ gate。

CU gate 的矩陣都會長成這樣的形式：

\begin{split}
CU=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & a & b \\
0 & 0 & c & d \\
\end{bmatrix} \qquad \text{其中} \quad
U =
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix}
\end{split}

例如： CX gate 是一種常見的 CU gate，我們知道 X gate 的矩陣是

\begin{split}
X =
\begin{bmatrix}
0 & 1 \\
1 & 0
\end{bmatrix}
\end{split}

那麼， CX gate 的矩陣就是：

\begin{split}
CX=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}
\end{split}

只有當 controlled qubit 為 $|1\rangle$ 時，CX 才會對 targe qubit 執行 X gate 操作。以下我們介紹幾種常見的 CU gate：

### CNOT gate
又稱作 controlled-NOT gate，是最常見的 CU gate 之一，就是上面舉例的 CX gate。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/Sy6yX_u2C.svg" alt="CX gate" width="30%"/>
<br>CNOT (CX) gate 的符號
<p>
</p>
</div>

CNOT 對 qubit 的操作如下表格所示，A 代表第一個 qubit（controlled qubit），B 代表第二個 qubit（target qubit）：

\begin{array}{|c|c|}
\hline
\text{Input} & \text{Output} \\
\hline
A\quad B & A \quad B \\
\hline
0\quad 0 & 0\quad 0 \\
\hline
0\quad 1 & 0\quad 1 \\
\hline
1\quad 0 & 1\quad 1\\
\hline
1\quad 1 & 1\quad 0\\
\hline
\end{array}

從表格中可以看出，只有當 A 為 $|1\rangle$ 時，CNOT 才會對 B 執行 X gate 操作。

以古典邏輯閘做比擬，CNOT 就是量子版的 XOR gate，即：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/SkJPXu_2C.svg" alt="classic AND" width="60%"/>
<br>用經典邏輯閘構建如 CNOT gate 的電路
<p>
</p>
</div>

如果今天 CNOT 施加在兩個處於疊加態的 qubits：

\begin{split}
\text{CNOT}|Q_0Q_1\rangle&=\text{CNOT} (c_0|00\rangle+c_1|01\rangle+c_2|10\rangle+c_3|11\rangle) \\
&=c_0\text{CNOT}|00\rangle + c_1 \text{CNOT}|01\rangle+c_2 \text{CNOT}|10\rangle +c_3\text{CNOT}|11\rangle \\
&=c_0|00\rangle+c_1|01\rangle+c_2|11\rangle+c_3|10\rangle \\
&=c_0|00\rangle+c_1|01\rangle+c_3|10\rangle+c_2|11\rangle
\end{split}

可以看到 $|01\rangle$ 與 $|11\rangle$ 的機率幅交換了。以矩陣表示 CNOT gate 的話：

\begin{split}
CNOT=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}
\end{split}

來算算看 CNOT 施加在量子態 $|11\rangle$ 上

\begin{split}
\text{CNOT}|11\rangle=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
0 \\
0 \\
0 \\
1
\end{bmatrix}=
\begin{bmatrix}
0 \\
0 \\
1 \\
0
\end{bmatrix}=
|10\rangle
\end{split}

CNOT gate 也可以這樣表達

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/By_hm_u2A.svg" alt="classic AND" width="60%"/>
<br>
<p>
</p>
</div>

<blockquote>
圖中右邊這張圖，稱作電路，會在本系列最後一篇文章中介紹如何解讀電路圖。電路同的看法是從左邊開始，所以在這圖中，兩個 qubit 先做 H gate，再做 CNOT，最後再做 H gate 操作
</blockquote>

### CZ gate
CZ gate 是 Controlled-Z gate，當 controlled qubit 是 $|1\rangle$ 時，對 target qubit 執行 Z gate 操作。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BJZl4OO2C.svg" alt="CZ gate" width="60%"/>
<br>CZ gate 的符號，最常見的符號是左邊的
<p>
</p>
</div>

同理，我們從前面章節得知 Z gate 的矩陣是
\begin{split}
Z=
\begin{bmatrix}
0 & -i \\
i & 0
\end{bmatrix}
\end{split}

因此 CZ gate 的矩陣是

\begin{split}
CZ=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & -1
\end{bmatrix}
\end{split}

有趣的是，下面這兩種 gate 是等價的

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BJFfvO_nR.svg" alt="CZ gate" width="60%"/>
<br>這兩種 gate 對 qubit 的狀態改變是一樣的
<p>
</p>
</div>

讓我們做證明，左邊的 CZ，controlled 是第一個 qubit，target 是第二個 qubit，所以我們記做 $CZ_{01}$

\begin{split}
CZ_{01}|Q_0Q_1\rangle&=CZ(c_0|00\rangle+c_1|01\rangle+c_2|10\rangle+c_3|11\rangle) \\
&=c_0|00\rangle+c_1|01\rangle+c_2|10\rangle-c_3|11\rangle
\end{split}

右邊的 CZ gate，同理，記做 $CZ_{10}$

\begin{split}
CZ_{10}|Q_0Q_1\rangle&=CZ(c_0|00\rangle+c_1|01\rangle+c_2|10\rangle+c_3|11\rangle) \\
&=c_0|00\rangle+c_1|01\rangle+c_2|10\rangle-c_3|10\rangle
\end{split}

兩個的結果是一樣。

### Toffoli gate
又稱為 CCNOT gate。CCNOT 是同時操作 3 個 qubits 的 gate，有兩個 controlled qubit 和一個 target qubit。只有在兩個 controlled qubit 都是 $|1\rangle$ 時，才會對 target gate 執行 X gate。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/rJLc4__nC.svg" alt="CCNOT gate" width="25%"/>
<br>Toffoli (CCNOT) gate 的符號
<p>
</p>
</div>

因為涉及 3 個 qubits，Toffoli 需要用 $8\times8$ 的矩陣做表達

\begin{split}
CCNOT=
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
\end{bmatrix}
\end{split}

Toffoli gate 相當於量子版的 AND gate，因為

\begin{split}
\text{CCNOT}&|110\rangle=|111\rangle \\
\text{CCNOT}&|111\rangle=|110\rangle \\
\text{CCNOT}&|ABC\rangle=|AB\rangle|A\oplus B\rangle
\end{split}

### Fredkin gate
又稱作 CSWAP，一樣涉及到 3 個 qubits，有一個 controlled 與兩個 target qubit。當 controlled qubit 是 $|1\rangle$ 時，對兩個 target qubit 執行 SWAP gate（我們會在下面說明何謂 SWAP gate）。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/B1L8Z1IYkg.svg" alt="CSWAP gate" width="25%"/>
<br>Fredkin (CSWAP) gate 的符號
<p>
</p>
</div>

CSWAP gate 的矩陣表示如下：

\begin{split}
SWAP=
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{bmatrix}
\end{split}

CSWAP gate 可以用三個 Toffoli gate 組合出來：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/rk64HudnC.svg" alt="CSWAP gate" width="60%"/>
<br>可以用三個 CCNOT 組合出 Toffoli gate
<p>
</p>
</div>

## SWAP gate

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/Sy_PBu_nR.svg" alt="SWAP gate" width="40%"/>
<br>SWAP gate 的符號
<p>
</p>
</div>

SWAP gate 的作用是交換兩個 qubits 的量子態，即：

\begin{split}
\text{SWAP}|00\rangle=|00\rangle \\
\text{SWAP}|01\rangle=|10\rangle \\
\text{SWAP}|10\rangle=|01\rangle \\
\text{SWAP}|11\rangle=|11\rangle
\end{split}

其矩陣表示為：

\begin{split}
SWAP=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
\end{split}

SWAP gate 可以用三個 CNOT gate 組合出來

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/S1M5BdO2A.svg" alt="SWAP gate" width="60%"/>
<br>SWAP gate 可以用三個 CNOT gate 組合出來。為了後面解釋方便，
<p>
</p>
</div>

可以用矩陣相成來證明

\begin{split}
CNOT_{10}CNOT_{01}CNOT_{10}&=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix} \\
&=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}\\
&=SWAP
\end{split}

<blockquote>
假設電路圖上，由左至右，qubit 做了 A, B, 與 C gate 操作，寫成矩陣相乘時要寫成 CBA，B 與 A 先相乘，再與 C 相乘
</blockquote>

## 其他量子邏輯閘組合
前面提及如何使用 tensor product 將多個 qubits 的量子態表示為一個矩陣，同樣地，我們也能用 tensor product 將多個 quantum gate 以一個矩陣表示。以下是一些範例：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/B1xEUduhR.svg" alt="HI gate" width="30%"/>
<br>
<p>
</p>
</div>

第一個 qubit 做 H gate 操作，第二個 qubit 什麼都不動，如果要用一個矩陣描述，就得用 tensor product 將 H gate 與 I gate 併在一起

\begin{split}
H\otimes I=\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 1\\
1 & -1
\end{bmatrix}
\begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}=
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1 \\
\end{bmatrix}
\end{split}

<blockquote>
同一條線上的 quantum gate 可透過矩陣相乘來組合成一個矩陣；對於不同線上的量子閘，則必須使用 tensor product 組合成一個矩陣。以前面提及用 H gate 和 CNOT 結合成 CNOT gate 的範例圖為例，最初和最後的兩個 H gate 因在不同的線上，所以它們的矩陣需透過張量積組合成一個我們先稱作 HH 的單一矩陣，接著 HH、CNOT 和最後的 HH 都是 two qubit gate，因此可以透過矩陣相乘將它們組合成單一矩陣。
</blockquote>

做個簡單的驗證，假設這兩個 qubits 的初始狀態都是 $|0\rangle$，那麼：

\begin{split}
(H\otimes I)|00\rangle &=\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1 \\
\end{bmatrix}
\begin{bmatrix}
1 \\
0 \\
0 \\
0
\end{bmatrix}=\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 \\
0 \\
1 \\
0
\end{bmatrix} \\
&=\frac{1}{\sqrt{2}} (
\begin{bmatrix}
1 \\
0 \\
0 \\
0
\end{bmatrix} +
\begin{bmatrix}
0 \\
0 \\
1 \\
0
\end{bmatrix} ) \\
&=\frac{1}{\sqrt{2}} (|00\rangle+|10\rangle) \\
&=\frac{1}{\sqrt{2}} (|0\rangle+|1\rangle)|0\rangle
\end{split}

與實際結果相同。

### 多個 H gate 組合

同樣地，當有 2 個 qubits 都執行 H gate 操作時

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/Sy_LIdO3R.svg" alt="HH gate" width="30%"/>
<br>
<p>
</p>
</div>

我們也可以用 tensor product 將兩個 H gate 矩陣以一個矩陣做表示，即

\begin{split}
H\otimes H=H^{\otimes 2}&= \frac{1}{2}
\begin{bmatrix}
1 & 1 & 1 & 1\\
1 & -1 & 1 & -1\\
1 & 1 & -1 & -1\\
1 & -1 & -1 & 1
\end{bmatrix}
\end{split}

如果兩個 qubits 的初始狀態都是 $|0\rangle$，則為

\begin{split}
H^{\otimes 2}|00\rangle&=H|0\rangle\otimes H|0\rangle \\
&=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\otimes\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \\
&=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)
\end{split}

當有 3 個 qubits 都執行 H gate 操作時，可以進一步使用 tensor product 將 $H^{\otimes 2}$ 與 $H$ 組合；然而，當 qubits 數越來越大，勢必這矩陣會越來越大，越來越難在紙上算出來，有沒有什麼通式呢？這就要用到之前提到 H gate 的 Dirac 表示法：

\begin{split}
H=\frac{1}{\sqrt 2} \sum_{x,y\in \left\{ 0,1 \right\}} (-1)^{x\cdot y}|x\rangle\langle y|
\end{split}

<div style="background-color: #E0E0E0; color: #333; padding: 15px; font-style: italic; border-radius: 5px;">
這裡的 $x$ 和 $y$ 都是 0 與 1
</div>

今天有 $n$ 個 qubits 都做 H gate 操作，就要把 $n$ 個上式做 tensor product，即：

\begin{split}
H^{\otimes n}&=
\frac{1}{\sqrt 2} \sum_{x_1,y_1} (-1)^{x_1\cdot y_1}|x_1\rangle\langle y_1| \otimes \frac{1}{\sqrt 2} \sum_{x_2,y_2} (-1)^{x_2\cdot y_2}|x_2\rangle\langle y_2|\otimes... \otimes \frac{1}{\sqrt 2} \sum_{x_n,y_n} (-1)^{x_n\cdot y_n}|x_n\rangle\langle y_n| \\
&=\frac{1}{\sqrt{2^n}} \sum_{x,y} (-1)^{x\cdot y}|x\rangle\langle y|
\end{split}

最後一行的 $x=[x_1,x_2,...x_n]$，$y$ 也是，都是 0 或 1 這兩個數字，以 2 個 qubits （$n=2$）都做 H gate 操作為例：

\begin{split}
H^{\otimes 2}=\frac{1}{\sqrt{2^2}}[ &|00\rangle\langle 00|+|01\rangle\langle 00|+|00\rangle\langle 01|-|01\rangle\langle 01|+ \\
&|10\rangle\langle 00|+|11\rangle\langle 00|+|10\rangle\langle 01|-|11\rangle\langle 01|+\\
&|00\rangle\langle 10|+|01\rangle\langle 10|+|00\rangle\langle 11|-|01\rangle\langle 11|-\\
&|10\rangle\langle 10|-|11\rangle\langle 10|-|10\rangle\langle 11|+|11\rangle\langle 11|]\\
&=\frac{1}{2}
\begin{bmatrix}
1 & 1 & 1 & 1\\
1 & -1 & 1 & -1\\
1 & 1 & -1 & -1\\
1 & -1 & -1 & 1
\end{bmatrix}
\end{split}

如果上式看了很頭痛，其實有更簡單的表示方法：

\begin{split}
H^{\otimes n}=\frac{1}{\sqrt{2}}
\begin{bmatrix}
H^{\otimes n-1} & H^{\otimes n-1} \\
H^{\otimes n-1} & -H^{\otimes n-1}
\end{bmatrix}
\end{split}

以 $H^{\otimes 2}$ 為例，即：

\begin{split}
H^{\otimes 2}=\frac{1}{\sqrt{2}}
\begin{bmatrix}
H & H \\
H & -H
\end{bmatrix}
\end{split}