アダマール変換

アダマール変換（ウォルシュ・アダマール変換、アダマール・ラーデマッハ・ウォルシュ変換、ウォルシュ変換、ウォルシュ・フーリエ変換とも呼ばれる）は、一般化されたフーリエ変換の一例である。2 $m 個の$ 実数（または複素数、 $超$ 複素数とも呼ばれるが、アダマール行列自体は純実数である）に対して、直交、対称、反転、線形演算を行う。

アダマール変換はサイズ2の離散フーリエ変換（DFT）から構築されていると見なすことができ、実際にはサイズ $2 \times 2 \times \dots \times 2 \times 2$ の多次元DFTと同等です。^{[2]任意の入力ベクトルを}ウォルシュ関数の重ね合わせに分解します。

この変換は、フランスの数学者ジャック・アダマール（フランス語： [adamaʁ]）、ドイツ系アメリカ人の数学者ハンス・ラーデマッハー、およびアメリカの数学者ジョセフ・L・ウォルシュにちなんで名付けられました。

意味

アダマール変換H _mは、 2 ^m × 2 ^m行列（正規化係数でスケーリングされたアダマール行列）であり、2 ^{m 個の}実数x _{n を}2 ^{m 個}の実数X _kに変換します。アダマール変換は、再帰的に定義するか、インデックスnとkの2進数（基数-2）表現を用いて定義する2つの方法で定義できます。

再帰的に、1 × 1 アダマール変換H _0を恒等式 H ₀ = 1で定義し、次にm > 0の場合のH _{m を}次のように定義します。ここで、1/ √2は省略されることもある正規化です。 $H_{m}={\frac {1}{2^{m/2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}$

m > 1の場合、 H _{m は}次のように定義することもできます。ここで、はクロネッカー積を表します。したがって、この正規化係数を除けば、アダマール行列は 1 と −1 のみで構成されます。 $H_{m}=H_{1}\otimes H_{m-1}$ $\otimes$

同様に、アダマール行列をその( k , n )番目の要素で定義すると、 ${\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}$

ここで、k _jとn _jはそれぞれkとnのビット要素（0または1）です。左上隅の要素については、次のように定義します。この場合、次の式が成り立ちます。 $k=n=0$ $(H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}$

入力と出力がそれぞれn _jとk _jでインデックス付けされた多次元配列とみなされる場合、これはまさにユニタリに正規化された多次元 DFT です。 ${\textstyle 2\times 2\times \cdots \times 2\times 2}$

アダマール行列の例をいくつか示します。ここでは、数値 i と j の2進表現のビット単位のドット積です。例えばの場合、となり、これは上記と一致します（全体の定数は無視します）。行列の最初の行、最初の列の要素はで表されることに注意してください。 ${\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\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}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}$ $i\cdot j$ ${\textstyle n\;\geq \;2}$ $(H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1$ ${\textstyle (H_{n})_{0,0}}$

H ₁はまさにサイズ2のDFTである。これはZ /(2) の2元加法群上のフーリエ変換とみなすこともできる。

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

ウォルシュ・アダマール変換の利点

本物

上記の行列Hの定義に従って、ここではH = H [ m , n ] とします。 $H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$

ウォルシュ変換では、行列には1と-1のみが現れます。1と-1は実数なので、複素数計算を行う必要はありません。

掛け算は不要

DFTでは無理数乗算が必要ですが、アダマール変換では必要ありません。有理数乗算も不要で、符号反転だけで済みます。

いくつかの特性はDFTの特性と似ている

ウォルシュ変換行列では、各行と各列はウォルシュ関数であり、符号の変化の回数は連続的に増加します。つまり、最初の行と最初の列では符号の変化はゼロです（すべての要素が1に等しい）。2行目と3列目では符号の変化が1回、3行目では符号の変化が2回、というように続きます。これを、各行 $iに$ ゼロ交差が含まれる離散フーリエ変換と比較してください。 $H[m,n]=\left({\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}}\right)$ ${\textstyle e^{-j2\pi mn/N}}$ ${\textstyle i-1}$

離散フーリエ変換では、 $m が$ 0 に等しい場合 (最初の行に対応)、結果も 1 になります。後続の行では、信号周波数が最初の生の行列では低く始まり、最後の行まで次の行に向かって増加するという行列の特性が見られます。

フーリエ変換との関係

アダマール変換は実際には $2\times2\times\dots\times2\times2$ の多次元DFTと同等である。^[2]

別のアプローチは、アダマール変換をブール群上のフーリエ変換と見なすものである。^[3]^[4]有限（アーベル）群上のフーリエ変換を用いると、関数のフーリエ変換はによって定義される関数となる。ここではの指標である。各指標はに対しての形を持ち、乗算はビット列上のブール内積である。したがって、への入力をと同一視することができ（ポンチャギン双対性）、によって定義される。 $(\mathbb {Z} /2\mathbb {Z} )^{n}$ $f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C}$ ${\widehat {f}}$ ${\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)$ $\chi$ $(\mathbb {Z} /2\mathbb {Z} )^{n}$ $\chi _{r}(a)=(-1)^{a\cdot r}$ $r\in (\mathbb {Z} /2\mathbb {Z} )^{n}$ ${\widehat {f}}$ $r\in (\mathbb {Z} /2\mathbb {Z} )^{n}$ ${\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C}$ ${\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}$

