在課堂 “量子電腦程式設計” 學到的推導過程。
主要是將一個 CCNOT 分解成使用 6 個 CNOT。

前言

算是很久沒上課了，而更久沒體會到數學推導的有趣。剛好本學期修到這堂課，老師半強迫要我們搞懂整個流程，意外找回國高中時寫數學的樂趣。在此附上我認為最詳盡易懂的推導過程。

gif 來自 cduck/bloch_sphere，references 中有附上連結。
另外，公式繁多可能有錯，再麻煩指正。

先備知識

Gate 只會介紹本篇用到的。

Math

• 複數 ($\mathbb{C}$¹): 實部 (real part) + 虛部 (imaginary part), e.g., $x + yi, i = \sqrt{-1}$.
• Euler’s identity: $e^{i\pi} + 1 = 0$. ²

Quantum bit (Qubit)

• Quantum state³
  • Classical state 0: $\lvert 0\rangle = {\small\begin{pmatrix}1 \\ 0\end{pmatrix}}$ (0 的機率為 100%)
  • Classical state 1: $\lvert 1\rangle = {\small\begin{pmatrix}0 \\ 1\end{pmatrix}}$ (1 的機率為 100%)
  • Arbitrary state: $\lvert\Phi \rangle= \alpha\lvert 0\rangle + \beta\lvert 1\rangle = {\small\begin{pmatrix}\alpha \\ \beta\end{pmatrix}}, \alpha, \beta\in\mathbb{C}$
    • (0 的機率為 $\lvert \alpha\lvert^2$, 1 的機率為 $\lvert \beta\lvert^2$)

1-bit Gate

• Hadamard gate: $H = \frac{1}{\sqrt{2}}{\small\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}}$
  • 最常用作將 classical state 轉為疊加態 (superposition)。E.g.,
  • $H\lvert 0\rangle = \frac{1}{\sqrt{2}}{\small\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}}{\small\begin{pmatrix}1 \\ 0\end{pmatrix}} = \frac{1}{\sqrt{2}}{\small\begin{pmatrix}1 \\ 1\end{pmatrix}} = \frac{\lvert 0\rangle+\lvert 1\rangle}{\sqrt{2}}$
  • $H\lvert 1\rangle = \frac{1}{\sqrt{2}}{\small\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}}{\small\begin{pmatrix}0 \\ 1\end{pmatrix}} = \frac{1}{\sqrt{2}}{\small\begin{pmatrix}1 \\ -1\end{pmatrix}} = \frac{\lvert 0\rangle-\lvert 1\rangle}{\sqrt{2}}$
  • 解釋: $\lvert 0\rangle, \lvert 1\rangle$ 經過 $H$ 後其 $0, 1$ 的機率皆各為 $\lvert \frac{1}{\pm\sqrt{2}}\lvert^2 = \frac{1}{2} = $ 50%

• Phase shift gate: $T = {\small\begin{pmatrix}1 & 0\\0 & e^{i\frac{\pi}{4}}\end{pmatrix}}$

• $T$’s conjugate transpose⁴: $T^\dagger = {\small\begin{pmatrix}1 & 0\\0 & e^{-i\frac{\pi}{4}}\end{pmatrix}}$

2-bit Gate

• Controlled NOT gate ($CNOT, CX, U_{CN}$): $U_{CN} ={\small\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}}$
  • control qubit ($\lvert C\rangle$) 為 1 時，target qubit ($\lvert T\rangle$) 會翻轉 (flip)。E.g.,
  • $U_{CN}(\frac{\lvert 0\rangle+\lvert 1\rangle}{\sqrt{2}})\lvert 0\rangle = {\small\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}} \frac{\lvert 00\rangle+\lvert 10\rangle}{\sqrt{2}} = {\small\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}} \frac{1}{\sqrt{2}} {\small\begin{pmatrix}1\\0\\1\\0\end{pmatrix}} = \frac{1}{\sqrt{2}} {\small\begin{pmatrix}1\\0\\0\\1\end{pmatrix}} = \frac{\lvert 00\rangle+\lvert 11\rangle}{\sqrt{2}}$
  • 解釋: 用 control bit 經過 $H$ 後會有 50-50 的機率，target bit 輸入為 0。則在 control bit 為 1 時，target bit 會轉為 1。因此輸出僅有兩種可能: 00 或 11。

