#!style
.grad {
background: border-box linear-gradient(to right, #781018, 10%, #8d141b 50%, 90%, #781018);
border: 2px solid transparent;
}
.grad tr:nth-of-type(2) > td {
background: padding-box var(--article-background-color);
overflow: hidden;
}
@theseed-dark-mode {
.grad {
background: border-box linear-gradient(to right, #781018, 10%, #8d141b 50%, 90%, #781018);
}
}
| 선형대수학 Linear Algebra | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#006ab8,#005593> ▲ 대수학 | ||||
| 기본 대상 | 일차함수 · 벡터 · 행렬 · 선형 변환 | ||||
| 대수 구조 | 가군(module) · 벡터 공간 · 내적 공간 · 노름 공간 · 쌍대 공간(대수적 쌍대 공간) | ||||
| 선형 연산자 | <colbgcolor=#006ab8,#005593> 기본 개념 | 연립방정식(1차 · 2차) · 행렬곱 · 단위행렬 · 역행렬과 크라메르 공식 · 가역행렬 · 전치행렬 · 행렬식(라플라스 전개) · 주대각합 | |||
| 선형계 | 기본행연산과 기본행렬 · 가우스-조르당 소거법 · 행사다리꼴 · 행렬표현 · 라그랑주 보간법 | ||||
| 주요 정리 | 선형대수학의 기본정리 · 차원 정리 · 가역행렬의 기본정리 · 스펙트럼 정리 | ||||
| 기타 | 제곱근행렬 · 멱등행렬 · 멱영행렬 · 대칭행렬 · 에르미트 행렬 · 야코비 행렬 · 방데르몽드 행렬 · 아다마르 행렬 변환 · 노름(수학) · 벡터장 | ||||
| 벡터공간의 분해 | 행렬의 닮음(상사) · 고유치 문제 · 케일리-해밀턴 정리 · 대각화(대각행렬) · 삼각화 · 조르당 분해 | ||||
| 벡터의 연산 | 노름 · 거리함수 · 내적 · 외적(신발끈 공식) · 다중선형형식 · ∇ · 크로네커 델타 | ||||
| 내적공간 | 그람-슈미트 과정 · 수반 연산자(에르미트 내적) | ||||
| 다중선형대수 | 텐서 · 텐서곱 · 레비치비타 기호 | ||||
| 기타 | 교재 | }}}}}}}}} | |||
| 한국어 | 아다마르 변환 |
| 영어 | Hadamard transform |
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)]을 아다마르 변환이라고 하고 아래와 같은 공식으로 쓴다.| <tableclass=disp> [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이라 한다.
| <tableclass=disp> [math(\displaystyle H_{N} = \frac{1}{\sqrt{2}} \begin{pmatrix} & H_{N-1} & H_{N-1} & \\ & H_{N-1} & -H_{N-1} & \end{pmatrix} )] |
| <tableclass=disp> [math(H_{N} = H_1 \otimes H_{N-1})] |
| <tableclass=disp> [math(\displaystyle n, l=\sum_{i=0}^{N-1}n, l_i 2^i )] |
| <tableclass=disp> [math((H_{N})_{n,l} = \dfrac{1}{2^{\frac{N}{2}} }(-1)^{\sum_j n_j l_j})] |
3. 푸리에 해석의 아류
아다마르 변환은 푸리에 변환을 이진 원소의 행렬로 일반화한 것으로써 푸리에 해석의 공리를 따른다. 그러므로, 대수를 활용한 푸리에 해석으로 아다마르 변환의 설명이 가능하다.유한군에서의 푸리에 해석을 살펴보자, 지표(character) 함수, [math(c(e) = e^{\frac{ie}{n}})]의 힐베르트 공간을 표현하기 위해서 대표적인 순환군이자, 몫군형태의 초등 아벨군, [math((\Z/2\Z)^n)]을 가정하고, 푸리에 변환을 상기하면, [math(f:((\Z/2\Z)^n) → \cnums)]의 푸리에 해석 [math(\hat f)]은 다음과 같다.
| <tableclass=disp> [math(\displaystyle \hat f(x) = \left< f, c \right>_{L(e)} = \sum_{e\in(\Z/2\Z)^n} f(e) \overline c(e))] |
| <tableclass=disp> [math(\displaystyle \hat f(x) = \sum_{e\in(\Z/2\Z)^n} f(e)(-1)^{er})] |
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 )]를 중첩한 상태의 사상을 디랙 규약으로 나타내면| <tableclass=disp> [math(H=\dfrac{|0 \rangle + |1 \rangle}{\sqrt{2}}\langle 0| + \dfrac{|0 \rangle - |1 \rangle}{\sqrt{2}}\langle 1|)] |
4.1.1. 연산
아다마르 게이트의 연산은 다음과 같다.| <tableclass=disp> [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이기 때문이다.