これは、とへの入力をブール文字列と見なしたのアダマール変換です。 $f$ $f$ ${\widehat {f}}$

上記の定式化において、アダマール変換は左側の複素数ベクトルをアダマール行列で乗算するものですが、をの要素のインデックスに対応するビット文字列を入力として取り、の対応する要素を出力することで、同等性がわかります。 $2^{n}$ $v$ $H_{n}$ $f$ $v$ $f$ $v$

これを、複素数のベクトルに適用するときに巡回群の指標を使用する通常の離散フーリエ変換と比較してください。 $v$ $2^{n}$ $\mathbb {Z} /2^{n}\mathbb {Z}$

計算の複雑さ

古典的領域では、高速アダマール変換アルゴリズムを使用して、アダマール変換を演算（）で計算できます。 $n\log n$ $n=2^{m}$

量子領域では、アダマール変換は並列化できる量子論理ゲートであるため、時間内に計算できます。 $O(1)$

量子コンピューティングの応用

アダマール変換は量子コンピューティングにおいて広く用いられている。2×2アダマール変換はアダマールゲートとして知られる量子論理ゲートであり、 -量子ビットレジスタの各量子ビットに並列にアダマールゲートを適用することは、アダマール変換と同等である。 $H_{1}$ $n$ $H_{n}$

アダマール門

量子計算において、アダマールゲートは1量子ビットの回転であり、量子ビット基底状態とを、計算基底状態とに等しい重みを持つ2つの重ね合わせ状態にマッピングする。通常、位相は次のように選択される。 $|0\rangle$ $|1\rangle$ $|0\rangle$ $|1\rangle$ $H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|$

ディラック記法で表されます。これは、計算基底とも呼ばれる基底の変換行列に対応します。状態とはそれぞれととして知られ、量子コンピューティングにおける極基底を構成します。 $H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$ $|0\rangle ,|1\rangle$ ${\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}$ ${\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}$ $\left|{\boldsymbol {+}}\right\rangle$ $\left|{\boldsymbol {-}}\right\rangle$

アダマールゲート演算

${\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}$

0または1の量子ビットにアダマールゲートを1回適用すると、観測された場合、0または1が等しい確率で得られる量子状態が生成されます（最初の2つの操作で見られるように）。これは、標準的な確率計算モデルにおいて、公平なコインを投げるのと全く同じです。しかし、アダマールゲートを2回連続して適用した場合（最後の2つの操作で実際に行われているように）、最終状態は常に初期状態と同じになります。

量子アルゴリズムにおけるアダマール変換

量子アダマール変換の計算は、アダマール変換のテンソル積構造のため、各量子ビットに個別にアダマールゲートを適用するだけです。この単純な結果は、量子アダマール変換は、古典的な演算の場合と比較して、演算を必要とすることを意味します。 $\log _{2}N$ $N\log _{2}N$

量子ビット系では、各量子ビット（それぞれに初期化されている）に作用するアダマールゲートは、がの形をとるときに均一な量子重ね合わせ状態を準備するために用いられる。この場合、量子ビットの場合、複合アダマールゲートはアダマールゲートのテンソル積として表される。 $n$ $n$ $|0\rangle$ $N$ $N=2^{n}$ $n$ $H_{n}$ $n$ $H_{n}=\underbrace {H\otimes H\otimes \ldots \otimes H} _{n{\text{ times}}}$

