進入量子演算法了。
越來越複雜，勉強能跟上。

前言

證明部分看情況再補上

有錯再麻煩指正。

Boolean satisfiability problem

布林可滿足性問題，可簡稱為 SAT ¹。給定一個邏輯電路，求是否存在一種輸入使得該電路輸出為真 (True, 1)。

舉例: $F(x_1, x_2) = (x_1\lor x_2)\land (\lnot x_1 \lor \lnot x_2) \land (x_1)$, where $x_1, x_2 \in \{0, 1\}$，
透過演算法可得 $x_1 = 1, x_2 = 0$ 時 $F(x_1, x_2) = 1$。求存在的其中一組解即可。

Complexity

SAT 問題屬於 NP-Complete ²，一般解法的複雜度需要花費到指數時間 $O(2^n)$。

簡單釐清一下 P、NP、NP-Complete、NP-Hard 之間的關係:

P: 能以多項式時間演算法計算答案的問題之集合
NP: 能以指數時間演算法計算答案，且能以多項式時間演算法驗證答案的問題之集合。P 也可以用指數時間演算法求解，因此 P $\subset$ NP。
NP-Complete: NP 中最難問題的集合，若其中一個問題存在多項式時間的解法的話，則此集合所有問題都可用多項式解決。NP-Complete $\subset$ NP。
NP-Hard: 難度至少為 NP，代表可能比 NP-Complete 還難 (例如，Halting problem ³)。NP-Complete $\subset$ NP-Hard。

若 P = NP 則 P = NP = NP-Complete $\subset$ NP-Hard。

Quantum Solution for SAT

Goal

使用量子特性 (Grover’s algorithm ⁴) 對解決 SAT 達到平方加速: $O(2^{\frac{n}{2}}) = O(\sqrt{2^n})$

Simple example

$F(x_1, x_2) = x_1 \land x_2$, where $x_1, x_2 \in \{0, 1\}$

Setup

q[0]: auxiliary working bit
q[1]: unused
q[2]: auxiliary Boolean variable, $s_2$
q[3]: $x_0$
q[4]: $x_1$

一開始會先將兩個輸入位元進行疊加，所以 q[3], q[4] 都會先使用 H gate 進入到疊加態。另外 q[0] 會先用 X gate 使其變為 $\lvert 1\rangle$ 再用 H gate，目的是讓其疊加成 $\frac{\lvert 0\rangle-\lvert 1\rangle}{\sqrt{2}}$，稍後會利用到此特性。

Step 1: Find the Oracle

Oracle (Oracle Machine，預言機)⁵ 可以把它看作是一個 black box，其功能是可以透過單次運算解答特定問題。例如此簡化後問題的 oracle 可寫成 $B$ 矩陣如下。有了此矩陣，就可以做振幅放大。
$$B = \small\begin{pmatrix}
1&0&0&0 \\
0&1&0&0 \\
0&0&1&0 \\
0&0&0&-1\end{pmatrix}$$

但是這裡有一個明顯的疑問，$B$ 矩陣不就是把答案解出來了嗎 ($x_0, x_1$ 皆為 1)，怎麼還需要解問題? 其實這是因為此問題已經簡化過，所以可以示範 oracle 的模樣。在較複雜的情況下這個 oracle 是表示不出來的。因此需要靠量子特性去找出這個 oracle。

實際情況是使用量子邏輯閘。若大家還有印象我們之前練習了一堆古典邏輯閘的轉換 (Programming on Quantum Computers Chapter 2 Exercises) 這些技巧在這邊就會使用到。以本次範例為例，目的是找出 q[3], q[4] AND 的結果為 1 的情況，所以可以利用 CCNOT 建構 AND，接著將其結果存放在 q[2]，並透過 CNOT 讓 q[2] 控制 q[0]，因此當 AND 輸出結果為 1 時就會影響到 q[0]。而這也是整個演算法的核心。

透過 CNOT 去抓去 1 的結果就代表我們拿到 oracle 了，接下來需要回復 AND 的動作，以讓狀態只有 oracle。因此透過量子的其中一項特性: 可逆性，將運算反著操作就可以回復狀態。則這步驟的邏輯閘可表示成下圖，有點像是個翅膀 (為了對稱性有加一些 ID gate, 深藍色 I)。

Step 2: Amplitude Amplification

