アダマール変換

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動
ブール関数ウォルシュ行列英語版はそのウォルシュスペクトラム[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)のウォルシュスペクトラムを早く計算するための方法である.
元の関数は多項式としてのウォルシュスペクトラムの平均によって表現することが出来る。

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

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

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

定義[編集]

アダマール変換 Hm は 2m × 2m の行列である(正規化された)アダマール行列であり、2m 個の実数 xn を 2m 個の実数Xkに変換する。アダマール変換は、再帰的に、もしくは添え字 n 及び k二進表現を用いることによって定義される。

再帰的にはまず 1 × 1 のアダマール変換 H0単位行列 H0 = 1 によって定義する。その後 m > 0 のときの Hm

で定義する。ここで正規化係数 1/√2 はしばしば省略される。従って、この正規化係数以外のアダマール行列は全て 1 と −1 で構成される。

あるいは別の表現として、アダマール行列の (kn) 番目の要素を

と定義することもできる。ただし、kjnj はそれぞれ kn の2進表記の各桁(0 もしくは 1)であり、

を満たす。行列の一番左上の要素は k = n = 0 と定義されることに注意。入力と出力を njkj で添字付けられた多次元配列とみなした際、これはユニタリ作用素となるように正規化された 次元DFTとなる。

アダマール行列のいくつかの例を以下に示す。

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

ここでは数 ij の二進表現のビットごとの内積となる。例えば、ならば、

であり、(全体の定数を無視すれば)上記のアダマール行列に一致する。行列の最も左上の要素がであることに注意する必要がある。

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

量子計算への応用[編集]

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

となるように選ばれる。を基底としたとき、これは変換行列

に対応する。

多くの量子アルゴリズム英語版はアダマール変換を初期化に利用している。m 個のの量子ビットを、を基底とする n=2m個の直交状態をすべて同じ重みで重ね合わせた状態に初期化する。

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

アダマールゲートによる演算[編集]

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

ケット であり、ケットである。

計算複雑性[編集]

アダマール変換は高速アダマール変換を用いると である。

他分野への応用[編集]

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

学習上の参考になる図書や文献[編集]

  • 遠藤靖:「ウォルシュ解析」、東京電機大学出版局、ISBN 4-501-61340-8 (1993年11月10日)。

関連項目[編集]

外部リンク[編集]

出典[編集]

  1. ^ Compare Figure 1 in Townsend, W. J.; Thornton, M. A.. Walsh Spectrum Computations Using Cayley Graphs. CiteSeerx10.1.1.74.8029.