結果として得られる均一な量子重ね合わせ状態は次のようになる。これは、任意のに対してアダマールゲートを用いた均一な量子状態の作成を一般化したものである。^[5] $H_{n}|0\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle$ $N=2^{n}$

この均一な量子状態を測定すると、～の間のランダム状態が得られます。 $|0\rangle$ $|N-1\rangle$

多くの量子アルゴリズムは、アダマール変換を初期ステップとして用います。これは、前述のように、アダマール変換は、で初期化されたn個の量子ビットを、等しい重みを持つ基底のすべての 2 ⁿ個の直交状態の重ね合わせにマッピングするためです。例えば、これはDeutsch–Jozsa アルゴリズム、Simon のアルゴリズム、Bernstein–Vazirani アルゴリズム、Grover のアルゴリズムで使用されています。Shorのアルゴリズムは、初期アダマール変換と量子フーリエ変換の両方を使用することに注意してください。これらはどちらも有限群上のフーリエ変換の一種で、前者は上、後者は上です。 $|0\rangle$ $|0\rangle ,|1\rangle$ $(\mathbb {Z} /2\mathbb {Z} )^{n}$ $\mathbb {Z} /2^{n}\mathbb {Z}$

≠ である一般的な場合における均一な量子重ね合わせ状態の準備は非自明であり、より多くの作業を必要とする。ゲート複雑度と回路深度が全てに対してのみであるような、重ね合わせ状態を準備するための効率的かつ決定論的なアプローチが最近発表された^[6] 。このアプローチに必要なのは量子ビットのみである。重要なのは、このアプローチでは均一な重ね合わせ状態を作成するために、補助量子ビットや複数の制御を持つ量子ゲートは必要ないということである。 $N$ $2^{n}$ $|\Psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}|j\rangle$ $O(\log _{2}N)$ $N$ $n=\lceil \log _{2}N\rceil$ $|\Psi \rangle$

分子系統学（進化生物学）の応用

アダマール変換は、分子データから系統樹を推定するために用いることができる。^[7]^[8]^[9] 系統学は、生物間の関係を理解することに焦点を当てた進化生物学の分野である。DNA多重配列アライメントから得られた部位パターン頻度のベクトル（または行列）にアダマール変換を適用すると、系統樹のトポロジーに関する情報を含む別のベクトルを生成することができる。系統樹アダマール変換の可逆性により、系統樹のトポロジーベクトルから部位尤度を計算することも可能となり、アダマール変換を用いて系統樹の最大尤度推定を行うことができる。しかし、後者の応用は、部位パターンベクトルから系統樹ベクトルへの変換ほど有用ではない。なぜなら、部位尤度を計算する他の方法^[10]^[11]の方がはるかに効率的だからである。しかし、系統樹アダマール変換の可逆性は、数理系統学にとって優れたツールを提供する。^[12]^[13]

系統学的アダマール変換の仕組みには、サイトパターンベクトルまたは行列を使用してツリーのトポロジと枝の長さに関する情報を提供するベクトルの計算が含まれます。 $\gamma (T)$ $T$ $s(T)$

$\gamma (T)=H^{-1}(\ln(Hs(T)))$ ここで、適切なサイズのアダマール行列です。この式は、解釈を簡略化するために、3つの式を連ねた式として書き直すことができます。 $H$

${\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}$

この方程式の可逆性により、次のようにして予想されるサイトパターンベクトル (または行列) を計算できます。

$s(T)=H^{-1}(\exp(H\gamma (T)))$

DNAのCavender-Farris- Neyman（CFN）二状態置換モデルでは、ヌクレオチドをバイナリ文字（プリンAとGはR、ピリミジンCとTはY）としてエンコードすることで使用できます。これにより、多重配列アライメントをサイトパターンベクトルとしてエンコードし、これをツリーベクトルに変換することが可能になります。次の例をご覧ください。 $s(T)$ $\gamma (T)$

