アダマール変換

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

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

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

定義

アダマール変換 H_n は 2ⁿ × 2ⁿ の行列である（規格化された）アダマール行列であり、2ⁿ 個の実数 x_j を 2ⁿ 個の実数X_kに変換する。アダマール変換は、再帰的に、もしくは添え字 j 及び k の二進表現を用いることによって定義される。

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

H_{n}={\frac {1}{\sqrt {2}}}{\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 を二進数の桁 j_i（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{aligned}H_{0}&=(1)\\H_{1}&={\frac {1}{\sqrt {2}}}{\begin{pmatrix}{\begin{array}{rr}1&1\\1&-1\end{array}}\end{pmatrix}}\end{aligned}}

（H₁はサイズ2のDFTである。またZ/(2)の2要素の加法群上のフーリエ変換とみなすことが出来る）

{\begin{aligned}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{aligned}}

アダマール行列の行はウォルシュ関数である。

量子計算への応用

量子情報科学では、アダマール変換はアダマールゲート（量子論理ゲート（英語版）を参照のこと）とも呼ばれる。これは1つの量子ビットの回転であり、量子ビットの基底状態 $|0\rangle$ と $|1\rangle$ から、 $|0\rangle$ と $|1\rangle$ の2つの重みが等しい重ね合わせへの写像である。普通その位相はディラックの記法で

H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|

となるように選ばれる。 $|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)。

外部リンク

Ritter, Terry (August 1996). “Walsh-Hadamard Transforms: A Literature Survey”. 2015年4月27日閲覧。
Akansu, A.N.; Poluri, R. (July 2007). “Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications” (PDF). IEEE Trans. on Signal Processing 55 (7): 3800–6. doi:10.1109/TSP.2007.894229 2015年4月27日閲覧。.
Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation|accessdate=2015-04-27 (May 28, 2009)
“Pump-probe Spectroscopy using Hadamard Transforms” (PDF) (January 2011). 2015年4月27日閲覧。
Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (September 2014). “Time-resolved crystallography using the Hadamard transform” (HTML). Nature Methods. doi:10.1038/nmeth.3139 2015年4月27日閲覧。.

出典

^ Compare Figure 1 in Townsend, W. J.; Thornton, M. A.. Walsh Spectrum Computations Using Cayley Graphs. CiteSeer^x: 10.1.1.74.8029.

[1] Compare Figure 1 in Townsend, W. J.; Thornton, M. A.. Walsh Spectrum Computations Using Cayley Graphs. CiteSeer^x: 10.1.1.74.8029.

[1]

定義