有了 oracle 後再來只需要透過 Grover’s algorithm 來操作振幅放大的工作。其中一般性的 Grover Diffusion Operator $D$ 定義為一個大小為 $2^n\times 2^n$ 內容為 $D_{i,j} = \frac{2}{2^n}$ if $i\ne j$, and $D_{i,j} = \frac{2}{2^n}-1$ if $i = j$。其中 $D = D^\dagger$ 且因為 $D\times D^\dagger = I_{2^n\times 2^n}$，符合 Unitary matrix⁶ 定義。$D$ 展開如下:

$$
D = \begin{pmatrix}
\frac{2}{2^n}-1 & \frac{2}{2^n} & \ldots & \frac{2}{2^n} \\
\frac{2}{2^n} & \frac{2}{2^n}-1 & \ldots & \frac{2}{2^n} \\
\vdots&\vdots&\ddots&\vdots\\
\frac{2}{2^n} & \frac{2}{2^n} & \ldots & \frac{2}{2^n}-1\end{pmatrix}_{2^n\times 2^n}
$$

接下來使用量子邏輯閘實作 $D$。首先介紹張量積 Tensor product ⁷, $\otimes$，範例如下:

接著定義 $\lvert\psi\rangle$ (對 $n$ 個輸入, $\lvert 0\rangle$ , 做 H gate，每個輸入對應兩種可能結果，所以整體共有 $2^n$ 種結果且機率都相同)，$\langle\psi\rvert$ 為轉置後結果。

$$
\begin{equation*}
\begin{split}
\lvert\psi\rangle =& H^{\otimes n}\lvert 0^{\otimes n}\rangle
\newline
=& \otimes^n_{k=1}\big(\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle)\big) = \frac{1}{\sqrt{2^n}}\begin{pmatrix}1 \\ 1 \\ \vdots \\ 1 \end{pmatrix}_{2^n\times 1}
\end{split}
\end{equation*}
$$

則 $D$ 矩陣的實作定義為第一行等式，並可簡化成第二行的版本方便使用量子邏輯閘實作:

$$
\begin{equation*}
\begin{split}
D =& 2\lvert\psi\rangle\langle\psi\rvert - I_{2^n\times 2^n}
\newline
\newline
=& H^{\otimes n}(2\lvert 0^{\otimes n} \rangle\langle 0^{\otimes n}\rvert - I_{2^n\times 2^n})H^{\otimes n}
\end{split}
\end{equation*}
$$

回頭看本文使用的範例，可知 $n = 2$，因此 $D$ 為:

$$
D = \begin{pmatrix}
\frac{2}{4}-1 & \frac{2}{4} & \frac{2}{4} & \frac{2}{4} \\
\frac{2}{4} & \frac{2}{4}-1 & \frac{2}{4} & \frac{2}{4} \\
\frac{2}{4} & \frac{2}{4} & \frac{2}{4}-1 & \frac{2}{4}\\
\frac{2}{4} & \frac{2}{4} & \frac{2}{4} & \frac{2}{4}-1\end{pmatrix}_{4\times 4}
$$

並可由下方邏輯閘實作 (詳細關聯待確認)，以及測量最終機率:

Run on IBM Quantum Composer

Source code

OPENQASM 2.0;
include "qelib1.inc";

qreg q[5];
creg c[5];

// Setup
x q[0];
h q[3];
h q[4];
h q[0];

barrier q[2],q[0],q[1],q[3],q[4];

// Step1: Find the Oracle
cx q[4],q[2];
tdg q[2];
cx q[3],q[2];
t q[2];
cx q[4],q[2];
tdg q[2];
t q[4];
cx q[3],q[2];
t q[2];
cx q[3],q[4];
h q[2];
t q[3];
tdg q[4];
cx q[3],q[4];
id q[2];

barrier q[2],q[0],q[1],q[3],q[4];

cx q[2],q[0];

barrier q[2],q[0],q[1],q[3],q[4];

id q[2];
cx q[3],q[4];
h q[2];
t q[3];
tdg q[4];
t q[2];
cx q[3],q[4];
cx q[3],q[2];
t q[4];
tdg q[2];
cx q[4],q[2];
t q[2];
cx q[3],q[2];
tdg q[2];
cx q[4],q[2];
h q[2];

barrier q[2],q[0],q[1],q[3],q[4];

// Step 2: Amplitude Amplification
h q[3];
h q[4];

x q[3];
x q[4];
h q[4];
cx q[3],q[4];
h q[4];
x q[4];
x q[3];
u3(2*pi,0*pi,0*pi) q[3];

h q[4];
h q[3];

// Measurement
measure q[4] -> c[4];
measure q[3] -> c[3];