최근 수정 시각 : 2024-01-20 06:13:23

아다마르 변환

해석학· 미적분학
Analysis · Calculus
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
<colbgcolor=#26455A>실수와 복소수 실수( 실직선 · 아르키메데스 성질) · 복소수( 복소평면 · 극형식 · 편각) · 근방 · 유계 · 콤팩트성 · 완비성
함수 함수 · 조각적 정의 · 항등함수 · 역함수 · 멱함수 · 다변수함수( 동차함수 · 음함수) · 다가 함수 · 함수의 그래프 · 좌표계 · 닮은꼴 함수 · 극값 · 볼록/오목 · 증감표
초등함수( 대수함수 · 초월함수 · 로그함수 · 지수함수 · 삼각함수) · 특수함수 · 범함수( 변분법 · 오일러 방정식) · 병리적 함수
극한·연속 함수의 극한 · 수열의 극한 · 연속함수 · ε-δ 논법 · 수렴( 균등수렴) · 발산 · 부정형 · 점근선 · 무한대 · 무한소 · 0.999…=1
중간값 정리 · 최대·최소 정리 · 부동점 정리 · 스털링 근사 · 선형근사( 어림)
수열· 급수 수열 · 급수( 멱급수 · 테일러 급수( 일람) · 조화급수 · 그란디 급수( 라마누잔합) · 망원급수( 부분분수분해)) · 그물
오일러 수열 · 베르누이 수열 · 월리스 곱
단조 수렴 정리 · 슈톨츠-체사로 정리 · 축소구간정리 · 급수의 수렴 판정 · 리만 재배열 정리 · 바젤 문제 · 파울하버의 공식 · 오일러-매클로린 공식 · 콜라츠 추측미해결
미분 미분 · 도함수( 이계도함수 · 도함수 일람) · 곱미분 · 몫미분 · 연쇄 법칙 · 임계점( 변곡점 · 안장점) · 매끄러움
평균값 정리( 롤의 정리) · 테일러 정리 · 역함수 정리 · 다르부 정리 · 로피탈 정리
립시츠 규칙 · 뉴턴-랩슨 방법 · 유율법
적분 적분 · 정적분( 예제) · 스틸체스 적분 · 부정적분( 부정적분 일람) · 부분적분( LIATE 법칙 · 도표적분법 · 예제) · 치환적분 · 이상적분( 코시 주요값)
미적분의 기본정리 · 적분의 평균값 정리
리시 방법 · 2학년의 꿈
다변수· 벡터 미적분 편도함수 · 미분형식 · · 중적분( 선적분 · 면적분 · 야코비안) · 야코비 공식
라그랑주 승수법 · 오일러 동차함수 정리 · 선적분의 기본정리 · 스토크스 정리( 발산 정리 · 그린 정리 변분법
미분방정식 미분방정식( 풀이) · 라플라스 변환
측도론 측도 · 가측함수 · 곱측도 · 르베그 적분 · 절대 연속 측도 · 라돈-니코딤 도함수
칸토어 집합 · 비탈리 집합
복소해석 코시-리만 방정식 · 로랑 급수 · 유수 · 해석적 연속 · 오일러 공식( 오일러 등식 · 드 무아브르 공식) · 리우빌의 정리 · 바이어슈트라스 분해 정리 · 미타그레플레르 정리
함수해석 공간 위상 벡터 공간 · 국소 볼록 공간 · 거리공간 · 프레셰 공간 · 노름공간 · 바나흐 공간 · 내적공간 · 힐베르트 공간 · Lp 공간
작용소 수반 작용소 · 에르미트 작용소 · 정규 작용소 · 유니터리 작용소 · 컴팩트 작용소
대수 C*-대수 · 폰 노이만 대수
정리 한-바나흐 정리 · 스펙트럼 정리 · 베르 범주 정리
이론 디랙 델타 함수( 분포이론)
조화해석 푸리에 해석( 푸리에 변환 · 아다마르 변환)
관련 분야 해석기하학 · 미분기하학 · 해석적 정수론( 1의 거듭제곱근 · 가우스 정수 · 아이젠슈타인 정수 · 소수 정리 · 리만 가설미해결) · 확률론( 확률변수 · 중심극한정리) · 수치해석학 · 카오스 이론 · 분수계 미적분학 · 수리물리학 · 수리경제학( 경제수학) · 공업수학
양-밀스 질량 간극 가설미해결 · 나비에 스토크스 방정식의 해 존재 및 매끄러움미해결
기타 퍼지 논리
}}}}}}}}} ||

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


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

