아다마르 변환 문서 원본 보기

[[파일:1010 0110 Walsh spectrum (single row).svg|섬네일|300px|[[행렬 곱셈|행렬 곱]]과 [[불 함수]] 및 [[아다마르 행렬]]의 [[월시 스펙트럼]]:<ref>Compare Figure 1 in {{콘퍼런스 인용
 | last1 = Townsend | first1 = W.J.
 | last2 = Thornton | first2 = M.A.
 | contribution = Walsh spectrum computations using Cayley graphs
 | doi = 10.1109/mwscas.2001.986127
 | publisher = IEEE
 | series = MWSCAS-01
 | title = Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001)| date = 2001
 | volume = 1
 | pages = 110–113
 | isbn = 0-7803-7150-X
 }}</ref><br>(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)]]
[[파일:1010 0110 Walsh spectrum (fast WHT).svg|섬네일|300px|(1, 0, 1, 0, 0, 1, 1, 0)의 월시 스펙트럼을 계산하는 더 빠른 방법인 [[고속 월시-아다마르 변환]]]]
[[파일:1010 0110 Walsh spectrum (polynomial).svg|섬네일|300px|원래 함수는 월시 스펙트럼을 통해 산술 다항식으로 표현될 수 있다.]]
'''아다마르 변환'''({{llang|en|Hadamard transform}}, '''월시-아다마르 변환'''(Walsh–Hadamard transform), '''아다마르-라데마허-월시 변환'''(Hadamard–Rademacher–Walsh transform), '''월시 변환'''(Walsh transform), 또는 '''월시-푸리에 변환'''(Walsh–Fourier transform)이라고도 함)은 일반화된 [[푸리에 변환]]의 한 예시이다. 이는 {{수학|2<sup>m</sup>}}개의 [[실수]] (또는 [[복소수]] 또는 초복소수)에 대해 [[직교행렬|직교]], [[대칭행렬|대칭]], [[대합 (수학)|대합적]], [[선형 작용소|선형 연산]]을 수행한다 (아다마르 행렬 자체는 순수하게 실수이다).

아다마르 변환은 크기 2의 [[이산 푸리에 변환]](DFT)으로 구성된 것으로 간주될 수 있으며, 실제로는 {{수학|2 × 2 × ⋯ × 2 × 2}} 크기의 다차원 DFT와 동일하다.<ref name="kunz"/> 이는 임의의 입력 벡터를 [[월시 함수]]의 중첩으로 분해한다.

이 변환은 [[프랑스]]의 [[수학자]]인 [[자크 아다마르]]({{IPA-fr|adamaʁ|lang}}), 독일계 미국인 수학자 [[한스 라데마허]], 그리고 미국인 수학자 [[조세프 월시]]의 이름을 따서 명명되었다.

== 정의 ==
아다마르 변환 H<sub>m</sub>은 2<sup>m</sup>&nbsp;×&nbsp;2<sup>m</sup> 행렬인 [[아다마르 행렬]](정규화 인자로 스케일링됨)로, 2<sup>m</sup>개의 실수 x<sub>n</sub>을 2<sup>m</sup>개의 실수 X<sub>k</sub>로 변환한다. 아다마르 변환은 두 가지 방식으로 정의될 수 있다: [[재귀적으로]] 정의하거나, 인덱스 n과 k의 [[이진법|이진]] ([[밑 (수학)|기수]]-2) 표현을 사용하여 정의한다.