特定の木のアダマール変換を示す例（実例の値はWaddell et al. 1997 ^[14]から改変）
索引	バイナリパターン	配置パターン	$\gamma (T)$	$\rho =H^{-1}\gamma (T)$	$r=\exp(\rho )$	$s(T)=H^{-1}\rho$
0	0000	RRRRとYYYY	−0.475	0	1	0.6479
1	0001	RRRYとYYYR	0.2	−0.5	0.6065	0.1283
2	0010	RRYR と YYRY	0.025	−0.15	0.8607	0.02
3*	0011	RRYYとYYRR	0.025	−0.45	0.6376	0.0226
4	0100	RYRRとYRYY	0.2	−0.45	0.6376	0.1283
5*	0101	RYRYとYRYR	0	−0.85	0.4274	0.0258
6*	0110	RYYRとYRRY	0	−0.5	0.6065	0.0070
7	0111	RYYYとYRRR	0.025	−0.9	0.4066	0.02

この表に示す例では、簡略化された 3 つの方程式スキームを使用しており、これは 4 つの分類群のツリーに対するもので、newick 形式では ((A,B),(C,D)); と記述できます。サイトパターンは ABCD の順序で記述されます。この特定のツリーには、2 つの長い末端分岐 (サイトあたり 0.2 個のトランスバージョン置換)、2 つの短い末端分岐 (サイトあたり 0.025 個のトランスバージョン置換)、および 1 つの短い内部分岐 (サイトあたり 0.025 個のトランスバージョン置換) があるため、newick 形式では ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)); と記述されます。このツリーは、データが最大節約基準を使用して分析された場合に長い分岐の魅力を示します(分析された配列が、観測されたサイトパターン頻度が列に示されている予測頻度に近くなるように十分に長いと想定)。長い枝の吸引力は、インデックス6を持つサイトパターン（ツリー((A,C),(B,D));を支持する）の期待数が、真のツリー（インデックス4）を支持するサイトパターンの期待数を超えているという事実を反映している。系統的アダマール変換の可逆性は、明らかに、ツリーベクトルが正しいツリーに対応することを意味することを意味する。したがって、変換後の節約分析は統計的に一貫しており、^[15]正しいモデル（この場合はCFNモデル）を用いた標準的な最尤分析と同様に一致する。 $s(T)=H^{-1}\rho$ $\gamma (T)$

0のサイトパターンは、ヌクレオチドをプリンまたはピリミジンとしてエンコードした後、変化していないサイトに対応することに注意してください。アスタリスク付きのインデックス（3、5、6）は「簡略化情報」であり、残りのインデックスは、1つの分類群が他の3つの分類群と異なるサイトパターンを表します（したがって、標準的な最尤系統樹における末端の枝の長さに相当します）。

ヌクレオチドデータをRとY（そして最終的には0と1）として再コード化せずに使用したい場合は、部位パターンを行列としてコード化することができます。4分類群のツリーを考えると、合計256の部位パターン（4ヌクレオチドの4乗）があります。しかし、キムラの3パラメータ（またはK81）モデルの対称性により、DNAの256の可能な部位パターンを64パターンに減らすことができ、4分類群のツリーのヌクレオチドデータを、上記の転座（RY）部位パターンに使用した8要素のベクトルと同様の方法で、8×8行列^{[16]としてコード化することができます。これは}、クラインの4群を使用してデータを再コード化することで実現されます。

系統発生アダマール変換のためのクラインの4群コーディング
ヌクレオチド1	ヌクレオチド2	ヌクレオチド3	ヌクレオチド4
A (0,0)	G (1,0)	C (0,1)	T（1,1）
C (0,0)	T (1,0)	A (0,1)	G (1,1)
G (0,0)	A (1,0)	0,1	C (1,1)
T (0,0)	C (1,0)	G (0,1)	ア（1,1）

RYデータと同様に、サイトパターンは任意に選択された最初の分類群の塩基を基準にインデックス付けされ、後続の分類群の塩基はその最初の塩基を基準にエンコードされます。したがって、最初の分類群はビットペア(0,0)を受け取ります。これらのビットペアを用いて、RYベクトルに類似した2つのベクトルを作成し、それらのベクトルを用いてマトリックスを構築することができます。これは、4つの霊長類ヘモグロビン擬遺伝子の多重配列アライメントに基づくHendy et al. (1994) ^[16]の例を用いて説明できます。

エンコードされた配列アラインメントの例（Hendy et al. 1994 ^[16]より）（値は9879サイト中のカウント）
	0	8	16	24	32	56
0	8988	9	10	12	24	90
1	41	9		**
2	45		13
3	54*			14		3
4	94				20
5			1
6	2				2
7	356		1		1	75

