| 선형대수학 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> 기본 개념 | 연립방정식 · 행렬곱 · 단위행렬 · 역행렬과 크라메르 공식 · 가역행렬 · 전치행렬 · 행렬식(라플라스 전개) · 주대각합 | |
| 선형 시스템 | 기본행연산과 기본행렬 · 가우스-조르당 소거법 · 행사다리꼴 · 행렬표현 · 라그랑주 보간법 | ||
| 주요 정리 | 선형대수학의 기본정리 · 차원 정리 · 가역행렬의 기본정리 · 스펙트럼 정리 | ||
| 기타 | 제곱근행렬 · 멱등행렬 · 멱영행렬 · 에르미트 행렬 · 야코비 행렬 · 방데르몽드 행렬 · 아다마르 행렬 변환 · 노름(수학) | ||
| 벡터공간의 분해 | 상사 · 고유치 문제 · 케일리-해밀턴 정리 · 대각화(대각행렬) · 삼각화 · 조르당 분해 | ||
| 벡터의 연산 | 노름 · 거리함수 · 내적 · 외적(신발끈 공식) · 다중선형형식 · ∇ · 크로네커 델타 | ||
| 내적공간 | 그람-슈미트 과정 · 수반 연산자(에르미트 내적) | ||
| 다중선형대수 | 텐서 · 텐서곱 · 레비치비타 기호 | }}}}}}}}} | |
| 한국어 | 아다마르 변환 |
| 영어 | Hadamard transform |
[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})]
\\(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이기 때문이다.