---
# System prepended metadata

title: 06 重試經典計算
tags: [量子演算法（上）, 基礎教學文章]

---

# 重視經典計算

量子計算看似複雜，但我們能夠過線性代數這樣的數學工具來簡化並讓我們直觀地瞭解它。為了更好地幫助初學者從經典計算過渡到量子計算，我們將用[線性代數入門](https://www.entangletech.tw/courses/linear-algebra)系列所學的數學計巧重新描述經典計算。

## Bit
雖然通常不會這樣做，但我們可以用 [Dirac 表示法](https://www.entangletech.tw/lesson/math-02) 描述 Bit 的狀態。當 Bit 為 0 時（無電流），我們可以用符號 $|0\rangle$ 表示；當 bit 為 1 （有電流），則表示為 $|1\rangle$：

\begin{split}
|0\rangle \qquad |1\rangle
\end{split}

這兩種狀態也能用矩陣的形式來描述：

\begin{split}
|0\rangle=
\begin{bmatrix}
1\\
0
\end{bmatrix}
\qquad
|1\rangle=
\begin{bmatrix}
0\\
1
\end{bmatrix}
\end{split}

如果今天有兩個 bit 都是 $1$，則可以表示為：

\begin{split}
&|1\rangle\otimes|1\rangle \quad \text{或}\\ 
&|1\rangle|1\rangle \quad \text{或}  \\
&|11\rangle
\end{split}

在二進位表示法中，$|11\rangle$ 就是數字 3，類似地，[78 的二進位表示](https://www.entangletech.tw/lesson/basic-algorithm-02)是：

\begin{split}
|78\rangle=|1001110\rangle
\end{split}

## 機率
在[入門系列](https://www.entangletech.tw/lesson/popular-03)提過，在量子的世界中，所有事情都只能用機率表示，一樣雖然通常我們不會這樣做，但我們可以用機率的方式描述經典計算。一個 bit 當下的狀態可以這樣描述

\begin{split}
\alpha|0\rangle+\beta|1\rangle=
\begin{bmatrix}
\alpha\\
\beta
\end{bmatrix}
\end{split}

其中，$\alpha$ 與 $\beta$ 是機率幅（probability amplitudes），其平方代表在測量後看到系統處於該狀態的機率。在經典計算中，bit 只會有兩種狀態：

\begin{split}
1|0\rangle+0|1\rangle=|0\rangle\\
0|0\rangle+1|1\rangle=|1\rangle
\end{split}

以第一條式子來說，意味著我們有 100%（$1^2$）的機率觀測到 bit 是 $|0\rangle$ 狀態，有 0% 的機率會看到 $|1\rangle$。所有可能狀態的機率總和起來一定會是 1（100%）：

\begin{split}
|\alpha|^2+|\beta|^2=1
\end{split}

## 邏輯閘
我們也可以用矩陣來描述邏輯閘，例如，是在前面提到的 [NOT gate](https://www.entangletech.tw/lesson/basic-algorithm-03)

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

改用矩陣描述：

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

當我們將 $|0\rangle$ 輸入 NOT gate 後會輸出 1，運算的過程可以用矩陣相乘來表示：

\begin{split}
\text{NOT}|0\rangle&=
\begin{bmatrix}
0 & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
1 \\
0 
\end{bmatrix}\\
&=
\begin{bmatrix}
0 \\
1 
\end{bmatrix} \\
&=|1\rangle
\end{split}

對於像 AND gate 這種有兩個以上的輸入，我們要用到在線性代數系列學到的 [tensor product](https://www.entangletech.tw/lesson/math-06)，將兩個 bit 的資訊濃縮成一個矩陣上，即：

\begin{split}
|11\rangle&=|1\rangle\otimes|1\rangle\\
&=
\begin{bmatrix}
0 \\
1
\end{bmatrix}
\otimes
\begin{bmatrix}
0 \\
1
\end{bmatrix}
=\begin{bmatrix}
0 
\begin{bmatrix}
0 \\
1
\end{bmatrix}\\
1
\begin{bmatrix}
0 \\
1
\end{bmatrix}
\end{bmatrix} \\
&=\begin{bmatrix}
0 \\
0 \\
0 \\
1
\end{bmatrix}
\end{split}

接下來，我們可以用矩陣描述 AND gate 的行為：

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

當輸入都是 1 時，AND 給出來的結果會是 1。

## 邏輯閘電路
<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>

同樣的，我們能用矩陣描述一個邏輯閘電路，把每個邏輯閘做 tensor product 就能得出，由於篇幅限制，想知道詳細推導的讀者可以看這篇[文章](https://ozaner.github.io/boolean-logic-with-matrices/)。因此一個半加法器的矩陣為：

\begin{split}
\text{Half-Adder}= 
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 
\end{bmatrix}
\end{split}

平常我們都是用布林運算描述經典計算，在這節中我們改以 Dirac 表示法與矩陣描述 bit 與邏輯閘操作，下一節我們將用同樣的數學工具，描述量子計算如何運作。