列 0 のサイトパターンの数が非常に多いのは、列 0 がトランジション差異に対応し、実質的にすべてのゲノム領域の比較においてトランスバージョン差異よりも急速に蓄積する (そしてこの実例で使用したヘモグロビン擬遺伝子では確実により急速に蓄積する^[17] ) という事実を反映している。サイトパターン AAGG を考えてみると、クラインのグループのビットペアの 2 番目の要素がバイナリパターン 0000、最初の要素が 0011 になる。この場合、最初の要素に基づくバイナリパターンでは、最初の要素はインデックス 3 に対応する (したがって、列 0 の行 3。表では 1 つのアスタリスクで示される)。サイトパターン GGAA、CCTT、および TTCC はまったく同じ方法でエンコードされる。サイトパターン AACT は、2 番目の要素に基づいてバイナリパターン 0011 でエンコードされ、最初の要素に基づいて 0001 でエンコードされ、これにより、最初の要素のインデックスは 1、2 番目の要素のインデックスは 3 になる。 2 番目のクラインのグループのビットペアに基づくインデックスに 8 を掛けて列インデックスを生成します (この場合は列 24 になります)。AACT サイトパターンの数を含むセルは 2 つのアスタリスクで示されます。ただし、例に数字がないことは、シーケンスアラインメントに AACT サイトパターンが含まれていないことを示します (同様に、同じ方法でエンコードされる CCAG、GGTC、および TTGA サイトパターンも存在しません)。

その他のアプリケーション

アダマール変換は、データ暗号化だけでなく、JPEG XRやMPEG-4 AVCといった多くの信号処理・データ圧縮アルゴリズムにも用いられています。ビデオ圧縮アプリケーションでは、通常、変換された差分の絶対値和の形で用いられます。また、量子コンピューティングにおける多くのアルゴリズムの重要な部分でもあります。アダマール変換は、NMR、質量分析、結晶構造解析といった実験技術にも応用されています。さらに、局所性に敏感なハッシュ法のいくつかのバージョンでは、擬似ランダムな行列回転を得るために用いられています。

参照

外部リンク

リッター、テリー（1996年8月）「ウォルシュ・アダマール変換：文献概説」
Akansu, Ali N. ; Poluri, R. (2007年7月). 「直接拡散CDMA通信におけるウォルシュ型非線形位相直交符号」(PDF) . IEEE Transactions on Signal Processing . 55 (7): 3800–6 . Bibcode :2007ITSP...55.3800A. doi :10.1109/TSP.2007.894229. S2CID 6830633.
Pan, Jeng-shyang 離散フラクショナルアダマール変換を使用したデータ暗号化手法 (2009 年 5 月 28 日)
ラコヴィッツ、パウェル博士。ウォルシュ・アダマール変換と金融収益系列のランダム性検定（2015年4月7日）
Beddard, Godfrey; Yorke, Briony A. (2011年1月). 「アダマール変換を用いたポンプ・プローブ分光法」(PDF) . 2014年10月18日時点のオリジナル(PDF)からアーカイブ。 2012年4月28日閲覧。
Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (2014年9月). 「アダマール変換を用いた時間分解結晶構造解析」. Nature Methods . 11 (11): 1131– 1134. doi :10.1038/nmeth.3139. PMC 4216935. PMID 25282611 .

参考文献

