최근 수정 시각 : 2022-08-12 11:20:45

아다마르 변환

해석학 · 미적분학
Analysis · Calculus
{{{#!wiki style="word-break: keep-all; margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px; letter-spacing: -1px"
<colbgcolor=#8f76d6> 함수 합성 · 항등원 · 역원 · 멱함수( 비례·반비례 ) · 초등함수( 대수함수 · 초월함수) · 특수함수 · 범함수 · 다변수 ( 동차 · 숨은 함수( 다가 함수 )) · 그래프 · 대칭 · 증감표 · 극값 · 연속 · 매끄러움 · 계단형 · 미끄럼틀형 · 볼록/오목 · 닮은꼴 함수 · 병리적 함수 · 해석적 연속 · 로그함수 · 지수함수 · 삼각함수
정리 · 토픽 좌표계 · 중간값 정리 · 최대·최소 정리 · 부동점 정리 · 오일러 동차함수 정리 · 립시츠 규칙
극한 부정형 · 어림( 유효숫자 ) · 근방 · 수열의 극한 · 엡실론-델타 논법 · 수렴 ( 균등수렴 ) · 발산 · 점근선 · 무한대 · 무한소 · 스털링 근사
정리 · 토픽 로피탈의 정리 · 슈톨츠-체사로 정리
수열
급수
규칙과 대응 · 단조 수렴 정리 · 멱급수 · 테일러 급수 ( 일람 ) · 조화급수 · 그란디 급수 · 망원급수 ( 부분분수분해 ) · 오일러 수열 · 베르누이 수열 · 파울하버의 공식 · 리만 재배열 정리
정리 · 토픽 바젤 문제 · 라마누잔합 · 0.999…=1 · 콜라츠 추측미해결
미적분 미분 도함수 일람 · 차분 · 유율법 · 변화량 · 변분법 · 도함수 ( 편도함수 ) · 곱미분 · 몫미분 · 연쇄 법칙 · 역함수 정리 · 임계점 ( 변곡점 · 안장점 ) · 미분형식 · 미분방정식 ( 풀이 ) · [math(boldsymbolnabla)] · 라그랑주 승수법
적분 역도함수 일람 · 부분적분 ( LIATE 법칙 · 도표적분법 · 예제 ) · 치환적분 · 정적분 ( 예제 ) · 이상적분 · 중적분 ( 선적분 · 면적분 · 야코비안 ) · 르베그 적분 · 스틸체스 적분 · 코시 주요값
정리 · 토픽 평균값 정리 ( 롤의 정리 ) · 스토크스 정리 ( 발산 정리 · 그린 정리 ) · 라플라스 변환 · 푸리에 해석 ( 푸리에 변환 ) · 아다마르 변환 · 미적분의 기본정리 · 2학년의 꿈 · 리시 방법

해석
측도론 ( 측도 · 르베그 측도 ) · 유계( 콤팩트성 ) · 칸토어 집합 · 비탈리 집합
정리 · 토픽
복소
해석
복소평면 · 편각 · 코시-리만 방정식
정리 · 토픽 오일러 공식 ( 드 무아브르 공식 ) · 리우빌의 정리 · 바이어슈트라스 분해 정리 · 미타그레플레르 정리
여타 하위 학문 수치해석학 ( FEM ) · 미분기하학 · 해석기하학 · 해석적 정수론 ( 소수 정리 ) · 벡터 미적분학 · 확률론 ( 중심극한정리 )
기타 뉴턴-랩슨 방법 · 디랙 델타 함수 · 리만 가설미해결 · 카오스 이론미해결 · merry=x-mas
응용 수리물리학 · 수리경제학( 경제수학) · 공업수학 }}}}}}}}}

