「ウォルシュ行列(英語版) 」とは異なります。
ブール関数 とウォルシュ行列(英語版) の積 は、そのウォルシュスペクトラム[ 1] である。 (1,0,1,0,0,1,1,0) * H(8) = (4,2,0,−2,0,2,0,2) 高速ウォルシュ-アダマール変換(英語版) これは(1,0,1,0,0,1,1,0)のウォルシュスペクトラムを早く計算するための方法である. 元の関数は多項式としてのウォルシュスペクトラムの平均によって表現することが出来る。 アダマール変換 (英語 : Hadamard transform 、ウォルシュ–アダマール変換 やアダマール–ラーデマッヘル–ウォルシュ変換 英語 : Hadamard–Rademacher–Walsh transform 、ウォルシュ変換 、ウォルシュ–フーリエ変換 としても知られている)は、フーリエ変換 の一般化の1つである。この変換は直交 かつ対称 かつ対合 かつ線形 な写像であり、2n 個の実数 (もしくは複素数 もしくは多元数 )に作用する(しかし,アダマール行列自体は、純粋な実数行列である)。
アダマール変換はサイズ2の離散フーリエ変換 (DFT) から構築されているとみなすことができ、実際、サイズが 2 × 2 × ⋯ × 2 × 2 {\displaystyle 2\times 2\times \cdots \times 2\times 2} の多次元離散フーリエ変換と等価である。これは任意の入力ベクトル をウォルシュ関数(英語版) の重ね合わせ に分解する。
この変換はフランス の数学者 ジャック・アダマール 、ドイツ の数学者ハンス・ラーデマッヘル 、アメリカ合衆国 の数学者ジョセフ・L・ウォルシュ(英語版) にちなんで命名されている。
定義 アダマール変換 H n は 2n × 2n の行列である(規格化された)アダマール行列であり、2n 個の実数 x j を 2n 個の実数X k に変換する。アダマール変換は、再帰 的に、もしくは添え字 j 及び k の二進表現 を用いることによって定義される。
再帰的な定義は以下の通りである。まずアダマール変換 H 0 は 1 × 1 の単位行列 1である。そして n > 0 について H n を
H n = 1 2 ( H n − 1 H n − 1 H n − 1 − H n − 1 ) {\displaystyle 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 ⊗ H n − 1 = ⨂ i = 1 n H 1 {\displaystyle H_{n}=H_{1}\otimes H_{n-1}=\bigotimes _{i=1}^{n}H_{1}} と表すことができる。 従って、この規格化係数以外のアダマール行列は全て 1 と −1 で構成される。
あるいは別の表現として、アダマール行列の (j , k ) 成分を
( H n ) j + 1 , k + 1 = 1 2 n / 2 ( − 1 ) j ⋅ k {\displaystyle \left(H_{n}\right)_{j+1,k+1}={\frac {1}{2^{n/2}}}(-1)^{{\boldsymbol {j}}\cdot {\boldsymbol {k}}}} と定義することもできる。ただし j ⋅ k {\displaystyle {\boldsymbol {j}}\cdot {\boldsymbol {k}}} は数 j と k の二進 表現のビットごとの内積 (すなわちビット単位AND演算 のハミング重み )である。j を二進数の桁 ji (0 もしくは 1)で
j = ∑ i = 0 n − 1 j i 2 i = j n − 1 2 n − 1 + j n − 2 2 n − 2 + ⋯ + j 1 2 + j 0 {\displaystyle 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}} と表記すると
j ⋅ k = ∑ i = 0 n − 1 j i k i {\displaystyle {\boldsymbol {j}}\cdot {\boldsymbol {k}}=\sum _{i=0}^{n-1}j_{i}k_{i}} である。入力と出力を j i と k i で添字付けられた多次元配列とみなした際、これはユニタリ作用素 となるように規格化された 2 × 2 × ⋯ × 2 × 2 {\displaystyle 2\times 2\times \cdots \times 2\times 2} 次元DFTとなる。
アダマール行列のいくつかの例を以下に示す。
H 0 = ( 1 ) H 1 = 1 2 ( 1 1 1 − 1 ) {\displaystyle {\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 1 はサイズ2のDFTである。またZ /(2)の2要素の加法群上のフーリエ変換 とみなすことが出来る)
H 2 = 1 2 ( 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ) H 3 = 1 2 3 / 2 ( 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 ) {\displaystyle {\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 ⟩ {\displaystyle |0\rangle } と | 1 ⟩ {\displaystyle |1\rangle } から、 | 0 ⟩ {\displaystyle |0\rangle } と | 1 ⟩ {\displaystyle |1\rangle } の2つの重みが等しい重ね合わせへの写像である。普通その位相はディラックの記法 で
H = | 0 ⟩ + | 1 ⟩ 2 ⟨ 0 | + | 0 ⟩ − | 1 ⟩ 2 ⟨ 1 | {\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|} となるように選ばれる。 | 0 ⟩ {\displaystyle |0\rangle } と | 1 ⟩ {\displaystyle |1\rangle } を基底としたとき、これは変換行列
H 1 = 1 2 ( 1 1 1 − 1 ) {\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}} に対応する。
多くの量子アルゴリズム(英語版) はアダマール変換を初期化に利用している。m 個の | 0 ⟩ {\displaystyle |0\rangle } の量子ビットを、 | 0 ⟩ {\displaystyle |0\rangle } と | 1 ⟩ {\displaystyle |1\rangle } を基底とする n =2m 個の直交状態をすべて同じ重みで重ね合わせた状態に初期化する。
量子アダマール変換の計算は、各量子ビットに対してそれぞれアダマールゲートを適用するだけである。アダマール変換がテンソル積の構造を持つからである。このシンプルな結果が示すことは、量子アダマール変換は m =log n 回の演算しか要求しないということである。これに対して、古典的な場合は n log n の演算が必要である。
アダマールゲートによる演算 H ( | 1 ⟩ ) = 1 2 | 0 ⟩ − 1 2 | 1 ⟩ {\displaystyle H(|1\rangle )={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle } H ( | 0 ⟩ ) = 1 2 | 0 ⟩ + 1 2 | 1 ⟩ {\displaystyle H(|0\rangle )={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle } H ( 1 2 | 0 ⟩ + 1 2 | 1 ⟩ ) = 1 2 ( | 0 ⟩ + | 1 ⟩ ) + 1 2 ( | 0 ⟩ − | 1 ⟩ ) = | 0 ⟩ {\displaystyle 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 ( 1 2 | 0 ⟩ − 1 2 | 1 ⟩ ) = 1 2 ( | 0 ⟩ + | 1 ⟩ ) − 1 2 ( | 0 ⟩ − | 1 ⟩ ) = | 1 ⟩ {\displaystyle 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 ⟩ = [ 1 0 ] {\displaystyle |0\rangle ={\begin{bmatrix}1\\0\\\end{bmatrix}}} であり、ケット | 1 ⟩ = [ 0 1 ] {\displaystyle |1\rangle ={\begin{bmatrix}0\\1\\\end{bmatrix}}} である。
計算複雑性 アダマール変換は高速アダマール変換を用いると O ( n log n ) ( n = 2 m ) {\displaystyle 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. http://web.njit.edu/~akansu/PAPERS/Akansu-Poluri-WALSH-LIKE2007.pdf 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. http://www.nature.com/nmeth/journal/vaop/ncurrent/full/nmeth.3139.html 2015年4月27日 閲覧。 .
出典 ^ Compare Figure 1 in Townsend, W. J.; Thornton, M. A.. Walsh Spectrum Computations Using Cayley Graphs . CiteSeerx : 10.1.1.74.8029.