^ Townsend , WJ; Thornton, MA (2001). "Walsh spectrum computes using Cayley graphs". Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001) . MWSCAS-01. Vol. 1. IEEE. pp. 110– 113. doi :10.1109/mwscas.2001.986127. ISBN 97844222223 ... 0-7803-7150-X。
^ ab Kunz, HO (1979). 「1次元離散ウォルシュ・アダマール変換と多次元離散フーリエ変換の等価性について」. IEEE Transactions on Computers . 28 (3): 267–8 . doi :10.1109/TC.1979.1675334. S2CID 206621901.
^ ブール写像のフーリエ解析–チュートリアル–、pp. 12–13
^ 講義5：基本的な量子アルゴリズム、ラジャット・ミッタル、pp.4～5
^ ニールセン、マイケル・A. ;チュアン、アイザック(2010). 『量子計算と量子情報』ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-1-10700-217-3. OCLC 43641333。
^ Alok ShuklaとPrakash Vedula (2024). 「均一な量子重ね合わせ状態の準備のための効率的な量子アルゴリズム」.量子情報処理. 23:38 (1): 38. arXiv : 2306.11747 . Bibcode :2024QuIP...23...38S. doi :10.1007/s11128-024-04258-4.
^ ヘンディ, マイケル・D.; ペニー, デイヴィッド (1989年12月). 「進化樹の定量的研究のための枠組み」 .系統動物学. 38 (4): 297. doi :10.2307/2992396. JSTOR 2992396.
^ Hendy, Michael D.; Penny, David (1993年1月). 「系統発生データのスペクトル解析」 . Journal of Classification . 10 (1): 5– 24. doi :10.1007/BF02638451. ISSN 0176-4268. S2CID 122466038.
^ Székely, LA, Erdős, PL, Steel, MA, & Penny, D. (1993). 進化樹のためのフーリエ反転公式.応用数学レターズ, 6 (2), 13–16.
^ Felsenstein, Joseph (1981年11月). 「DNA配列からの進化樹形図：最大尤度法」 . Journal of Molecular Evolution . 17 (6): 368– 376. Bibcode :1981JMolE..17..368F. doi :10.1007/BF01734359. ISSN 0022-2844. PMID 7288891. S2CID 8024924.
^ Stamatakis, Alexandros (2019), Warnow, Tandy (ed.), 「系統学的尤度計算の最適化のためのアプローチのレビュー」 , Bioinformatics and Phylogenetics , Computational Biology, vol. 29, Cham: Springer International Publishing, pp. 1– 19, doi :10.1007/978-3-030-10837-3_1, ISBN 978-3-030-10836-6, S2CID 145834168 , 2020年10月10日取得
^ Chor, Benny ; Hendy, Michael D. ; Holland, Barbara R. ; Penny, David (2000-10-01). 「系統樹における複数の尤度最大値：解析的アプローチ」. Molecular Biology and Evolution . 17 (10): 1529– 1541. doi : 10.1093/oxfordjournals.molbev.a026252 . ISSN 1537-1719. PMID 11018159.
^ Matsen, Frederick A.; Steel, Mike (2007-10-01). Ané, Cécile ; Sullivan, Jack (編). 「単一系統樹上の系統発生的混合は、別のトポロジーの系統樹を模倣することができる」. Systematic Biology . 56 (5): 767– 775. arXiv : 0704.2260 . doi : 10.1080/10635150701627304 . ISSN 1076-836X. PMID 17886146.
^ Waddell, Peter J; Steel, MA (1997年12月). 「サイト間で不等な速度を持つ一般的な時間可逆距離：不変サイトにおけるΓ分布と逆ガウス分布の混合」. Molecular Phylogenetics and Evolution . 8 (3): 398– 414. Bibcode :1997MolPE...8..398W. doi :10.1006/mpev.1997.0452. PMID 9417897.
^ Steel, MA; Hendy, MD; Penny, D. (1993-12-01). 「倹約は一貫性を持つ！」 . Systematic Biology . 42 (4): 581– 587. doi :10.1093/sysbio/42.4.581. ISSN 1063-5157.
^ abc Hendy, MD; Penny, D.; Steel, MA (1994-04-12). 「進化樹の離散フーリエ解析」. Proceedings of the National Academy of Sciences . 91 (8): 3339– 3343. Bibcode :1994PNAS...91.3339H. doi : 10.1073/pnas.91.8.3339 . ISSN 0027-8424. PMC 43572. PMID 8159749 .
^ Miyamoto, MM; Koop, BF; Slightom, JL; Goodman, M.; Tennant, MR (1988-10-01). 「高等霊長類の分子系統学：系譜関係と分類」. Proceedings of the National Academy of Sciences . 85 (20): 7627– 7631. Bibcode :1988PNAS...85.7627M. doi : 10.1073/pnas.85.20.7627 . ISSN 0027-8424. PMC 282245. PMID 3174657 .

[1] Townsend , WJ; Thornton, MA (2001). "Walsh spectrum computes using Cayley graphs". Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001) . MWSCAS-01. Vol. 1. IEEE. pp. 110– 113. doi :10.1109/mwscas.2001.986127. ISBN 97844222223 ... 0-7803-7150-X。

[kunz-2] Kunz, HO (1979). 「1次元離散ウォルシュ・アダマール変換と多次元離散フーリエ変換の等価性について」. IEEE Transactions on Computers . 28 (3): 267–8 . doi :10.1109/TC.1979.1675334. S2CID 206621901.

[3] ブール写像のフーリエ解析–チュートリアル–、pp. 12–13