선형대수학
Linear Algebra
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
<colbgcolor=#006ab8> 기본 대상 일차함수 · 벡터 · 행렬 · 선형 변환
대수적 구조 가군(모듈) · 벡터 공간 · 내적 공간
선형 연산자 <colbgcolor=#006ab8> 기본 개념 연립방정식 · 행렬곱 · 단위행렬 · 역행렬 크라메르 공식 · 가역행렬 · 전치행렬 · 행렬식( 라플라스 전개) · 주대각합
선형 시스템 기본행연산 기본행렬 · 가우스-조르당 소거법 · 행사다리꼴 · 행렬표현 · 라그랑주 보간법
주요 정리 차원 정리 · 가역행렬의 기본정리 · 선형대수학의 기본정리 · 스펙트럼 정리
기타 제곱근행렬 · 멱등행렬 · 멱영행렬 · 에르미트 행렬 · 야코비 행렬 · 방데르몽드 행렬 · 아다마르 행렬 변환
벡터공간의 분해 상사 · 고유치 문제 · 케일리-해밀턴 정리 · 대각화( 대각행렬) · 삼각화 · 조르당 분해
벡터의 연산 내적 · 외적( 신발끈 공식) · 다중선형형식 · [math(boldsymbolnabla)] · 크로네커 델타
내적공간 그람-슈미트 과정 · 수반 연산자( 에르미트 내적)
다중선형대수 텐서 · 텐서곱 · 레비치비타 기호 }}}}}}}}}


한국어 아다마르 변환
영어 Hadamard transform

1. 개요2. 정의3. 푸리에 변환과의 관계4. 양자 정보학
4.1. 아다마르 게이트
4.1.1. 연산
5. 계통 유전학

[clearfix]

1. 개요

아다마르 변환(Hadamard transform)은 이진 범위에서 실수를 연산할때 선형적으로 수행하는 푸리에 변환을 일반화시킨 연산법이다. 즉 임의의 벡터값을 분해하는 특징이 있기 때문에 이진 연산 범위에서의 DFT를 행렬로 정의할수 있다.

프랑스 수학자 자크 아다마르와 독일 수학자 한스 라데마허, 미국 수학자 조세프 웰시가 아다마르 변환을 정립했다.

2. 정의

이진 행렬 [math(2^N \times 2^N)]을 가정할때, [math(2^N)]의 실수 [math(x_n)]을 또 다른 행렬 원소 [math(2^N)]의 실수 [math(X_k)]로 변환하는 방법을 아다마르 변환 [math(H_N)]을 아다마르 변환이라고 하고 아래와 같은 공식으로 쓴다.
[math(\displaystyle X_k = \dfrac{1}{\sqrt{2^N}}\sum_{n=0}^{N}|x_n\rangle)]

아다마르 변환은 재귀적으로 풀어가는 방법과, n과 k에 binary을 적용하는 크게 2가지 방법으로 정의된다.

재귀적으로 풀때, 아다마르 변환 [math(H_0)]은 [math(1 \times 1)] 행렬로 정의되므로 [math(H_0)]이 항등원임을 알수 있다. 그러므로 N>0이라는 가정하에, [math(H_N)]이 다음과 같은 행렬로 나타나게 된다.

[math(\displaystyle H_{N+1} = \frac{1}{\sqrt{2}} \begin{pmatrix} & H_{N} & H_{N} & \\ & H_{N} & -H_{N} & \end{pmatrix} )]

그러므로 N>1일때, [math(H_N)]이 아래와 같은 크로네커 곱[1]으로 표현됨을 알수 있다.

[math(H_{N+1} = H_1 \otimes H_{N})]

또 다른 방법인 이진법을 이용하면, n과 k는 다음과 같이 정의된다.

[math(\displaystyle k=\sum_{i=0}^{N}k_i 2^i = k_{N}2^{N} + k_{N-1}2^{N-1} + \cdots + k_1 2 + k_0 )]

[math(\displaystyle n=\sum_{i=0}^{N}n_i 2^i = n_{N}2^{N} + n_{N-1}2^{N-1} + \cdots + n_1 2 + n_0 )]

그러므로,

