實作邏輯閘

第二章的內容就是先介紹了 CCNOT 邏輯閘 (請參考之前文章 “Quantum Toffoli Gate (CCNOT) Decomposition)"。此邏輯閘的出現可以讓古典運算做對照，也就是可以用量子邏輯閘來模擬古典邏輯閘的特性。不過並非純粹模擬，而是利用同樣輸入輸出的特性來得以描述同一問題，並嘗試利用量子特性來加速解決問題的時間。

本章作業內容是利用 CCNOT 可類推到 AND 的特性 (如下圖) 來將給定的邏輯閘轉換成使用 CCNOT。

這裡會大量使用笛摩根定理 ¹ 將主要邏輯閘換成 AND。另外這裡使用的符號跟課本所用的符號不太一樣 (因為 $\bar{x}$ 在多層下不太方便):

$\lnot x$: NOT x
$x\lor y$: x OR y
$x\land y$: x AND y

另外量子的表達方法用 OpenQASM 的方式呈現，$x$ 對應 q[0], $y$ 對應 q[1], 輸出為 q[2]，其中 q[0], q[1] 會用 Hadamard 使輸入變成疊加態。篇幅問題重複部分 (標頭檔、宣告、Hadamard、測量) 就不寫如簡化後版本:

例如: $\lnot x \land y$ 簡化前:

OPENQASM 2.0;
include "qelib1.inc";
qreg q[5];
creg c[3];
h q[0];
h q[1];
// ---
x q[0];
ccx q[0], q[1], q[2];
x q[0]; // 回復 q[0]
// ---
measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];

例如: $\lnot x \land y$ 簡化後:

x q[0];
ccx q[0], q[1], q[2];
x q[0]; // 回復 q[0]

$\lnot x \lor y$

$\lnot x \lor y \Longleftrightarrow \lnot(\lnot\lnot x \land \lnot y) \Longleftrightarrow \lnot(x \land \lnot y)$

x q[1];
x q[2]; // AND 後 NOT 的做法是把 target bit 先 NOT
ccx q[0], q[1], q[2];
x q[1];

$x \lor \lnot y$

$x \lor \lnot y \Longleftrightarrow \lnot(\lnot x \land \lnot\lnot y) \Longleftrightarrow \lnot(\lnot x \land y)$

x q[0];
x q[2]; // AND 後 NOT 的做法是把 target bit 先 NOT
ccx q[0], q[1], q[2];
x q[0];

$\lnot y \land (x \lor \lnot x)$

比較特別是 $x$ 跟 $\lnot x$ 需要分開，另外會需要用到兩個暫存 qubit (q[3], q[4])。

$\lnot y \land (x \lor \lnot x)
\Longleftrightarrow (\lnot y \land x) \lor (\lnot y \land \lnot x)
\Longleftrightarrow \lnot \Big(\lnot (\lnot y \land x) \land \lnot(\lnot y \land \lnot x)\Big)$

// (\lnot y \land x)
x q[1];
ccx q[0], q[1], q[3];
x q[1];
barrier q[0],q[1],q[2],q[3],q[4];

// (\lnot y \land \lnot x)
x q[0];
x q[1];
ccx q[0], q[1], q[4];
x q[0];
x q[1];
barrier q[0],q[1],q[2],q[3],q[4];

x q[3];
x q[4];
x q[2];
ccx q[3], q[4], q[2];
x q[3];
x q[4];

$\lnot x \land (y \lor \lnot y)$

其實跟上面類似，只是 $x, y$ 互換

$\lnot x \land (y \lor \lnot y)
\Longleftrightarrow \lnot \Big(\lnot (\lnot x \land y) \land \lnot(\lnot x \land \lnot y)\Big)$

// (\lnot x \land y)
x q[0];
ccx q[0], q[1], q[3];
x q[0];
barrier q[0],q[1],q[2],q[3],q[4];

// (\lnot x \land \lnot y)
x q[0];
x q[1];
ccx q[0], q[1], q[4];
x q[0];
x q[1];
barrier q[0],q[1],q[2],q[3],q[4];

x q[3];
x q[4];
x q[2];
ccx q[3], q[4], q[2];
x q[3];
x q[4];