アダマール変換
アダマール変換(Hadamard transform、ウォルシュ–アダマール変換やアダマール–ラーデマッヘル–ウォルシュ変換 Hadamard–Rademacher–Walsh transform、ウォルシュ変換、ウォルシュ–フーリエ変換としても知られている)は、フーリエ変換の一般化の1つである。この変換は直交かつ対称かつ対合かつ線形な写像であり、2n個の実数(もしくは複素数もしくは多元数)に作用する(しかし,アダマール行列自体は、純粋な実数行列である)。
アダマール変換はサイズ2の離散フーリエ変換 (DFT) から構築されているとみなすことができ、実際、サイズが2\times2\times\cdots\times2\times2の多次元離散フーリエ変換と等価である。これは任意の入力ベクトルをウォルシュ関数の重ね合わせに分解する。
この変換はフランスの数学者ジャック・アダマール、ドイツの数学者ハンス・ラーデマッヘル、アメリカ合衆国の数学者ジョセフ・L・ウォルシュにちなんで命名されている。
アダマール変換 Hn は 2n × 2n の行列である(規格化された)アダマール行列であり、2n 個の実数 xj を 2n 個の実数Xkに変換する。アダマール変換は、再帰的に、もしくは添え字 j 及び k の二進表現を用いることによって定義される。
再帰的な定義は以下の通りである。まずアダマール変換 H0 は 1 × 1 の単位行列 1である。そして n > 0 について Hn を
H_n = \frac{1}{\sqrt2} \begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}
で定義する。規格化係数 1/√2 は省略されることがある。n > 1 のとき、クロネッカー積⊗を用いると
H_n = H_{1} \otimes H_{n-1} = \bigotimes_{i=1}^{n} H_{1}
と表すことができる。
従って、この規格化係数以外のアダマール行列は全て 1 と −1 で構成される。
あるいは別の表現として、アダマール行列の (j, k) 成分を
\left( H_n \right)_{j+1,k+1} = \frac{1}{2^{n/2} (-1)^{\boldsymbol{j} \cdot \boldsymbol{k}
と定義することもできる。ただし \boldsymbol{j} \cdot \boldsymbol{k} は数 j と k の二進表現のビットごとの内積(すなわちビット単位AND演算のハミング重み)である。j を二進数の桁 ji(0 もしくは 1)で
j = \sum_{i=0}^{n-1} j_i 2^i = j_{n-1} 2^{n-1} + j_{n-2} 2^{n-2} + \dots + j_1 2 + j_0
\boldsymbol{j} \cdot \boldsymbol{k} = \sum_{i=0}^{n-1} j_i k_i
である。入力と出力を ji と ki で添字付けられた多次元配列とみなした際、これはユニタリ作用素となるように規格化された 2 \times 2 \times \cdots \times 2 \times 2 次元DFTとなる。
アダマール行列のいくつかの例を以下に示す。
\begin{align}
H_0 &= (1) \\
H_1 &= \frac{1}{\sqrt2}
\begin{pmatrix}\begin{array}{rr}
1 & 1\\
1 & -1
\end{array}\end{pmatrix}
\end{align}
(H1はサイズ2のDFTである。またZ/(2)の2要素の加法群上のフーリエ変換とみなすことが出来る)
\begin{align}
H_2 = \frac{1}{2}
&\begin{pmatrix}\begin{array}{rrrr}
1 &  1 &  1 &  1\\
1 & -1 &  1 & -1\\
1 &  1 & -1 & -1\\
1 & -1 & -1 &  1
\end{array}\end{pmatrix}\\
H_3 = \frac{1}{2^{3/2}
&\begin{pmatrix}\begin{array}{rrrrrrrr}
1 &  1 &  1 &  1 &  1 &  1 &  1 &  1\\
1 & -1 &  1 & -1 &  1 & -1 &  1 & -1\\
1 &  1 & -1 & -1 &  1 &  1 & -1 & -1\\
1 & -1 & -1 &  1 &  1 & -1 & -1 &  1\\
1 &  1 &  1 &  1 & -1 & -1 & -1 & -1\\
1 & -1 &  1 & -1 & -1 &  1 & -1 &  1\\
1 &  1 & -1 & -1 & -1 & -1 &  1 &  1\\
1 & -1 & -1 &  1 & -1 &  1 &  1 & -1
\end{array}\end{pmatrix}
\end{align}
アダマール行列の行はウォルシュ関数である。
量子情報科学では、アダマール変換はアダマールゲート(量子論理ゲートを参照のこと)とも呼ばれる。これは1つの量子ビットの回転であり、量子ビットの基底状態|0 \rangle と|1 \rangle から、|0 \rangle と|1 \rangle の2つの重みが等しい重ね合わせへの写像である。普通その位相はディラックの記法で
H=\frac〔0\rangle+|1\rangle}{\sqrt{2}\langle0|+\frac〔0\rangle-|1\rangle}{\sqrt{2}\langle1|
となるように選ばれる。|0 \rangle と|1 \rangle を基底としたとき、これは変換行列
H_1=\frac{1}{\sqrt{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}
に対応する。
多くの量子アルゴリズムはアダマール変換を初期化に利用している。m 個の|0 \rangle の量子ビットを、|0 \rangle と|1 \rangle を基底とする n=2m個の直交状態をすべて同じ重みで重ね合わせた状態に初期化する。
量子アダマール変換の計算は、各量子ビットに対してそれぞれアダマールゲートを適用するだけである。アダマール変換がテンソル積の構造を持つからである。このシンプルな結果が示すことは、量子アダマール変換は m=log n 回の演算しか要求しないということである。これに対して、古典的な場合は n log n の演算が必要である。
H(|1\rangle) = \frac{1}{\sqrt{2}|0\rangle-\frac{1}{\sqrt{2}|1\rangle
H(|0\rangle) = \frac{1}{\sqrt{2}|0\rangle+\frac{1}{\sqrt{2}|1\rangle
H\left( \frac{1}{\sqrt{2}|0\rangle+\frac{1}{\sqrt{2}|1\rangle \right)= \frac{1}{2}( |0\rangle+|1\rangle) + \frac{1}{2}( |0\rangle - |1\rangle) = |0\rangle
H\left( \frac{1}{\sqrt{2}|0\rangle-\frac{1}{\sqrt{2}|1\rangle \right)= \frac{1}{2}( |0\rangle+|1\rangle) - \frac{1}{2}( |0\rangle - |1\rangle) = |1\rangle
0または1のqubitにアダマールゲートを1回適用すると(上の最初の二つの式)、0と1が等しい確率で観測されるような量子ビットが生成される。これは、例えば表と裏が出る確率が同様に確からしいコインを投げるようなものである。しかし、もしアダマールゲートが2回続けて適用された場合(上の3番目と4番目の式)、最終的な状態は初期状態に等しくなる。
ケット |0\rangle =
\begin{bmatrix}
1  \\
0 \\
\end{bmatrix}
であり、ケット |1\rangle =
\begin{bmatrix}
0  \\
1 \\
\end{bmatrix}
である。
アダマール変換は高速アダマール変換を用いると O(n \operatorname{log}n) \quad (n=2^m) である。
アダマール変換は暗号理論並びに多くの信号処理やJPEG XR、MPEG-4 AVCのようなデータ圧縮アルゴリズムで用いられる。ビデオ圧縮アプリケーションでは、普通は絶対変換差で使用される。また、量子アルゴリズムにおけるグローバーのアルゴリズムやショアのアルゴリズムでも重要である。アダマール変換はまた核磁気共鳴や質量分析法、結晶学といったような科学的方法にも適用される。