[4] 講義5：基本的な量子アルゴリズム、ラジャット・ミッタル、pp.4～5

[Nielsen-Chuang-5] ニールセン、マイケル・A. ;チュアン、アイザック(2010). 『量子計算と量子情報』ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-1-10700-217-3. OCLC 43641333。

[shukla2024efficient-6] Alok ShuklaとPrakash Vedula (2024). 「均一な量子重ね合わせ状態の準備のための効率的な量子アルゴリズム」.量子情報処理. 23:38 (1): 38. arXiv : 2306.11747 . Bibcode :2024QuIP...23...38S. doi :10.1007/s11128-024-04258-4.

[7] ヘンディ, マイケル・D.; ペニー, デイヴィッド (1989年12月). 「進化樹の定量的研究のための枠組み」 .系統動物学. 38 (4): 297. doi :10.2307/2992396. JSTOR 2992396.

[8] Hendy, Michael D.; Penny, David (1993年1月). 「系統発生データのスペクトル解析」 . Journal of Classification . 10 (1): 5– 24. doi :10.1007/BF02638451. ISSN 0176-4268. S2CID 122466038.

[9] Székely, LA, Erdős, PL, Steel, MA, & Penny, D. (1993). 進化樹のためのフーリエ反転公式.応用数学レターズ, 6 (2), 13–16.

[10] Felsenstein, Joseph (1981年11月). 「DNA配列からの進化樹形図：最大尤度法」 . Journal of Molecular Evolution . 17 (6): 368– 376. Bibcode :1981JMolE..17..368F. doi :10.1007/BF01734359. ISSN 0022-2844. PMID 7288891. S2CID 8024924.

[11] Stamatakis, Alexandros (2019), Warnow, Tandy (ed.), 「系統学的尤度計算の最適化のためのアプローチのレビュー」 , Bioinformatics and Phylogenetics , Computational Biology, vol. 29, Cham: Springer International Publishing, pp. 1– 19, doi :10.1007/978-3-030-10837-3_1, ISBN 978-3-030-10836-6, S2CID 145834168 , 2020年10月10日取得

[12] Chor, Benny ; Hendy, Michael D. ; Holland, Barbara R. ; Penny, David (2000-10-01). 「系統樹における複数の尤度最大値：解析的アプローチ」. Molecular Biology and Evolution . 17 (10): 1529– 1541. doi : 10.1093/oxfordjournals.molbev.a026252 . ISSN 1537-1719. PMID 11018159.

[13] Matsen, Frederick A.; Steel, Mike (2007-10-01). Ané, Cécile ; Sullivan, Jack (編). 「単一系統樹上の系統発生的混合は、別のトポロジーの系統樹を模倣することができる」. Systematic Biology . 56 (5): 767– 775. arXiv : 0704.2260 . doi : 10.1080/10635150701627304 . ISSN 1076-836X. PMID 17886146.

[14] Waddell, Peter J; Steel, MA (1997年12月). 「サイト間で不等な速度を持つ一般的な時間可逆距離：不変サイトにおけるΓ分布と逆ガウス分布の混合」. Molecular Phylogenetics and Evolution . 8 (3): 398– 414. Bibcode :1997MolPE...8..398W. doi :10.1006/mpev.1997.0452. PMID 9417897.

[15] Steel, MA; Hendy, MD; Penny, D. (1993-12-01). 「倹約は一貫性を持つ！」 . Systematic Biology . 42 (4): 581– 587. doi :10.1093/sysbio/42.4.581. ISSN 1063-5157.

[:0-16] Hendy, MD; Penny, D.; Steel, MA (1994-04-12). 「進化樹の離散フーリエ解析」. Proceedings of the National Academy of Sciences . 91 (8): 3339– 3343. Bibcode :1994PNAS...91.3339H. doi : 10.1073/pnas.91.8.3339 . ISSN 0027-8424. PMC 43572. PMID 8159749 .

[17] Miyamoto, MM; Koop, BF; Slightom, JL; Goodman, M.; Tennant, MR (1988-10-01). 「高等霊長類の分子系統学：系譜関係と分類」. Proceedings of the National Academy of Sciences . 85 (20): 7627– 7631. Bibcode :1988PNAS...85.7627M. doi : 10.1073/pnas.85.20.7627 . ISSN 0027-8424. PMC 282245. PMID 3174657 .