アダマール変換

**アダマール変換**（、**ウォルシュ–アダマール変換**や**アダマール–ラーデマッヘル–ウォルシュ変換** 、**ウォルシュ変換**、**ウォルシュ–フーリエ変換**としても知られている）は、フーリエ変換の一般化の1つである。この変換は直交かつ対称かつ対合かつ線形な写像であり、2*n*個の実数（もしくは複素数もしくは多元数）に作用する（しかし，アダマール行列自体は、純粋な実数行列である）。

アダマール変換はサイズ2の離散フーリエ変換 (DFT) から構築されているとみなすことができ、実際、サイズが2\times2\times\cdots\times2\times2の多次元離散フーリエ変換と等価である。これは任意の入力ベクトルをの重ね合わせに分解する。

この変換はフランスの数学者ジャック・アダマール、ドイツの数学者ハンス・ラーデマッヘル、アメリカ合衆国の数学者にちなんで命名されている。

## 定義
アダマール変換 *H**n* は 2*n*&nbsp;&times;&nbsp;2*n* の行列である（規格化された）アダマール行列であり、2*n* 個の実数 *x**j* を 2*n* 個の実数*X**k*に変換する。アダマール変換は、再帰的に、もしくは添え字 *j* 及び *k* の二進表現を用いることによって定義される。

再帰的な定義は以下の通りである。まずアダマール変換 *H*0 は 1&nbsp;&times;&nbsp;1 の単位行列 1である。そして *n*&nbsp;>&nbsp;0 について *H**n* を

:H_n = \frac{1}{\sqrt2} \begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}

で定義する。規格化係数 1/√2 は省略されることがある。*n*&nbsp;>&nbsp;1 のとき、クロネッカー積⊗を用いると

:H_n = H_{1} \otimes H_{n-1} = \bigotimes_{i=1}^{n} H_{1}

と表すことができる。
従って、この規格化係数以外のアダマール行列は全て 1 と &minus;1 で構成される。

あるいは別の表現として、アダマール行列の (*j*,&nbsp;*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* を二進数の桁 *j<sub>i</sub>*（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

である。入力と出力を *j**i* と *k**i* で添字付けられた多次元配列とみなした際、これはユニタリ作用素となるように規格化された 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}

（*H*1はサイズ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*=2*m*個の直交状態をすべて同じ重みで重ね合わせた状態に初期化する。

量子アダマール変換の計算は、各量子ビットに対してそれぞれアダマールゲートを適用するだけである。アダマール変換がテンソル積の構造を持つからである。このシンプルな結果が示すことは、量子アダマール変換は *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のようなデータ圧縮アルゴリズムで用いられる。ビデオ圧縮アプリケーションでは、普通は絶対変換差で使用される。また、量子アルゴリズムにおけるグローバーのアルゴリズムやショアのアルゴリズムでも重要である。アダマール変換はまた核磁気共鳴や質量分析法、結晶学といったような科学的方法にも適用される。

## 学習上の参考になる図書や文献
* 遠藤靖：「ウォルシュ解析」、東京電機大学出版局、ISBN 4-501-61340-8 (1993年11月10日)。
*赤浦協一郎：「文書画像の属性識別に関する研究ーアダマール変換による画像特性抽出ー」、早稲田大学大学院理工学研究科修士論文(1985)。

## 関連項目
* 
* 
* 
* 

## 外部リンク
*
*
* Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation|accessdate=2015-04-27 (May 28, 2009)
*
*

## 出典