문서 보기문서 편집수정 내역 아다마르 변환 (덤프버전으로 되돌리기) [include(틀:해석학·미적분학)] [include(틀:선형대수학)] [[분류:해석학(수학)]][[분류:선형대수학]][[분류:양자컴퓨터]][[분류:생물정보학]] || [[한국어]] || 아다마르 변환 || || [[영어]] || Hadamard transform || [목차] [clearfix] == 개요 == 아다마르 변환(Hadamard transform)은 이진 범위에서 실수를 선형적으로 연산하는 [[푸리에 변환]]의 일종이다. 즉 임의의 벡터값을 분해하는 특징이 있기 때문에 이진 연산 범위에서의 [[DFT]]를 [math(2^n)] 행렬로 정의할수 있다. 프랑스 수학자 자크 아다마르와 독일 수학자 한스 라데마허, 미국 수학자 조세프 웰시가 아다마르 변환을 정립했다. == 정의 == 이진 행렬 [math(2^N \times 2^N)]에 대하여, [math(2^N)]의 실수 [math(x_n)]을 또 다른 행렬 원소 [math(2^N)]의 실수 [math(X_l)]로 변환하는 방법 [math(H_N)]을 아다마르 변환이라고 하고 아래와 같은 공식으로 쓴다. {{{#!wiki style="text-align:center" [math(\displaystyle X_l = \dfrac{1}{\sqrt{2^N}}\sum_{n=0}^{N}|x_n\rangle)]}}} === 재귀성과 이진적인 특성 === [math(N=0)]이라면, 아다마르 변환 [math(H_0)]은 [math(1 \times 1)] 행렬로 정의되므로 [math(H_0)]이 항등원 1이다. 그러나 [math(N>0)]이라면, [math(H_N)]이 다음과 같이 재귀적으로 정의된다. 이를 sylvester construction이라 한다. {{{#!wiki style="text-align:center" [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)]이 아래와 같은 크로네커 곱으로 표현됨을 알 수 있다. {{{#!wiki style="text-align:center" [math(H_{N} = H_1 \otimes H_{N-1})]}}} [math(l)], [math(n)]을 이진수라 하고, 이진 변환 {{{#!wiki style="text-align:center" [math(\displaystyle n, l=\sum_{i=0}^{N-1}n, l_i 2^i )]}}} 을 생각하면 다음을 얻는다. {{{#!wiki style="text-align:center" [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]]인 것이다. == [[푸리에 해석]]의 아류 == 아다마르 변환은 푸리에 변환을 이진 원소의 행렬로 일반화한 것으로써 푸리에 해석의 공리를 따른다. 그러므로, 대수를 활용한 푸리에 해석으로 아다마르 변환의 설명이 가능하다. 유한군에서의 푸리에 해석을 살펴보자, 지표(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)]은 다음과 같다. {{{#!wiki style="text-align:center" [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})]로 정리될 수 있다. 그러므로 지표의 특성을 고려하여 식을 다시 정리하면, {{{#!wiki style="text-align:center" [math(\displaystyle \hat f(x) = \sum_{e\in(\mathbb Z/2\mathbb Z)^n} f(e)(-1)^{er})]}}} 즉, [math(f(e))]에 대한 아다마르 변환이 나온다. == [[양자정보과학|양자 정보학]] == '''양자 컴퓨팅에서 가장 중요한 변환중 하나이다.''' 아다마르 변환은 양자 알고리즘의 기본적인 초기 연산 방법으로 많이 사용된다. [math(|0\rangle)]과 함께 초기화된 큐비트 [math(2^N)]이 직교화 상태로 중첩되도록해서 [math(|0\rangle )]혹은 [math(|1\rangle)] 벡터 기저를 가지도록 한다. '''즉, 데이터화된 임의의 정보를 알고리즘에 대입하면 알고리즘 내에서 그 정보를 양자 중첩 상태로 만드는 매우 중요한 역할을 한다.''' 고전 컴퓨팅에서의 [[이산 푸리에 변환#s-3.2.1|아다마르 변환은 [math({\mathcal O}(n\log n))]이라는 지수적인 시간 복잡도]][* 재귀함수에서의 반복문이 O(n)의 시간 복잡도를 가질때, 재귀 깊이의 최댓값은 logn이기 때문이다. ] 를 가지지만 양자 컴퓨팅에서는 [math({\mathcal O}(1))]의 시간 복잡도를 가진다. 특히, 여러 아다마르 변환중에서 [math(2 \times 2)]의 아다마르 변환 [math(H_1)]이 양자 [[논리 회로]]에서 아다마르 게이트라는 이름으로 활용된다. === 아다마르 게이트 === 아다마르 게이트는 양자 컴퓨팅에서 1 큐비트 [[스핀(물리학)|회전]]을 의미한다. 계산적인 기저 상태인 [math(|0\rangle )]와 [math(|1\rangle )]로 큐비트 기저 상태, [math(|0\rangle )]와 [math(|1\rangle )]를 중첩한 상태의 사상을 디랙 규약으로 나타내면 {{{#!wiki style="text-align:center" [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)]에 일치함으로써, 양자 컴퓨팅의 극점 기저로 활용된다. ==== 연산 ==== 아다마르 게이트의 연산은 다음과 같다. {{{#!wiki style="text-align:center" [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이 된다. == 참고 문헌 == * [[https://en.m.wikipedia.org/wiki/Hadamard_transform]] * 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캡챠되돌리기