次に、1ビットのユニタリー変換と2ビットの制御NOTで、
任意の2ビットのユニタリー変換が作れることを示す。

前節で、1ビットのユニタリー変換と2ビットの制御NOTで、
制御U、制御Vが作れることを示したので、
制御U、制御Vを任意の2ビットのユニタリー変換の構成に用いることができる。

以下、2ビットの状態を、
$|0\rangle |0\rangle =|0),|0\rangle |1\rangle =|1),|1\rangle |0\rangle = |2),|1\rangle |1\rangle = |3)$
と書くことがある。

任意の2ビットのユニタリー変換は、
その固有値と固有ベクトルで対角化した表示で、
\begin{align}
S=\sum_{n=0}^3 e^{i\gamma _n} |\psi_n \rangle \langle \psi_n | \label{eq:Unitary}
\end{align}
と書ける。$|\psi_n \rangle ,e^{i\gamma_n} (n=0,1,2,3)$は
それぞれ$S$の固有ベクトル、固有値であり、
$S$を与えればそこから求めることができる。

この任意の$S$から決まる固有ベクトル$|\psi_n \rangle $を
2ビットの標準基底で展開すると、
\begin{gather}
|\psi_n \rangle =\sum_{a,b=0,1} c_{ab}^n |a \rangle |b \rangle
\end{gather}
となる。まずこの$|\psi_n \rangle $に対して、
\begin{gather}
G(\psi_n )|\psi_n \rangle = |n ) \qquad (n=0,1,2,3)
\end{gather}
と2ビットの状態に変換する$G(\psi_n)$が作れることを示す。

例として$n=3$のときのみを示すことにする。
すなわち$|\psi_3 \rangle$を$|3)=|1\rangle |1\rangle$に移すことを考える。

$|\psi_n \rangle$を2ビットの状態を基底として行列表示すれば、
\begin{gather}
| \psi_3 \rangle = \begin{pmatrix} c_{00} \\ c_{01} \\ c_{10} \\ c_{11} \end{pmatrix}
\end{gather}
ここで、$c$の$n=3$の添え字は見にくくなるので省略した。

これに、前に述べた第1ビットを制御ビット、
第2ビットを標的ビットとした制御U演算
\begin{gather}
\begin{pmatrix} 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \\
\end{pmatrix}
\end{gather}
を作用させると、
\begin{align}
& \begin{pmatrix} 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \\
\end{pmatrix} \begin{pmatrix} c_{00} \\ c_{01} \\ c_{10} \\ c_{11} \end{pmatrix} \\
= & c_{00} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}
+ c_{01} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}
+ \begin{pmatrix} 0 \\ 0 \\ c_{10}u_{11}+c_{11}u_{12} \\ c_{10}u_{21}+c_{11}u_{22} \end{pmatrix}
\end{align}
ここで、
\begin{align}
c_{01}u_{11}+c_{11}u_{12} = 0
\end{align}
となるように$u_{11},u_{12}$をとれば、
\begin{align}
|\psi_3 \rangle \stackrel{\text{制御U}}{\longrightarrow } c_{00}|0\rangle |0\rangle + c_{01}
|0\rangle |1\rangle + c_{11}'|1\rangle |1\rangle
\end{align}
のように、$|1\rangle |0\rangle$を掃きだすことができる。

続いて、第1ビットにNOT演算を行うと、
\begin{align}
|\psi_3 \rangle \stackrel{\text{制御U+NOT}}{\longrightarrow } c_{00}|1\rangle |0\rangle + c_{01}|1\rangle |1\rangle + c_{11}'|0\rangle |1\rangle
\end{align}
この状態に、上と同様の制御Uを行うと、
$|1\rangle |0\rangle $状態を掃きだせるから、
\begin{align}
|\psi_3 \rangle \stackrel{\text{制御U+NOT+制御U}}{\longrightarrow } c_{01}'|1\rangle |1\rangle + c_{11}'|0\rangle |1\rangle
\end{align}
最後に、第2ビットを制御ビット、第1ビットを標的ビットとした制御V
\begin{align}
\begin{pmatrix} 1 & 0 & 0 & 0 \\
0 & v_{11} & 0 & v_{12} \\
0 & 0 & 1 & 0 \\
0 & v_{21} & 0 & v_{22} \\
\end{pmatrix}
\end{align}
を作用させると
\begin{align}
&\begin{pmatrix} 1 & 0 & 0 & 0 \\
0 & v_{11} & 0 & v_{12} \\
0 & 0 & 1 & 0 \\
0 & v_{21} & 0 & v_{22} \\
\end{pmatrix}
\begin{pmatrix} 0 \\ c_{01}' \\ 0 \\ c_{11}' \end{pmatrix}\\
=& \begin{pmatrix}
0 \\ c_{01}'v_{11}+c_{11}'v_{12} \\ 0 \\ c_{01}'v_{21}+c_{11}'v_{22}
\end{pmatrix}
\end{align}
前と同様に、
\begin{align}
c_{01}'v_{11}+c_{11}'v_{12}=0
\end{align}
となるように$v_{11},v_{12}$をとれば、
$|0\rangle |1\rangle$を掃きだすことができて、
結局、
\begin{align}
|\psi_3 \rangle \stackrel{\text{制御U+NOT+制御U+制御V}}{\longrightarrow } c_{01}''|1\rangle |1\rangle
\end{align}
よって、$c_{11}''=1$となるように$u_{21},u_{22},v_{21},v_{22}$をとれば、
\begin{align}
|\psi_3 \rangle \longrightarrow |1\rangle |1\rangle
\end{align}
したがって、$|\psi_3 \rangle $から$|1\rangle |1\rangle = |3)$へ
変換する$G(\psi_3)$が構成できた。

