アダマール変換のソースを表示

{{distinguish|{{仮リンク|ウォルシュ行列|en|Walsh_matrix}}}}
{{参照方法|date=2019年3月}}
[[File:1010 0110 Walsh spectrum (single row).svg|thumb|300px| [[ブール関数]]と{{仮リンク|ウォルシュ行列|en|Walsh_matrix}}の[[行列の乗法|積]]は、その[[ウォルシュスペクトラム]]<ref>Compare Figure 1 in {{cite paper | id = {{citeseerx|10.1.1.74.8029}} | title = Walsh Spectrum Computations Using Cayley Graphs | first1 = W. J. | last1 = Townsend | first2 = M. A. | last2 = Thornton }}</ref>である。<br>(1,0,1,0,0,1,1,0) * H(8) = (4,2,0,−2,0,2,0,2)]]
[[File:1010 0110 Walsh spectrum (fast WHT).svg|thumb|300px|{{仮リンク|高速ウォルシュ-アダマール変換|en|Fast Walsh-Hadamard transform}}<br>これは(1,0,1,0,0,1,1,0)のウォルシュスペクトラムを早く計算するための方法である.]]
[[File:1010 0110 Walsh spectrum (polynomial).svg|thumb|300px|元の関数は多項式としてのウォルシュスペクトラムの平均によって表現することが出来る。]]
'''アダマール変換'''（{{lang-en|Hadamard transform}}、'''ウォルシュ–アダマール変換'''や'''アダマール–ラーデマッヘル–ウォルシュ変換''' {{lang-en|Hadamard–Rademacher–Walsh transform}}、'''ウォルシュ変換'''、'''ウォルシュ–フーリエ変換'''としても知られている）は、[[フーリエ変換]]の一般化の1つである。この変換は[[直交変換|直交]]かつ[[対称行列|対称]]かつ[[対合]]かつ[[線型写像|線形]]な写像であり、2<sup>''n''</sup>個の[[実数]]（もしくは[[複素数]]もしくは[[多元数]]）に作用する（しかし，アダマール行列自体は、純粋な実数行列である）。

アダマール変換はサイズ2の[[離散フーリエ変換]] (DFT) から構築されているとみなすことができ、実際、サイズが<math>2\times2\times\cdots\times2\times2</math>の多次元離散フーリエ変換と等価である。これは任意の入力[[ベクトル]]を{{仮リンク|ウォルシュ関数|en|Walsh_function}}の[[重ね合わせ]]に分解する。

この変換は[[フランス]]の[[数学者]][[ジャック・アダマール]]、[[ドイツ]]の数学者[[ハンス・ラーデマッヘル]]、[[アメリカ合衆国]]の数学者{{仮リンク|ジョセフ・L・ウォルシュ|en|Joseph_L._Walsh}}にちなんで命名されている。

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

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

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

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

:<math>H_n = H_{1} \otimes H_{n-1} = \bigotimes_{i=1}^{n} H_{1}</math>

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

あるいは別の表現として、アダマール行列の (''j'',&nbsp;''k'') 成分を

:<math>\left( H_n \right)_{j+1,k+1} = \frac{1}{2^{n/2}} (-1)^{\boldsymbol{j} \cdot \boldsymbol{k}}</math>

と定義することもできる。ただし<math> \boldsymbol{j} \cdot \boldsymbol{k} </math>は数 ''j'' と ''k'' の[[二進法|二進]]表現のビットごとの[[内積]]（すなわち[[ビット演算#AND|ビット単位AND演算]]の[[ハミング重み]]）である。''j'' を二進数の桁 ''j<sub>i</sub>''（0 もしくは 1）で

:<math>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</math>

と表記すると

:<math>\boldsymbol{j} \cdot \boldsymbol{k} = \sum_{i=0}^{n-1} j_i k_i</math>

である。入力と出力を ''j''<sub>''i''</sub> と ''k''<sub>''i''</sub> で添字付けられた多次元配列とみなした際、これは[[ユニタリ作用素]]となるように規格化された <math>2 \times 2 \times \cdots \times 2 \times 2</math> 次元DFTとなる。

アダマール行列のいくつかの例を以下に示す。
:<math>\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}</math>

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

:<math>\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}</math>

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

== 量子計算への応用 ==
[[量子情報科学]]では、アダマール変換は'''アダマールゲート'''（{{仮リンク|量子論理ゲート|en|Quantum_gate}}を参照のこと）とも呼ばれる。これは1つの[[量子ビット]]の回転であり、量子ビットの[[基底]]状態<math>|0 \rangle </math>と<math>|1 \rangle </math>から、<math>|0 \rangle </math>と<math>|1 \rangle </math>の2つの重みが等しい重ね合わせへの写像である。普通その位相は[[ディラックの記法]]で

:<math>H=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\langle0|+\frac{|0\rangle-|1\rangle}{\sqrt{2}}\langle1|</math>

となるように選ばれる。<math>|0 \rangle </math>と<math>|1 \rangle </math>を基底としたとき、これは変換行列

:<math>H_1=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}</math>