[math((H_{N+1})_{n,k} = \dfrac{1}{2^{\frac{N}{2}}}(-1)^{\sum_j k_j i_j})][2]

혹은,

따라서, 대입값과 산출값이 [math(n_j)]와 [math(k_j)]의 다중차원 배열일때, 아다마르 변환은 [math(2^n)]의 다중차원 DFT임을 알수 있다.

3. 푸리에 변환과의 관계

초등 아벨군, [math((\mathbb Z/2\mathbb Z)^n)]의 푸리에 변환은 아다마르 변환을 설명하는 방법들중 하나이다. 유한군에서의 푸리에 변환을 상기하면, [math(f:((\mathbb Z/2\mathbb Z)^n) → \mathbb C)]라는 함수의 푸리에 변환 [math(\hat f)]은 다음과 같이 정리된다.

[math(\displaystyle \hat f(x) = \sum_{a\in(\mathbb Z/2\mathbb Z)^n} f(a) \overline x(a))]

여기서 x는 [math((\mathbb Z/2\mathbb Z)^n)]의 지표이다. 곱연산이 초등 아벨군의 내적일때, 한 [math(r\in(\mathbb Z/2\mathbb Z)^n)]에 대해, 각 지표는 [math(x_r(a)=(-1)^{ar})]로 정리될수 있다. 그러므로 지표의 특성을 고려하여 식을 다시 정리하면,

[math(\displaystyle \hat f(x) = \sum_{a\in(\mathbb Z/2\mathbb Z)^n} f(a)(-1)^{ar})]

즉, f(a)에 대한 아다마르 변환이 나옴을 알수있다. 위의 정의 문단에서 아다마르 변환이 아다마르 행렬 왼쪽에 있는 식 복소수 v를 [math(2^n)]이라는 벡터의 곱연산임을 상기하면, f에 v의 원소의 지표와 일치하는 비트 끈을 대입함으로써 동일함이 성립됨을 알 수 있다.

4. 양자 정보학

양자 컴퓨팅에서 가장 중요한 변환중 하나이다.

아다마르 변환은 양자 알고리즘의 기본적인 초기 연산 방법으로 많이 사용된다. [math(|0\rangle)]과 함께 초기화된 큐비트 [math(2^N)]이 직교화 상태로 중첩되도록해서 [math(|0\rangle )]혹은 [math(|1\rangle)]기저를 가지도록 한다. 즉, 데이터화된 임의의 정보를 알고리즘에 대입하면 알고리즘 내에서 그 정보를 양자 중첩 상태로 만드는 매우 중요한 역할을 한다.

이런 특성으로 고전 컴퓨팅에서의 아다마르 변환은 [math({\mathcal O}(n\log n))]이라는 지수적인 시간 복잡도를 가지나 양자 컴퓨팅에서는 [math({\mathcal O}(1))]의 시간 복잡도를 가진다.

특히, 여러 아다마르 변환중에서 [math(2 \times 2)]의 아다마르 변환 [math(H_1)]이 양자 논리 회로에서 아다마르 게이트라는 이름으로 활용된다.

4.1. 아다마르 게이트

아다마르 게이트는 양자 컴퓨팅에서 1 큐비트 회전을 의미한다. 계산적인 기저 상태인 [math(|0\rangle )]와 [math(|1\rangle )]로 큐비트 기저 상태, [math(|0\rangle )]와 [math(|1\rangle )]를 중첩한 상태의 사상을 디랙 규약으로 나타내면

[math(H=\dfrac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0| + \dfrac{|0 \rangle - |1 \rangle}{\sqrt{2}}\langle 1|)]

위 식은 아다마르 변환 [math(H_1)]과 일치한다. 참고로 [math(\frac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0|)]과 [math(\frac{|0 \rangle - |1 \rangle}{\sqrt{2}}\langle 1|)]는 각각 [math(|+\rangle)]과 [math(|-\rangle)]에 일치함으로써, 양자 컴퓨팅의 극점 기저로 활용된다.

4.1.1. 연산