Toffoli Gate (CCNOT)

顧名思義，有兩個 control bit，不過是兩個同時為 1 時才會影響 target bit。

不過它其實等價於下面的形式:

推導過程

這邊要先注意，輸入的兩個 control bit 有經過 $H$ 變成疊加態，也就是下圖。不同階段的狀態使用不同符號 ($\lvert\Phi_i\rangle, i = 1…16$) 以便對應。

$$
\def\TT{i\frac{\pi}{4}}
\begin{equation*}
\small
\begin{split}
\lvert\Phi_1\rangle =& \frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle) \frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle) \lvert 0\rangle \\ =& \frac{1}{2}(\lvert 000\rangle+\lvert 010\rangle+\lvert 100\rangle+\lvert 110\rangle)
\newline
\newline
\lvert\Phi_2\rangle =& \frac{1}{2} \Biggr(\lvert 00\rangle\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle) \newline &\quad+\lvert 01\rangle\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle) \newline &\quad+\lvert 10\rangle\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle) \newline &\quad+\lvert 11\rangle\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle)\Biggr)\newline =& \frac{1}{2\sqrt{2}}(\lvert 000\rangle+\lvert 001\rangle+\lvert 010\rangle+\lvert 011\rangle+\lvert 100\rangle+\lvert 101\rangle+\lvert 110\rangle+\lvert 111\rangle)
\newline
\newline
\lvert\Phi_3\rangle =& \frac{1}{2\sqrt{2}}(\lvert 000\rangle+\lvert 001\rangle+\lvert 011\rangle+\lvert 010\rangle+\lvert 100\rangle+\lvert 101\rangle+\lvert 111\rangle+\lvert 110\rangle)
\newline
\newline
\lvert\Phi_4\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+
e^{-\TT}\lvert 001\rangle+
e^{-\TT}\lvert 011\rangle+
\lvert 010\rangle+
\lvert 100\rangle+
e^{-\TT}\lvert 101\rangle+
e^{-\TT}\lvert 111\rangle+
\lvert 110\rangle)
\newline
\newline
\lvert\Phi_5\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+
e^{-\TT}\lvert 001\rangle+
e^{-\TT}\lvert 011\rangle+
\lvert 010\rangle+
\lvert 101\rangle+
e^{-\TT}\lvert 100\rangle+
e^{-\TT}\lvert 110\rangle+
\lvert 111\rangle)
\newline
\newline
\lvert\Phi_6\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+
e^{\TT}e^{-\TT}\lvert 001\rangle+
e^{\TT}e^{-\TT}\lvert 011\rangle+
\lvert 010\rangle\newline &\qquad+
e^{\TT}\lvert 101\rangle+
e^{-\TT}\lvert 100\rangle+
e^{-\TT}\lvert 110\rangle+
e^{\TT}\lvert 111\rangle)\newline
=& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+\lvert 001\rangle+
\lvert 011\rangle+\lvert 010\rangle+e^{\TT}\lvert 101\rangle+
e^{-\TT}\lvert 100\rangle+
e^{-\TT}\lvert 110\rangle+
e^{\TT}\lvert 111\rangle)
\newline
\newline
\lvert\Phi_7\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+\lvert 001\rangle+
\lvert 010\rangle+\lvert 011\rangle+e^{\TT}\lvert 101\rangle+
e^{-\TT}\lvert 100\rangle+
e^{-\TT}\lvert 111\rangle+
e^{\TT}\lvert 110\rangle)
\newline
\newline
\lvert\Phi_8\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+
e^{-\TT}\lvert 001\rangle+
\lvert 010\rangle+
e^{-\TT}\lvert 011\rangle+
\lvert 101\rangle+
e^{-\TT}\lvert 100\rangle+
e^{-2\TT}\lvert 111\rangle+
e^{\TT}\lvert 110\rangle)
\newline
\newline
\lvert\Phi_{9}\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+
e^{-\TT}\lvert 001\rangle+
\lvert 010\rangle+
e^{-\TT}\lvert 011\rangle+
\lvert 100\rangle+
e^{-\TT}\lvert 101\rangle+
e^{-2\TT}\lvert 110\rangle+
e^{\TT}\lvert 111\rangle)
\newline
\newline
\lvert\Phi_{10}\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+
\lvert 001\rangle+
\lvert 010\rangle+
\lvert 011\rangle+
\lvert 100\rangle+
\lvert 101\rangle+
e^{-2\TT}\lvert 110\rangle+
e^{2\TT}\lvert 111\rangle)
\newline
\newline
\lvert\Phi_{11}\rangle =& \frac{1}{2\sqrt{2}}(
\lvert 000\rangle+
\lvert 001\rangle+
e^{\TT}\lvert 010\rangle+
e^{\TT}\lvert 011\rangle+
\lvert 100\rangle+
\lvert 101\rangle+
e^{-\TT}\lvert 110\rangle+
e^{3\TT}\lvert 111\rangle)
\newline
\newline
\lvert\Phi_{12}\rangle =& \frac{1}{2\sqrt{2}}\Biggr(
\lvert 00\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle) \newline &\qquad+
\lvert 00\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle-\lvert 1\rangle)\newline &\qquad+
\lvert 01\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle)e^{\TT}\newline &\qquad+
\lvert 01\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle-\lvert 1\rangle)e^{\TT}\newline &\qquad+
\lvert 10\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle)\newline &\qquad+
\lvert 10\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle-\lvert 1\rangle)\newline &\qquad+
\lvert 11\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle)e^{-\TT}\newline &\qquad+
\lvert 11\rangle \frac{1}{\sqrt{2}}(\lvert 0\rangle-\lvert 1\rangle)e^{3\TT}\Biggr)\newline
=& \frac{1}{2\sqrt{2}}(
\frac{2}{\sqrt{2}}\lvert 000\rangle+
e^{\TT}\frac{2}{\sqrt{2}}\lvert 010\rangle+
\frac{2}{\sqrt{2}}\lvert 100\rangle+
e^{-\TT}\frac{2}{\sqrt{2}}\lvert 111\rangle
)\newline
=& \frac{1}{2}(\lvert 000\rangle + e^{\TT}\lvert 010\rangle + \lvert 100\rangle + e^{-\TT}\lvert 111\rangle)
\newline
\newline
\lvert\Phi_{13}\rangle =& \frac{1}{2}(\lvert 000\rangle + e^{\TT}\lvert 010\rangle + \lvert 110\rangle + e^{-\TT}\lvert 101\rangle)
\newline
\newline
\lvert\Phi_{14}\rangle =& \frac{1}{2}(\lvert 000\rangle + \lvert 010\rangle + e^{-\TT}\lvert 110\rangle + e^{-\TT}\lvert 101\rangle)
\newline
\newline
\lvert\Phi_{15}\rangle =& \frac{1}{2}(\lvert 000\rangle + \lvert 010\rangle + \lvert 110\rangle + \lvert 101\rangle)
\newline
\newline
\lvert\Phi_{16}\rangle =& \frac{1}{2}(\lvert 000\rangle + \lvert 010\rangle + \lvert 100\rangle + \lvert 111\rangle)
\end{split}
\end{equation*}
$$

解釋

最終結果推出這樣的輸入下 (前兩位元疊加態，第三位元 0) 只有四種輸出可能 (000, 010, 100, 111) 各佔 25%，前三種因為前兩位元不全為 1 所以第三位元維持 0。第四種因為前兩位元皆為 1，第三位元因此翻轉成 1。

補充說明

其中我認為最精采的是 $\lvert\Phi_{12}\rangle$，在這步驟中，原先 8 個狀態透過 $H$ 作用後可以抵消掉 4 個狀態。比較需要注意的是 $e^{-\TT} = -1 \cdot e^{3\TT}$ 因此會消掉 $\lvert 11\rangle\lvert 0\rangle$ 這項。

References

• Quantum logic gate - wiki
• Qubit Bloch Sphere Visualization: cduck/bloch_sphere - github
• Fundamentals of Quantum Programming in IBM’s Quantum Computers