に対応する。
<!--　以下，未翻訳
in the <math>|0 \rangle , |1 \rangle </math> basis, also known as the [[computational basis]]. The states <math display="inline">\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt{2}}</math> and <math display="inline">\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt{2}}</math> are known as <math>\left|\boldsymbol{+}\right\rangle</math> and <math>\left|\boldsymbol{-}\right\rangle</math> respectively, and together constitute the [[polar basis]] in [[quantum computing]].-->

多くの{{仮リンク|量子アルゴリズム|en|Quantum_algorithm}}はアダマール変換を初期化に利用している。''m'' 個の<math>|0 \rangle </math>の量子ビットを、<math>|0 \rangle </math>と<math>|1 \rangle </math>を基底とする ''n''=2<sup>''m''</sup>個の直交状態をすべて同じ重みで重ね合わせた状態に初期化する。

量子アダマール変換の計算は、各量子ビットに対してそれぞれアダマールゲートを適用するだけである。アダマール変換がテンソル積の構造を持つからである。このシンプルな結果が示すことは、量子アダマール変換は ''m''=log ''n'' 回の演算しか要求しないということである。これに対して、古典的な場合は ''n'' log ''n'' の演算が必要である。

=== アダマールゲートによる演算 ===
:<math>H(|1\rangle) = \frac{1}{\sqrt{2}}|0\rangle-\frac{1}{\sqrt{2}}|1\rangle</math>

:<math>H(|0\rangle) = \frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle</math>

:<math>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</math>

:<math>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</math>

0または1のqubitにアダマールゲートを1回適用すると（上の最初の二つの式）、0と1が等しい確率で観測されるような量子ビットが生成される。これは、例えば表と裏が出る確率が同様に確からしいコインを投げるようなものである。しかし、もしアダマールゲートが2回続けて適用された場合（上の3番目と4番目の式）、最終的な状態は初期状態に等しくなる。

ケット<math> |0\rangle =  
  
   \begin{bmatrix}
      1  \\
      0 \\
     
   \end{bmatrix}
</math>
であり、ケット<math> |1\rangle =  
  
   \begin{bmatrix}
      0  \\
      1 \\
     
   \end{bmatrix}
</math>である。

== 計算複雑性 ==
アダマール変換は高速アダマール変換を用いると <math>O(n \operatorname{log}n) \quad (n=2^m)</math> である。

== 他分野への応用 ==
アダマール変換は[[暗号理論]]並びに多くの[[信号処理]]や[[JPEG XR]]、[[MPEG-4 AVC]]のような[[データ圧縮]][[アルゴリズム]]で用いられる。ビデオ圧縮アプリケーションでは、普通は絶対変換差で使用される。また、量子アルゴリズムにおける[[グローバーのアルゴリズム]]や[[ショアのアルゴリズム]]でも重要である。アダマール変換はまた[[核磁気共鳴]]や[[質量分析法]]、[[結晶学]]といったような科学的方法にも適用される。

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

== 関連項目 ==
* {{仮リンク|高速ウォルシュ–アダマール変換|en|Fast Walsh–Hadamard transform}}
* {{仮リンク|擬似アダマール変換|en|Pseudo-Hadamard transform}}
* {{仮リンク|ハール変換|en|Haar transform}}
* {{仮リンク|分配法則の一般化|en|Generalized distributive law}}

== 外部リンク ==
*{{cite web |first=Terry |last=Ritter |title=Walsh-Hadamard Transforms: A Literature Survey |date=August 1996|url=http://www.ciphersbyritter.com/RES/WALHAD.HTM|accessdate=2015-04-27}}
*{{cite journal |first1=A.N. |last1=Akansu |first2=R. |last2=Poluri |title=Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications |journal=IEEE Trans. on Signal Processing |volume=55 |issue=7 |pages=3800–6 |date=July 2007 |doi=10.1109/TSP.2007.894229  |url=http://web.njit.edu/~akansu/PAPERS/Akansu-Poluri-WALSH-LIKE2007.pdf |format=PDF|accessdate=2015-04-27}}
* Pan, Jeng-shyang [http://www.freepatentsonline.com/y2009/0136023.html Data Encryption Method Using Discrete Fractional Hadamard Transformation|accessdate=2015-04-27] (May 28, 2009)
*{{cite web |first1=Godfrey |last1=Beddard |first2=Briony A.|last2=Yorke |title=Pump-probe Spectroscopy using Hadamard Transforms |date=January 2011 |url=http://www1.chem.leeds.ac.uk/People/GSB/Hadamard_for_web.pdf |format=PDF|accessdate=2015-04-27}}
*{{cite journal |first1=Briony A. |last1=Yorke |first2=Godfrey |last2=Beddard |first3=Robin L. |last3=Owen |first4=Arwen R. |last4=Pearson| title= Time-resolved crystallography using the Hadamard transform |journal= Nature Methods |date=September 2014 |doi=10.1038/nmeth.3139  |url= http://www.nature.com/nmeth/journal/vaop/ncurrent/full/nmeth.3139.html |format=HTML|accessdate=2015-04-27}}

== 出典 ==
{{reflist}}

{{DEFAULTSORT:あたまるへんかん}}
[[Category:量子アルゴリズム]]
[[Category:変換 (数学)]]
[[Category:ジャック・アダマール]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]