經典邏輯閘（下）：邏輯閘的特性 | EntangleTech 量子教育平台

# 經典邏輯閘（下）在上一節中，我們介紹了 7 種常用的邏輯閘。在這節，我們將探討經典邏輯閘的特性，這些特性與量子計算相關，理解這些特性能幫助我們更好地了解經典計算與量子計算的差異。 ## Universal gates（通用邏輯閘）如果只用其中幾個邏輯閘就能組合出所有的邏輯閘，我們稱這些邏輯閘囗 universal gate set（通用邏輯閘集合），以下介紹常見的 universal gate set。 {NOT, AND, OR} 這組是 universal gate set，任何邏輯閘電路都能只用這三種邏輯閘表示。那有沒有更簡單的，當然有，{NOT, AND} 用兩個 gate 就能組和上一節我們介紹的所有 gate，可以自己在紙上透過 NOT 與 AND 拼湊出其他 gate。當然，還有更簡單的：{NAND}，單用 NAND gate 就能組合出所有的 gate，換言而之，任何數位電路上面滿滿各種 gate，都能轉成只有 NAND 組合的電路。在上一節中我們提到 half adder：

半加法器的電路圖

它能簡單地只用 NAND gate 表達

半加法器的電路圖

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

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

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

NOT gate 的電路圖

\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

AND gate 的電路圖

\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 越多，那這晶片的熱耗會越高，能量使用效率很低。

這邊指的是理論上，實際上會更複雜

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

Toffoli gate 的電路圖

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）

CNOT gate 的電路圖

當 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}

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

到介紹量子邏輯閘的時候，會再遇到 CNOT 與 Toffoli gate

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