재귀적으로, 우리는 1&nbsp;×&nbsp;1 아다마르 변환 H<sub>0</sub>를 [[단위 행렬|단위]] H<sub>0</sub> = 1로 정의하고, m&nbsp;>&nbsp;0에 대해 H<sub>m</sub>을 다음과 같이 정의한다:
<math display="block">H_m = \frac{1}{\sqrt2} \begin{pmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{pmatrix}</math>
여기서 1/{{제곱근|2}}는 때때로 생략되는 정규화 요소이다.

m&nbsp;>&nbsp;1의 경우, H<sub>m</sub>은 다음과 같이 정의될 수도 있다:
<math display="block">H_m = H_{1} \otimes H_{m-1}</math>
여기서 <math> \otimes </math>는 [[크로네커 곱]]을 나타낸다. 따라서, 이 정규화 인자를 제외하면, 아다마르 행렬은 완전히 1과 −1로 구성된다.

동등하게, 아다마르 행렬은 (k,&nbsp;n)-번째 항목을 다음과 같이 정의할 수 있다:
<math display="block">\begin{align}
  k &= \sum^{m-1}_{i=0} {k_i 2^i} = k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \dots + k_1 2 + k_0 \\
  n &= \sum^{m-1}_{i=0} {n_i 2^i} = n_{m-1} 2^{m-1} + n_{m-2} 2^{m-2} + \dots + n_1 2 + n_0
\end{align}</math>

여기서 k<sub>j</sub>와 n<sub>j</sub>는 각각 k와 n의 비트 요소(0 또는 1)이다. 왼쪽 상단 모서리의 요소에 대해 <math>k = n = 0</math>으로 정의한다. 이 경우, 다음이 성립한다:
<math display="block"> (H_m)_{k,n} = \frac{1}{2^{m/2}} (-1)^{\sum_j k_j n_j}</math>

이는 입력과 출력을 각각 n<sub>j</sub>와 k<sub>j</sub>로 인덱싱된 다차원 배열로 간주할 때, 정확히 <math display=inline> 2 \times 2 \times \cdots \times 2 \times 2</math>의 다차원 DFT이며, [[유니터리 작용소|유니터리]]가 되도록 정규화되었다.

아다마르 행렬의 몇 가지 예시는 다음과 같다.
<math display="block">
\begin{align}
  H_0 & = +\begin{pmatrix}1\end{pmatrix}\\[5pt]
  H_1 & = \frac{1}{\sqrt2}
            \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{align}
</math>
여기서 <math> i \cdot j </math>는 i와 j의 이진 표현의 비트 단위 [[스칼라곱]]이다. 예를 들어, <math display="inline"> n \;\geq\; 2</math>인 경우, <math display="block"> (H_n)_{3,2} \;=\;  (-1)^{3 \cdot 2} \;=\; (-1)^{(1,1) \cdot (1,0)} \;=\; (-1)^{1+0} \;=\; (-1)^1 \;=\; -1</math>이 되며, 이는 위 결과와 일치한다(전체 상수 무시). 행렬의 첫 번째 행, 첫 번째 열 요소는 <math display="inline"> (H_n)_{0,0} </math>으로 표시된다.

H<sub>1</sub>은 정확히 크기 2의 DFT이다. 이는 또한 '''Z'''/(2)의 두 요소 덧셈 그룹에 대한 [[푸리에 변환]]으로 간주될 수 있다.

아다마르 행렬의 행은 [[월시 함수]]이다.

== 월시-아다마르 변환의 장점 ==
=== 실수 ===
행렬 H의 위 정의에 따르면, 여기서 H = H[m,n]으로 둔다.
<math display="block">H[m,n]=\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}</math>

월시 변환에서는 행렬에 1과 -1만 나타난다. 1과 -1은 실수이므로 [[복소수]] 계산을 수행할 필요가 없다.

=== 곱셈이 필요 없음 ===
DFT는 무리수 곱셈이 필요한 반면, 아다마르 변환은 그렇지 않다. 부호 반전만으로 충분하므로 유리수 곱셈도 필요하지 않다.

=== 일부 속성은 DFT와 유사 ===
월시 변환 행렬에서 각 행과 각 열은 [[월시 함수]]이며, 부호 변화의 수가 연속적으로 증가한다. 즉, 첫 번째 행과 첫 번째 열에는 부호 변화가 없다(모든 항목이 1과 같다). 두 번째 행에는 하나의 부호 변화가 있고, 세 번째 행에는 두 개의 부호 변화가 있으며, 이런 식으로 마지막 행까지 이어진다. <math display="block">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)</math>이를 이산 푸리에 변환 <math display="inline">e^{-j 2\pi mn/N}</math>과 비교하면, 각 행 {{수학 변수|i}}에는 <math display="inline">i-1</math>개의 [[영점 교차]]가 포함된다.

이산 푸리에 변환에서 {{수학 변수|m}}이 0과 같을 때(첫 번째 행에 해당), 결과도 1이다. 이후 행에 대해서는 행렬의 특성인 신호 주파수가 첫 번째 원본 행렬에서는 낮게 시작하여 다음 행으로 갈수록 증가하다가 마지막 행에서 최고조에 달하는 것을 관찰할 수 있다.

== 푸리에 변환과의 관계 ==
아다마르 변환은 사실 {{수학|2 × 2 × ⋯ × 2 × 2}} 크기의 다차원 DFT와 동일하다.<ref name="kunz">{{서적 인용|first=H.O. |last=Kunz |title=On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms |journal=IEEE Transactions on Computers |volume=28 |issue=3 |pages=267–8 |year=1979 |doi=10.1109/TC.1979.1675334 |s2cid=206621901 }}</ref>

