# 經典邏輯閘（下）
在上一節中，我們介紹了 7 種常用的邏輯閘。在這節，我們將探討經典邏輯閘的特性，這些特性與量子計算相關，理解這些特性能幫助我們更好地了解經典計算與量子計算的差異。

## Universal gates（通用邏輯閘）

如果只用其中幾個邏輯閘就能組合出所有的邏輯閘，我們稱這些邏輯閘為 universal gate set（通用邏輯閘集合），以下介紹常見的 universal gate set。

$\{\text{NOT}, \text{AND}, \text{OR}\}$ 這組是 universal gate set，任何邏輯閘電路都能只用這三種邏輯閘表示。那有沒有更簡單的，當然有，$\{\text{NOT}, \text{AND}\}$ 用兩個 gate 就能組和上一節我們介紹的所有 gate，可以自己在紙上透過 NOT 與 AND 拼湊出其他 gate。

當然，還有更簡單的：$\{\text{NAND}\}$，單用 NAND gate 就能組合出所有的 gate，換言而之，任何數位電路上面滿滿各種 gate，都能轉成只有 NAND 組合的電路。在上一節中我們提到 half adder：

<div style="text-align: center;">
<img src="https://upload.wikimedia.org/wikipedia/commons/d/d9/Half_Adder.svg"
alt="半加法器" width="40%"/>
<br>
<p>半加法器的電路圖
</p>
</div>

它能簡單地只用 NAND gate 表達

<div style="text-align: center;">
<img src="https://upload.wikimedia.org/wikipedia/commons/5/55/Half_adder_using_NAND_gates_only.jpg"
alt="半加法器" width="100%"/>
<br>
<p>半加法器的電路圖
</p>
</div>

您可能會好奇，為什麼要把一個簡單由兩種 gate 組成的電路，轉換成五個相同的 gate，看起來似乎更複雜，其實這樣反而簡化了問題。在紙上或電腦上畫出的電路最終需要被製造出來。雖然我們可以用相應的電晶體組合出各種邏輯閘，但如果整個電路只使用一種邏輯閘，製造過程會更簡單且成本低（使用多種不同的 gate 需要不同的製造工藝）。而且在所有邏輯閘中，NAND 的製作成本較低，且所有的 EDA tool 都支援 NAND gate，但其他類型的邏輯閘就不一定有支援。

<blockquote>
<p>在量子電腦上也是，有許多不同的量子邏輯閘供我們使用，但硬體層面不一定支援所有的 gate。因此，一台好的量子電腦至少得能做 universal gate 操作，才能用這些基本的 gate 組合出其他種 quantum gate。 </p>
</blockquote>

## Reversible gates（可逆邏輯閘）
Reversible gate 是指能單靠 gate 的輸出值就能判斷原本的輸入是什麼，比方說 NOT gate：

<div style="text-align: center;">
<img src="https://upload.wikimedia.org/wikipedia/commons/6/60/NOT_ANSI_Labelled.svg"
alt="半加法器" width="40%"/>
<br>
<p>NOT gate 的電路圖
</p>
</div>

\begin{array}{|c|c|}
\hline
\text{Input} & \text{Output} \\
\hline
A & Q=\overline{A} \\
\hline
0 & 1 \\
\hline
1 & 0 \\
\hline
\end{array}

你能輕易地從輸出值判斷原本的輸入是什麼，看到輸出是 1，那原本的輸入肯定是 0，這樣的 gate 具有 reversible 特性。

像 AND gate

<div style="text-align: center;">
<img src="https://upload.wikimedia.org/wikipedia/commons/b/b9/AND_ANSI_Labelled.svg"
alt="半加法器" width="40%"/>
<br>
<p>AND gate 的電路圖
</p>
</div>

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

當輸出是 0 時，無法單靠輸出值判斷原本的輸入是什麼。這點很重要性，如果輸入與輸出不是一對一對應（one-to-one and onto），代表中間有資訊丟失，丟失的資訊會以熱的形式從 gate 發散到環境中（Landauer's principle），導致能量消耗。因此，晶片上使用的 irreversible gate 越多，那這晶片的熱耗會越高，能量使用效率很低。

<blockquote>
<p>這邊指的是理論上，實際上會更複雜 </p>
</blockquote>

那該如何解決 AND gate 的不可逆性導致的能量浪費呢？這時候就得用一個特別的邏輯閘叫 Toffoli gate（or CCNOT gate），它是一個可逆版的 AND gate

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/ryXk7bKDA.svg"
alt="半加法器" width="90%"/>
<br>
<p>Toffoli gate 的電路圖
</p>
</div>

Toffoli gate 有三個輸入與三個輸出，中間由 AND 與 XOR 組成。下圖為其真值表，只有當 A 與 B 都是 1 時，才對 C 做 NOT 操作。

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

同樣的功能，AND gate 在操作過程中（理論上、多數情況下）會消耗 $6\times 10^{-21}$ 焦耳，而 Toffoli gate 因為是可逆的，理論上不會消耗能量。

另一種 reversible gate 稱作 controlled not gate（or CNOT gate）

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BJhbmZKvC.svg"
alt="Classic CNOT" width="90%"/>
<br>
<p>CNOT gate 的電路圖
</p>
</div>

當 A 為 1 時， 對 B 做 NOT gate 操作並輸出到 Q 端，如果 A 為 0， Q 跟 B 一樣。

\begin{array}{|c|c|}
\hline
\text{Input} & \text{Output} \\
\hline
A\quad B & A\quad Q \\
\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}

<blockquote>
<p>在量子電腦中，所有的 quantum gate 都是可逆，因此量子電腦可以在沒有能量消耗的情況下做計算 </p>
</blockquote>

<blockquote>
<p>到介紹量子邏輯閘的時候，會再遇到 CNOT 與 Toffoli gate </p>
</blockquote>

這節我們介紹了通用邏輯閘集合和可逆邏輯閘的概念，這些概念對理解量子計算非常重要。在進到量子計算前，我們還得先介紹何謂演算法複雜度。