1. 개요2. 정의
2.1. 재귀성과 이진적인 특성
3. 푸리에 해석의 아류4. 양자 정보학
4.1. 아다마르 게이트
4.1.1. 연산
5. 참고 문헌

[clearfix]

1. 개요

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

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

2. 정의

이진 행렬 [math(2^N \times 2^N)]에 대하여, [math(2^N)]의 실수 [math(x_n)]을 또 다른 행렬 원소 [math(2^N)]의 실수 [math(X_l)]로 변환하는 방법 [math(H_N)]을 아다마르 변환이라고 하고 아래와 같은 공식으로 쓴다.

[math(\displaystyle X_l = \dfrac{1}{\sqrt{2^N}}\sum_{n=0}^{N}|x_n\rangle)]

2.1. 재귀성과 이진적인 특성

[math(N=0)]이라면, 아다마르 변환 [math(H_0)]은 [math(1 \times 1)] 행렬로 정의되므로 [math(H_0)]이 항등원 1이다.

그러나 [math(N>0)]이라면, [math(H_N)]이 다음과 같이 재귀적으로 정의된다. 이를 sylvester construction이라 한다.

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

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

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

[math(l)], [math(n)]을 이진수라 하고, 이진 변환
[math(\displaystyle n, l=\sum_{i=0}^{N-1}n, l_i 2^i )]

을 생각하면 다음을 얻는다.

[math((H_{N})_{n,l} = \dfrac{1}{2^{\frac{N}{2}} }(-1)^{\sum_j n_j l_j})]

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

3. 푸리에 해석의 아류

아다마르 변환은 푸리에 변환을 이진 원소의 행렬로 일반화한 것으로써 푸리에 해석의 공리를 따른다. 그러므로, 대수를 활용한 푸리에 해석으로 아다마르 변환의 설명이 가능하다.

유한군에서의 푸리에 해석을 살펴보자, 지표(character) 함수, [math(c(e) = e^{\frac{ie}{n}})]의 힐베르트 공간을 표현하기 위해서 대표적인 순환군이자, 몫군형태의 초등 아벨군, [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) = \left< f, c \right>_{L(e)} = \sum_{e\in(\mathbb Z/2\mathbb Z)^n} f(e) \overline c(e))]

초등 아벨군의 한 원소 [math(r\in(\mathbb Z/2\mathbb Z)^n)]에 대해, 아다마르 변환의 지표는 [math(c_r(e)=(-1)^{er})]로 정리될 수 있다. 그러므로 지표의 특성을 고려하여 식을 다시 정리하면,

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

즉, [math(f(e))]에 대한 아다마르 변환이 나온다.

4. 양자 정보학

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

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

고전 컴퓨팅에서의 아다마르 변환은 [math({mathcal O}(nlog n))]이라는 지수적인 시간 복잡도[1] 를 가지지만 양자 컴퓨팅에서는 [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(\begin{aligned}H(|0\rangle)&=\frac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0|:=|+\rangle

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

\\(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

\\(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\end{aligned})]


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

5. 참고 문헌

  • Mittal, R. (2022, Oct 21) Lecture 8, CS 682 [Lecture Note], Department of Computer Science and Engineering, IIT Kanpur
  • Tao, T. (2019, Mar 1) Lecture Note 9 : Fourier Analysis of Abelian Group, Math 247B [Lecture Note], Department of Mathematics, UCLA

[1] 재귀함수에서의 반복문이 O(n)의 시간 복잡도를 가질때, 재귀 깊이의 최댓값은 logn이기 때문이다.