この記事は,ベクトルの内積や行列の掛け算や転置など基本的な線型代数の知識を前提とします.
#ベクトルとブラケット記法
$2$次元縦ベクトル$|0 \rangle $と$|1 \rangle$を次で定義する.
|0 \rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \hspace{20pt}
|1 \rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}
さらに
|+ \rangle = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \hspace{20pt}
|- \rangle = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}
と定義する.この$| \cdot \rangle$のことをケットと呼ぶ.
ケットの転置をとったものをブラと呼び,$\langle \cdot |$と表記する.例えば
\langle 0 | = \begin{bmatrix} 1 & 0 \end{bmatrix} \hspace{20pt}
\langle - | = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & -1 \end{bmatrix}
行ベクトルと列ベクトルの積は内積に相当し,内積$\langle , \rangle$を次のように略記する.
(|0 \rangle と|+ \rangle の内積) = \langle 0 | |+ \rangle = \langle 0|+ \rangle \hspace{10pt} (= 1 \cdot \frac{1}{\sqrt{2}} + 0 \cdot \frac{1}{\sqrt{2}} = \frac{1}{\sqrt{2}})
ベクトル$x,y$が直交するとは$\langle x,y \rangle = 0$である事を言う.
#テンソル積
ベクトル$x$の第n成分を$x(n)$と表記する.また成分は一番最初を第$0$成分とし,$n$はビット列(二進数表示)で表されることが多い.
a \otimes b = c \Leftrightarrow c(ij) = a(i) \times b(j)
上式で$i,j$はビット列,$ij$はその連結である事に注意.具体例を挙げると
| 0 \rangle \otimes |1 \rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \otimes \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \times 0 \\ 1 \times 1 \\ 0 \times 0 \\ 0 \times 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}
ちなみに,ブラケット記法ではテンソル積を省略して表記する事がある.つまり$| 0 \rangle \otimes | 1 \rangle = | 0 \rangle | 1 \rangle$さらにこれを$|01 \rangle$と表記する事もある.
この表現の素晴らしい点は二進数表示で中身の数の成分だけが1で他の成分が0であるベクトル,という解釈が可能な点である.
#複素行列とユニタリ行列
行列$U$に対して(成分が複素数でもよい)成分を複素共役をとりさらに転置をとった行列を随伴行列と言い,$U^*$で表す.
さらに,行列$U$が$U U^* = I$を満たすならば$U$をユニタリ行列または単にユニタリと言う.ユニタリとユニタリの積は再びユニタリである.次の諸性質は量子アルゴリズムで重要である.
###性質1 ノルム保存の性質
任意のベクトル$x$とユニタリ$U$に対して
||x || = || Ux ||
###性質2 正規直交基底との関係
ユニタリ$U$を列ベクトルを並べたのもと解釈すれば$U = [u_1 , u_2 , \cdots u_n]$と表せる.このときベクトル$u_1 , u_2 , \cdots u_n$は正規直交基底である,すなわちすべてノルムが$1$で全て互いに直交する.
ちなみに,行列$U$がユニタリである事,性質1を満たすこと,性質2を満たすこと,これらは互いに同値である.
#行列のテンソル積と重要なユニタリ
$U$を$m \times n$行列、$V$を$r \times s$行列とした時それらのテンソル積$W = U \otimes V$は$mr \times ns$行列で、$c(ij) = a(i) {b}(j)$を満たす任意のベクトルの組を用いて
({W}{c})(ij) = ({U}{a})(i)({V}{b})(j)
を満たす行列として定義される。しかし定義に基づいて行列のテンソル積を求めるのはとても手間がかかるので次の便利な計算方法を覚えておこう.
\begin{bmatrix} a & b \\ c & d \end{bmatrix}
\otimes
\begin{bmatrix} x & y \\ z & w \end{bmatrix}
=
\begin{bmatrix} a \begin{bmatrix} x & y \\ z & w \end{bmatrix} & b \begin{bmatrix} x & y \\ z & w \end{bmatrix} \\ c\begin{bmatrix} x & y \\ z & w \end{bmatrix} & d\begin{bmatrix} x & y \\ z & w \end{bmatrix} \end{bmatrix}
=
\begin{bmatrix} ax & ay & bx & by \\ az & aw & bz & bw
\\ cx & cy & dx & dy \\ cz & cw & dz & dw \end{bmatrix}
こんな具合である.どんな行列のサイズでもテンソル積が定義されるのは嬉しい.
###アダマール行列
$2^n \times 2^n$行列であるアダマール行列$H_{2^n}$を帰納的に定義する.
H_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}
\hspace{20pt} H_{2^{n+1}} = H_{2^n} \otimes H_{2}
特に$H_2$の事を単に$H$と書く場合もある.
任意の$2^n$次元ベクトル$a$に対して$b = H_{2^n} a$の第$x$成分$b(x)$は
b(x) = \frac{1}{\sqrt{2^n}} \sum_{t=0}^{N-1}(-1)^{x \bullet t} a(t)
ここで$x \bullet t$とは二進数内積のことである,たとえば
10010 \bullet 11000 = (1 \times 1)(0 \times 1)\cdots (0 \times 0) = 10000
このように一文字ごとに掛け算して連結させたものである(論理積とも言える).