$|0\rangle |1\rangle , |1\rangle |0\rangle , |0\rangle |0\rangle$への変換についても同様に構成できる。
例として、上で示した$|\psi_3 \rangle $から$|1\rangle |1\rangle = |3)$への変換の量子回路を下に示す。

したがって、$G(\psi_n)$が1ビットのユニタリー変換と、
2ビットの制御NOTで作れることが示せた。

続いて、この$G(\psi_n)$を用いて
任意の2ビットのユニタリー変換が作れることを示す。

任意の2ビットのユニタリー変換は(\ref{eq:Unitary})のように書ける。
これが$G(\psi_n)$を用いて、
\begin{align}
S=\prod_{n=0}^3 G(\psi_n)^{-1} X_n G(\psi _n) \label{eq:Unitary2}
\end{align}
と書けることを示す。ここで、$X_n$は、
\begin{align}
X_0 = e^{i\gamma _0} |0)(0|+|1)(1|+|2)(2|+|3)(3| \\
X_1 = |0)(0|+ e^{i\gamma _1}|1)(1|+|2)(2|+|3)(3| \\
X_2 = |0)(0|+|1)(1|+ e^{i\gamma _2}|2)(2|+|3)(3| \\
X_3 = |0)(0|+|1)(1|+|2)(2|+ e^{i\gamma _3}|3)(3|
\end{align}
である。

まず、$X_n$が1ビットのユニタリー演算と制御Uで作れることを示す。
例として$X_0$は行列表示すると、
\begin{align}
\begin{pmatrix}
e^{i\gamma_0} & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}
\end{align}
である。
これは第1ビットに対するNOT演算と制御Uを用いて作ることができる。
\begin{align}
&NOT+制御U+NOT\notag \\ =
&\begin{pmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22}
\end{pmatrix}
\begin{pmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{pmatrix} \\ =
&\begin{pmatrix}
u_{11} & u_{12} & 0 & 0 \\
u_{21} & u_{22} & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}
\end{align}
ここで、$u_{11}=e^{i\gamma _0},u_{12}=u_{21}=0,u_{22}=1$とすれば、$X_0$となる。
他の$X_n$についても同様である。$X_0$について量子回路を書くと、下のようになる。

次に、(\ref{eq:Unitary2})を証明する。(\ref{eq:Unitary})を書き換えると、
\begin{align}
S|\psi_n \rangle = e^{i\gamma_n} |\psi _n \rangle \qquad (n=0,1,2,3)
\end{align}
となる。よって、(\ref{eq:Unitary2})の代わりに、
\begin{align}
\prod_{i=0}^3 G(\psi_i)^{-1} X_i G(\psi _i) | \psi_n \rangle = e^{i\gamma_n } |\psi _n \rangle
\qquad (n=0,1,2,3) \label{eq:Unitary3}
\end{align}
を示せばよい。

ここで、
\begin{align}
& (n | G(\psi_n) | \psi _m \rangle \\
= & \langle \psi_n | G(\psi_n)^\dagger G(\psi_n) | \psi_m \rangle \\
= & \langle \psi_n | \psi_m \rangle \qquad (n\neq m)
\end{align}
を用いると、$n\neq0$のとき、
\begin{align}
& G(\psi_0)^{-1} X_0 G(\psi _0) | \psi_n \rangle \\
= & G(\psi_0)^{-1} \{ e^{i\gamma_0} |0)(0|+|1)(1|+|2)(2|+|3)(3| \} G(\psi_0)|\psi_n \rangle \\
= & G(\psi_0)^{-1} \{ |0)(0|+|1)(1|+|2)(2|+|3)(3| \} G(\psi_0) |\psi_n \rangle \\
= & G(\psi_0)^{-1} G(\psi_0) | \psi_n \rangle \\
= & |\psi_n \rangle \qquad (n\neq 0 のとき)
\end{align}
よって一般には、$n\neq m$のとき、
\begin{align}
&G(\psi_n)^{-1} X_n G(\psi_n) | \psi \rangle \\
= & |\psi_m \rangle (n\neq m のとき)
\end{align}
となる。$n=m$のときは、
\begin{align}
& G(\psi_n)^{-1} X_n G(\psi_n) |\psi_n \rangle \\
= & G(\psi_n)^{-1} X_n |n) \\
= & G(\psi_n)^{-1} e^{i\gamma _n} |n) \\
= & e^{i\gamma_n} |\psi_n \rangle
\end{align}
以上より、
\begin{align}
\prod_{i=0}^3 G(\psi_i)^{-1} X_i G(\psi _i) | \psi_n \rangle = e^{i\gamma_n } |\psi _n \rangle
\qquad (n=0,1,2,3)
\end{align}
となる。
よって(\ref{eq:Unitary3})が示されたから、(\ref{eq:Unitary2})が示されて、
\begin{align}
S=\prod_{n=0}^3 G(\psi_n)^{-1} X_n G(\psi _n)
\end{align}
となり、任意の2ビットのユニタリー変換$S$が、
$G(\psi_n)$と$X_n$であらわされた。

したがって、任意の2ビットのユニタリー変換が、
1ビットのユニタリー変換と2ビットの制御NOTで作れることが示せた。

以上の議論を応用すれば、任意の$n$ビットのユニタリー変換が、
1ビットの演算と制御NOTのみで構成できることを示すことができる。