아다마르 변환
덤프버전 :
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(l)], [math(n)]을 이진수라 하고, 이진 변환
을 생각하면 다음을 얻는다.
[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}(n\log 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|)]
[1] 재귀함수에서의 반복문이 O(n)의 시간 복잡도를 가질때, 재귀 깊이의 최댓값은 logn이기 때문이다.
위 식은 아다마르 변환 [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
이 문서의 내용 중 전체 또는 일부는 2023-12-06 14:16:56에 나무위키 아다마르 변환 문서에서 가져왔습니다.