또 다른 접근 방식은 아다마르 변환을 [[불 대수군]] <math>(\Z / 2\Z)^n</math>에 대한 푸리에 변환으로 보는 것이다.<ref>{{웹 인용 |url=https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf |제목=Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12–13 |확인날짜=2025-07-17 |archive-date=2021-05-01 |archive-url=https://web.archive.org/web/20210501173437/https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf |url-status= }}</ref>
<ref>[https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4–5]</ref> [[유한군에 대한 푸리에 변환|유한 (아벨) 군에 대한 푸리에 변환]]을 사용하여, 함수 <math>f \colon (\Z/2\Z)^n \to \Complex</math>의 푸리에 변환은 다음과 같이 정의된 함수 <math>\widehat f</math>이다.
<math display="block">\widehat{f}(\chi) = \sum_{a \in (\Z/2\Z)^n} f(a) \bar{\chi}(a)</math>
여기서 <math>\chi</math>는 <math>(\Z/2\Z)^n</math>의 [[지표 (수학)|지표]]이다. 각 지표는 어떤 <math>r \in (\Z/2\Z)^n</math>에 대해 <math>\chi_r(a) = (-1)^{a \cdot r}</math>의 형태를 가지며, 여기서 곱셈은 비트 문자열에 대한 불 스칼라곱이다. 따라서 <math>\widehat{f}</math>의 입력을 <math>r \in (\Z/2\Z)^n</math>([[폰트랴긴 쌍대성]])와 동일시하고, <math>\widehat f \colon (\Z/2\Z)^n \to \Complex</math>를 다음과 같이 정의할 수 있다:
<math display="block">\widehat{f}(r) = \sum_{a \in (\Z/2\Z)^n} f(a) (-1)^{r \cdot a}</math>

이는 <math>f</math>와 <math>\widehat{f}</math>의 입력을 불리언 문자열로 간주할 때 <math>f</math>의 아다마르 변환이다.

아다마르 변환이 <math>2^n</math>개의 복소수 벡터 <math>v</math>에 왼쪽에서 아다마르 행렬 <math>H_n</math>을 곱하는 위의 공식화 측면에서, 이 동등성은 <math>f</math>를 <math>v</math>의 요소 인덱스에 해당하는 비트 문자열을 입력으로 받고, <math>f</math>가 <math>v</math>의 해당 요소를 출력하도록 취함으로써 확인된다.

이는 벡터 <math>v</math>에 적용될 때 [[순환군]] <math>\Z / 2^n \Z</math>의 지표를 사용하는 일반적인 [[이산 푸리에 변환]]과 비교된다.

== 계산 복잡도 ==
고전적인 영역에서, 아다마르 변환은 [[고속 아다마르 변환]] 알고리즘을 사용하여 <math>n \log n</math> 연산(<math>n = 2^m</math>)으로 계산할 수 있다.

양자 영역에서, 아다마르 변환은 [[양자 논리 게이트]]로서 [[양자 논리 게이트#병렬 게이트|병렬화]]될 수 있으므로 <math>O(1)</math> 시간에 계산할 수 있다.

== 양자 컴퓨팅 응용 ==
아다마르 변환은 [[양자 컴퓨팅]]에서 광범위하게 사용된다. 2&nbsp;×&nbsp;2 아다마르 변환 <math>H_1</math>은 아다마르 게이트로 알려진 [[양자 논리 게이트]]이며, {{개행 금지|<math>n</math>-큐비트}} 레지스터의 각 큐비트에 아다마르 게이트를 병렬로 적용하는 것은 아다마르 변환 {{개행 금지|<math>H_n</math>}}과 동일하다.

=== 아다마르 게이트 ===
{{추가 정보|양자 게이트#아다마르 게이트}}
[[양자 컴퓨팅]]에서 아다마르 게이트는 하나의 [[큐비트]] [[회전]]으로, 큐비트-[[기저 (선형대수학)|기저]] 상태 <math>|0 \rangle </math>와 <math>|1 \rangle </math>를 계산 [[기저 (선형대수학)|기저]] 상태 <math>|0 \rangle </math>와 <math>|1 \rangle </math>의 동일한 가중치를 갖는 두 개의 [[양자 중첩]] 상태로 매핑한다. 일반적으로 위상은 다음과 같이 선택된다:
<math display="block">H=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\langle0|+\frac{|0\rangle-|1\rangle}{\sqrt{2}}\langle1|</math>

[[디랙 표기법]]에서. 이는 [[변환행렬]]
<math display="block">H_1=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}</math>
에 해당한다. 이는 <math>|0 \rangle , |1 \rangle </math> 기저, 즉 [[계산 기저]]에서도 알려져 있다. 상태 <math display="inline"> \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt{2}}</math>와 <math display="inline">\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt{2}}</math>는 각각 <math>\left|\boldsymbol{+}\right\rangle</math>와 <math>\left|\boldsymbol{-}\right\rangle</math>로 알려져 있으며, 함께 [[양자 컴퓨팅]]에서 [[극좌표 기저]]를 구성한다.

=== 아다마르 게이트 연산 ===
<math display="block">\begin{align}
  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{align}</math>

0 또는 1 큐비트에 아다마르 게이트를 한 번 적용하면 (처음 두 연산에서 볼 수 있듯이) 관측될 경우 0 또는 1이 동일한 확률로 나올 [[양자 상태]]가 생성된다. 이는 표준 [[확률적 튜링 기계|확률적 계산 모델]]에서 공정한 동전을 던지는 것과 정확히 같다. 그러나 아다마르 게이트를 연속으로 두 번 적용하면 (마지막 두 연산에서 효과적으로 수행되는 것처럼), 최종 상태는 항상 초기 상태와 동일하다.

=== 양자 알고리즘의 아다마르 변환 ===
양자 아다마르 변환은 아다마르 변환의 텐서곱 구조 때문에 각 큐비트에 아다마르 게이트를 개별적으로 적용하는 것과 같다. 이 간단한 결과는 양자 아다마르 변환이 <math>\log_2 N </math> 연산을 필요로 하며, 고전적인 경우 <math>N \log_2 N</math> 연산과 비교된다는 것을 의미한다.

<math>n</math>-큐비트 시스템의 경우, 각 <math>n</math> 큐비트(각각 <math>|0\rangle</math>으로 초기화됨)에 작용하는 [[아다마르 게이트]]는 <math>N = 2^n</math> 형태일 때 균일한 [[양자 중첩]] 상태를 준비하는 데 사용될 수 있다.
이 경우 <math>n</math> 큐비트를 사용하면 결합된 아다마르 게이트 <math>H_n</math>은 <math>n</math>개의 아다마르 게이트의 텐서곱으로 표현된다:
<math>H_n = \underbrace{H \otimes H \otimes \ldots \otimes H}_{n \text{ times}}</math>

결과적인 균일 양자 중첩 상태는 다음과 같다:
<math> H_{n} |0\rangle^{\otimes n} =  \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} |j\rangle</math>
이는 모든 <math>N = 2^n</math>에 대해 아다마르 게이트를 사용하여 균일 양자 상태를 준비하는 것을 일반화한다.<ref name="Nielsen-Chuang">{{서적 인용|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac|date=2010|publisher=[[케임브리지 대학교 출판부]]|isbn=978-1-10700-217-3|location=Cambridge|oclc=43641333|author-link=Michael Nielsen|author-link2=Isaac Chuang|url=https://www.cambridge.org/9781107002173}}</ref>

이 균일 양자 상태의 [[측정]]은 <math>|0\rangle</math>과 {{개행 금지|<math>|N-1\rangle</math>}} 사이의 [[난수 발생기|무작위]] 상태를 초래한다.

많은 [[양자 알고리즘]]은 아다마르 변환을 초기 단계로 사용한다. 앞서 설명했듯이, 이는 <math>|0 \rangle</math>으로 초기화된 n 큐비트를 <math> |0 \rangle , |1 \rangle </math> 기저의 모든 2<sup>n</sup> 직교 상태의 동일한 가중치를 갖는 중첩으로 매핑하기 때문이다. 예를 들어, 이는 [[도이치–조사 알고리즘]], [[사이먼의 알고리즘]], [[번스타인-바지라니 알고리즘]], 그리고 [[그로버 알고리즘]]에서 사용된다. [[쇼어 알고리즘]]은 초기 아다마르 변환과 [[양자 푸리에 변환]]을 모두 사용하는데, 둘 다 [[유한군에 대한 푸리에 변환]]의 일종이다. 첫 번째는 <math>(\Z / 2 \Z)^n</math>에 대한 것이고 두 번째는 <math>\Z /2^n \Z</math>에 대한 것이다.

일반적인 경우 <math>N </math> ≠  <math>2^n</math>일 때 균일 양자 중첩 상태를 준비하는 것은 비자명하며 더 많은 작업이 필요하다.
균일 중첩 상태를 준비하기 위한 효율적이고 결정론적인 접근 방식
<math
display="block">  |\Psi\rangle = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} |j\rangle  </math>
는 모든 <math>N</math>에 대해 게이트 복잡도와 회로 깊이가 <math> O(\log_2 N)</math>에 불과하며 최근에 발표되었다.<ref name="shukla2024efficient">
{{서적 인용| author = Alok Shukla and Prakash Vedula
  | title = An efficient quantum algorithm for preparation of uniform quantum superposition states
  | journal = Quantum Information Processing
  | volume = 23:38
  | issue = 1
  | year = 2024
  | page = 38
 | doi = 10.1007/s11128-024-04258-4
  | arxiv = 2306.11747
  | bibcode = 2024QuIP...23...38S
 }}
</ref> 이 접근 방식은 오직
<math> n = \lceil \log_2 N \rceil</math>
큐비트만 필요하다. 중요한 점은 이 접근 방식에서 균일 중첩 상태 <math> |\Psi\rangle </math>를 생성하는 데 보조 큐비트나 다중 제어 양자 게이트가 필요하지 않다는 것이다.

== 분자 계통학(진화생물학) 응용 ==
아다마르 변환은 분자 데이터를 사용하여 [[계통수]]를 추정하는 데 사용될 수 있다.<ref>{{서적 인용| last1=Hendy| first1=Michael D.| last2=Penny| first2=David|date=December 1989|title=A Framework for the Quantitative Study of Evolutionary Trees| url=https://academic.oup.com/sysbio/article-lookup/doi/10.2307/2992396| journal=Systematic Zoology|volume=38| issue=4| pages=297| doi=10.2307/2992396|jstor=2992396| url-access=subscription}}</ref><ref>{{서적 인용|last1=Hendy|first1=Michael D.|last2=Penny|first2=David| date=January 1993|title=Spectral analysis of phylogenetic data|url=http://link.springer.com/10.1007/BF02638451|journal=Journal of Classification| language=en|volume=10|issue=1|pages=5–24|doi=10.1007/BF02638451|s2cid=122466038|issn=0176-4268|url-access=subscription}}</ref><ref>Székely, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993). A Fourier inversion formula for evolutionary trees. Applied mathematics letters, 6(2), 13–16.</ref> [[계통학]]은 유기체 간의 관계를 이해하는 데 초점을 맞춘 [[진화생물학]]의 하위 분야이다. DNA [[다중서열정렬]]에서 얻은 위치 패턴 빈도의 벡터(또는 행렬)에 적용된 아다마르 변환은 나무 위상에 대한 정보를 담는 또 다른 벡터를 생성하는 데 사용될 수 있다. 계통 발생학적 아다마르 변환의 가역적 특성은 나무 위상 벡터로부터 위치 가능성을 계산할 수 있게 하여, 아다마르 변환을 [[최대가능도 방법|최대 가능도 추정]]에 사용할 수 있도록 한다. 그러나 후자의 응용은 위치 가능성을 계산하는 다른 훨씬 더 효율적인 방법이 있기 때문에 위치 패턴 벡터에서 나무 벡터로의 변환보다 덜 유용하다.<ref>{{서적 인용|last=Felsenstein|first=Joseph|date=November 1981| title=Evolutionary trees from DNA sequences: A maximum likelihood approach|url=http://link.springer.com/10.1007/BF01734359| journal=Journal of Molecular Evolution|language=en|volume=17|issue=6|pages=368–376|doi=10.1007/BF01734359|pmid=7288891|bibcode=1981JMolE..17..368F | s2cid=8024924| issn=0022-2844|url-access=subscription}}</ref><ref>{{인용|last=Stamatakis|first=Alexandros|title=A Review of Approaches for Optimizing Phylogenetic Likelihood Calculations|date=2019|url=http://link.springer.com/10.1007/978-3-030-10837-3_1|work=Bioinformatics and Phylogenetics|series=Computational Biology|volume=29|pages=1–19|editor-last=Warnow|editor-first=Tandy| place=Cham| publisher=Springer International Publishing|language=en|doi=10.1007/978-3-030-10836-6| isbn=978-3-030-10836-6|s2cid=145834168 | access-date=2020-10-10|url-access=subscription}}</ref> 그러나 계통 발생학적 아다마르 변환의 가역적 특성은 수학적 계통 발생학을 위한 우아한 도구를 제공한다.<ref>{{서적 인용|last1=Chor|first1=Benny|author1-link= 베니 코어 |last2=Hendy|first2=Michael D.| last3=Holland|first3=Barbara R.|last4=Penny|first4=David|date=2000-10-01|title=Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach|url=http://academic.oup.com/mbe/article/17/10/1529/956181|journal=Molecular Biology and Evolution| language=en|volume=17|issue=10|pages=1529–1541|doi=10.1093/oxfordjournals.molbev.a026252|pmid=11018159|issn=1537-1719|doi-access=free}}</ref><ref>{{서적 인용|last1=Matsen|first1=Frederick A.|last2=Steel|first2=Mike|date=2007-10-01|editor-last=Ané| editor-first=Cécile|editor-link= 세실 아네 |editor2-last=Sullivan|editor2-first=Jack|title=Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology|journal=Systematic Biology|language=en|volume=56|issue=5| pages=767–775| doi=10.1080/10635150701627304| pmid=17886146| issn=1076-836X|doi-access=free|arxiv=0704.2260}}</ref>

계통 발생학적 아다마르 변환의 메커니즘은 나무 <math>T</math>에 대한 위상 및 분지 길이 정보를 제공하는 벡터 <math>\gamma(T)</math>를 [[사이트 패턴]] 벡터 또는 행렬 <math>s(T)</math>를 사용하여 계산하는 것을 포함한다.

<math display="block">\gamma(T) = H^{-1}(\ln(Hs(T)))</math>
여기서 <math>H</math>는 적절한 크기의 아다마르 행렬이다. 이 방정식은 해석을 단순화하기 위해 세 개의 방정식 시리즈로 다시 작성될 수 있다:

<math display="block">\begin{align}
          r &= H s(T) \\
       \rho &= \ln r \\
  \gamma(T) &= H^{-1}\rho
\end{align}</math>

이 방정식의 가역적 특성은 다음과 같이 예상되는 사이트 패턴 벡터(또는 행렬)를 계산할 수 있게 한다:

<math display="block">s(T)=H^{-1}(\exp(H\gamma(T)))</math>

DNA에 대한 Cavender–Farris–[[예지 네이만|Neyman]] (CFN) 두 상태 [[치환 모델]]을 사용하여 [[뉴클레오타이드]]를 이진 문자([[퓨린]] A와 G는 R로, [[피리미딘]] C와 T는 Y로 인코딩)로 인코딩할 수 있다. 이렇게 하면 다중 서열 정렬을 위 사이트 패턴 벡터 <math>s(T)</math>로 인코딩할 수 있으며, 이는 다음 예시에서와 같이 나무 벡터 <math>\gamma(T)</math>로 변환될 수 있다:
{| class="wikitable"
|+ 특정 나무에 대한 아다마르 변환을 보여주는 예시
(작업 예시에 대한 값은 Waddell et al. 1997<ref>{{서적 인용|last1=Waddell|first1=Peter J| last2=Steel| first2=M.A| date=December 1997|title=General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites|journal=Molecular Phylogenetics and Evolution|language=en|volume=8| issue=3| pages=398–414 |doi=10.1006/mpev.1997.0452|pmid=9417897|bibcode=1997MolPE...8..398W }}</ref>에서 인용)
|-
! 인덱스
! 이진 패턴
! 정렬 패턴
! <math>\gamma(T)</math>
! <math>\rho = H^{-1}\gamma(T)</math>
! <math>r = \exp(\rho)</math>
! <math>s(T) = H^{-1}\rho</math>
|-
|  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
|}

이 표에 제시된 예시는 간략화된 세 가지 방정식 체계를 사용하며, [[Newick 형식]]으로 ((A,B),(C,D))로 작성될 수 있는 4개 분류군 나무에 대한 것이다. 사이트 패턴은 ABCD 순서로 작성된다. 이 특정 나무는 두 개의 긴 말단 가지(사이트당 0.2개의 [[트랜스버전]] 치환), 두 개의 짧은 말단 가지(사이트당 0.025개의 트랜스버전 치환), 그리고 짧은 내부 가지(사이트당 0.025개의 트랜스버전 치환)를 가지고 있다. 따라서 Newick 형식으로는 ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2))로 작성될 것이다. 이 나무는 데이터가 [[최대 단순성 (계통학)|최대 단순성]] 기준으로 분석될 경우 [[긴 가지 끌림]]을 나타낼 것이다(분석된 서열이 관찰된 사이트 패턴 빈도가 <math>s(T)=H^{-1}\rho</math> 열에 표시된 예상 빈도에 근접할 만큼 충분히 길다고 가정). 긴 가지 끌림은 인덱스 6의 사이트 패턴(나무 ((A,C),(B,D))를 지지하는)의 예상 수가 참 나무(인덱스 4)를 지지하는 예상 사이트 패턴의 수를 초과한다는 사실을 반영한다. 분명히, 계통 발생학적 아다마르 변환의 가역적 특성은 나무 벡터 <math>\gamma(T)</math>가 정확한 나무에 해당한다는 것을 의미한다. 따라서 변환 후의 단순성 분석은 [[일치 추정량|통계적으로 일치]]하며,<ref>{{서적 인용|last1=Steel|first1=M. A.|last2=Hendy|first2=M. D.|last3=Penny|first3=D.|date=1993-12-01|title=Parsimony Can Be Consistent!| url=https://academic.oup.com/sysbio/article-lookup/doi/10.1093/sysbio/42.4.581|journal=Systematic Biology| language=en| volume=42|issue=4|pages=581–587|doi=10.1093/sysbio/42.4.581|issn=1063-5157|url-access=subscription}}</ref> 올바른 모델(이 경우 CFN 모델)을 사용하는 표준 최대 우도 분석과 동일하다.

0 인덱스의 사이트 패턴은 (뉴클레오타이드를 퓨린 또는 피리미딘으로 인코딩한 후) 변경되지 않은 사이트에 해당한다. 별표가 있는 인덱스(3, 5, 6)는 "parsimony-informative"하며, 나머지 인덱스는 단일 분류군이 다른 세 분류군과 다른 사이트 패턴을 나타낸다(따라서 표준 최대 우도 계통수에서 말단 가지 길이와 동등하다).

RY 데이터 없이 뉴클레오타이드 데이터를 사용하려면(궁극적으로 0과 1로 재코딩), 사이트 패턴을 행렬로 인코딩할 수 있다. 4개 분류군 나무를 고려하면 총 256개의 사이트 패턴(4개의 뉴클레오타이드의 4제곱)이 존재한다. 그러나 [[DNA 진화 모델|기무라 3매개변수(또는 K81) 모델]]의 대칭성을 통해 DNA에 대한 256개의 가능한 사이트 패턴을 64개 패턴으로 줄일 수 있으며, 이로 인해 4개 분류군 나무에 대한 뉴클레오타이드 데이터를 8 × 8 행렬로 인코딩할 수 있다.<ref name=":0">{{서적 인용|last1=Hendy|first1=M. D.|last2=Penny|first2=D.|last3=Steel|first3=M. A.| date=1994-04-12| title=A discrete Fourier analysis for evolutionary trees.|journal=Proceedings of the National Academy of Sciences| language=en| volume=91|issue=8|pages=3339–3343|doi=10.1073/pnas.91.8.3339|issn=0027-8424|pmc=43572|pmid=8159749|bibcode=1994PNAS...91.3339H |doi-access=free}}</ref> 이는 위에서 전이(RY) 사이트 패턴에 사용된 8개 요소 벡터와 유사하다. 이는 [[클라인 4원군]]을 사용하여 데이터를 재코딩함으로써 달성된다:
{| class="wikitable"
|+ 계통 발생학적 아다마르 변환을 위한 클라인 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)
|T (0,1)
|C (1,1)
|-
|T (0,0)
|C (1,0)
|G (0,1)
|A (1,1)
|}

RY 데이터와 마찬가지로, 사이트 패턴은 임의로 선택된 첫 번째 분류군의 염기를 기준으로 색인화되며, 이후 분류군의 염기는 해당 첫 번째 염기를 기준으로 인코딩된다. 따라서 첫 번째 분류군은 비트 쌍 (0,0)을 받는다. 이 비트 쌍을 사용하여 RY 벡터와 유사한 두 개의 벡터를 생성한 다음 해당 벡터를 사용하여 행렬을 채울 수 있다. 이는 Hendy et al. (1994)의 예시<ref name=":0" />를 사용하여 설명할 수 있으며, 이는 네 가지 영장류 헤모글로빈 유사유전자의 다중 서열 정렬을 기반으로 한다:
{| class="wikitable"
|+ 인코딩된 서열 정렬 예시 (Hendy et al. 1994<ref name=":0" />에서 발췌)
(값은 9879개 사이트 중 개수임)
|-
!
! 0
! 8
! 16
! 24
! 32
! 40
! 48
! 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열이 [[전이 (유전학)|전이]] 차이에 해당하기 때문이며, 이는 거의 모든 유전체 영역 비교에서 트랜스버전 차이보다 더 빠르게 축적된다(그리고 이 예시에 사용된 헤모글로빈 유사유전자에서는 확실히 더 빠르게 축적된다<ref>{{서적 인용| last1=Miyamoto|first1=M. M.|last2=Koop|first2=B. F.|last3=Slightom|first3=J. L.|last4=Goodman|first4=M.| last5=Tennant| first5=M. R.|date=1988-10-01|title=Molecular systematics of higher primates: genealogical relations and classification.| journal= Proceedings of the National Academy of Sciences| language=en|volume=85|issue=20| pages=7627–7631| doi=10.1073/pnas.85.20.7627| issn=0027-8424| pmc=282245|pmid=3174657|bibcode=1988PNAS...85.7627M |doi-access=free}}</ref>). AAGG 사이트 패턴을 고려하면 클라인 군 비트 쌍의 두 번째 요소에 대해 이진 패턴 0000이 되고, 첫 번째 요소에 대해 0011이 된다. 이 경우 첫 번째 요소를 기반으로 한 이진 패턴은 인덱스 3(테이블에서 단일 별표로 표시)에 해당한다. GGAA, CCTT, TTCC 사이트 패턴도 정확히 같은 방식으로 인코딩된다. AACT 사이트 패턴은 두 번째 요소에 대해 이진 패턴 0011, 첫 번째 요소에 대해 0001로 인코딩된다. 이는 첫 번째 요소에 대해 인덱스 1, 두 번째 요소에 대해 인덱스 3을 생성한다. 두 번째 클라인 군 비트 쌍을 기반으로 한 인덱스는 8을 곱하여 열 인덱스(이 경우 24열)를 산출한다. AACT 사이트 패턴의 개수가 포함될 셀은 두 개의 별표로 표시되어 있다. 그러나 예시에서 숫자가 없는 것은 서열 정렬에 AACT 사이트 패턴이 없음을 나타낸다(마찬가지로 CCAG, GGTC, TTGA 사이트 패턴도 같은 방식으로 인코딩되며, 이들도 없음).

== 기타 응용 ==
아다마르 변환은 [[데이터 암호화]], [[JPEG XR]] 및 [[H.264/MPEG-4 AVC|MPEG-4 AVC]]와 같은 많은 [[신호 처리]] 및 [[데이터 압축]] [[알고리즘]]에서도 사용된다. [[영상 압축]] 응용 프로그램에서는 일반적으로 [[변환된 차이의 절대값 합계]] 형태로 사용된다. 또한 양자 컴퓨팅에서 상당수의 알고리즘의 중요한 부분이다. 아다마르 변환은 [[핵자기 공명]], [[질량 분석법]] 및 [[결정학]]과 같은 실험 기술에도 적용된다. 또한 일부 버전의 [[지역 민감 해싱]]에서도 의사 난수 행렬 회전을 얻기 위해 사용된다.

== 같이 보기 ==
* [[고속 왈시-아다마르 변환]]
* [[유사-아다마르 변환]]
* [[하르 변환]]
* [[일반화된 분배 법칙]]

== 외부 링크 ==
*{{웹 인용|first=Terry |last=Ritter |title=Walsh–Hadamard Transforms: A Literature Survey |date=August 1996 |url=http://www.ciphersbyritter.com/RES/WALHAD.HTM}}
*{{서적 인용|first1=Ali N. |last1=Akansu |first2=R. |last2=Poluri |title=Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications |journal=IEEE Transactions on Signal Processing |volume=55 |issue=7 |pages=3800–6 |date=July 2007 |doi=10.1109/TSP.2007.894229  |bibcode=2007ITSP...55.3800A |s2cid=6830633 |url=http://web.njit.edu/~akansu/PAPERS/Akansu-Poluri-WALSH-LIKE2007.pdf |author1-link=알리 아칸수 }}
* Pan, Jeng-shyang [http://www.freepatentsonline.com/y2009/0136023.html Data Encryption Method Using Discrete Fractional Hadamard Transformation] (May 28, 2009)
* Lachowicz, Dr. Pawel. [http://www.quantatrisk.com/2015/04/07/walsh-hadamard-transform-python-tests-for-randomness-of-financial-return-series/ Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series] (April 7, 2015)
*{{웹 인용|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 |access-date=2012-04-28 |archive-date=2014-10-18 |archive-url=https://web.archive.org/web/20141018190749/http://www1.chem.leeds.ac.uk/People/GSB/Hadamard_for_web.pdf |url-status=dead }}
*{{서적 인용|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  |volume=11 |issue=11 |pages=1131–1134 |pmid=25282611 |pmc=4216935}}

== 각주 ==
{{각주}}

{{WikiVault 번역 검토 필요}}
{{위키데이터 속성 추적}}

[[분류:양자 알고리즘]]
[[분류:변환 (수학)]]