아다마르 게이트의 연산은 다음과 같다.

[math(H(|0\rangle)=\frac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0|:=|+\rangle)]

[math(H(|1\rangle)=\frac{|0 \rangle - |1 \rangle}{\sqrt{2}}\langle 1|:=|-\rangle)]

[math(H(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle)=\frac{1}{2}(|0\rangle +|1\rangle)+\frac{1}{2}(|0\rangle - |1\rangle)=|0\rangle)]

[math(H(\frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle)=\frac{1}{2}(|0\rangle +|1\rangle)-\frac{1}{2}(|0\rangle - |1\rangle)=|1\rangle)]

위 연산에서는 0,1이 양자 상태를 결정하고, 양자 상태가 관측되면, 0,1으로 나타내질 확률이 1/2가 된다.

5. 계통 유전학

아다마르 변환은 유기체를 이루는 분자들의 상호작용을 측정할 수 있기 때문에 계통 유전 트리에도 사용된다. 계통 유전 트리에 아다마르 변환을 이용하면 유전체 염기서열의 위치 패턴 빈도들의 벡터 값에 계통 위상의 유전적인 정보를 다루는 다른 벡터 값을 도출할 수 있게 된다. 또한 아다마르 변환의 변환적 특징(invertible nature)을 사용해서 유전 계통에서의 유전적 정보내 원소의 특정 위치를 확률적으로 계산할 수 있다.

유전 계통의 아다마르 변환이 적용되는 역학적 원리는 다음과 같다.

[math(\displaystyle \gamma(T)=H^{-1}(\ln(Hs(T)))]

벡터 연산 [math(\gamma(T))]과 아다마르 행렬 H를 적용한 위 식을 활용하면 위치 패턴 벡터 s(T)를 정의해서 유전 계통 트리의 가지 길이 T와 위상에 관한 정보를 알수있다.

그러므로 위식을 변환(invertible nature)하여 위치 백터를 도출하는 식은 위식의 역연산과 동치이다.

[math(\displaystyle s(T)=H^{-1}(e^{H\gamma(T)}))]

한편, 유전체의 아미노산 합성 정보에 관여하는 A,T,G,C의 위치 패턴을 아다마르 변환을 활용하여 이진 모델인 CFN-이종 상태 대체 모델로 깔끔하게 나타내기 위해서는 퓨린기의 A G을 R, 피리미딘기의 C T은 Y로 치환하고 위 식을 아래와 같이 치환해야 한다.

[math(\displaystyle r=Hs(T))]
[math(\displaystyle ρ=\ln\,r)]
[math(\displaystyle \gamma(T)=H^{-1}ρ)]

그러므로, invertible한 식, 치환한 식과 유전체 이진 부호를 모두 적용하면, 트리 벡터 [math(\gamma(T))]와 위치 패턴 벡터 [math(s(T))]을 CFN-이종 상태 대체 모델의 표로 깔끔하게 계산할 수 있다.
index 이진패턴 배열패턴 [math(\gamma(T))] [math(ρ=H^{-1}\gamma(T))] [math(r=e^ρ)] [math(H^{-1}ρ=s(T))]
0 0000 RRRR -0.475 0 1 0.6479
1 0001 RRRY 0.2 -0.5 0.6065 0.1283
2 0010 RRYR 0.025 -0.15 0.8607 0.02
3* 0011 RRYY 0.025 -0.45 0.6376 0.0226
4 0100 RYRR 0.2 -0.45 0.6376 0.1823
5* 0101 RYRY 0 -0.85 0.4274 0.0258
6* 0110 RYYR 0 -0.5 0.6065 0.0070
7 0111 RYYY 0.025 -0.9 0.4066 0.02

[1] 간단히 말해서 크로네커 곱으로 표현된 행렬 A와 B의 연산은 행렬 A의 각 인수와 행렬 B 전체를 곱연산하는 것이다. [2] [math(\sum_j k_j i_j)]는 내적 연산이다.