양자 알고리듬 (Quantum Algorithm) 편집하기 (부분)

경고: 로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다. 로그인하거나 계정을 생성하면 편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.

= 양자 푸리에 변환 (Quantum Fourier Transform) =

양자 푸리에 변환은 이산 푸리에 변환(discrete Fourier transform)

\[y_{k} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1}x_j e^{\frac{2 \pi ijk}{N}}\]

을 [[양자 컴퓨터]]를 통해 수행하는 알고리즘이다.

일반적으로 이산 푸리에 변환이 길이가 $$N(= 2^{n})$$인 배열(array)에 대해 정의되는 것에 비해 양자 푸리에 변환은 직교 기저(orthonormal basis) $$\left| \left.  0 \right\rangle \right. $$, …, $$\left| \left.  N - 1 \right\rangle \right. $$에 대해 다음과 같이 정의된다.

\[\begin{align*}
\left.  |j \right\rangle \overset{\text{QFT}}{\rightarrow}\frac{1}{\sqrt{N}}\sum_{k= 0}^{N - 1}{e^{\frac{2\pi ijk}{N}}\left.  |k \right\rangle}

&= \frac{1}{\sqrt{N}} \sum_{k_{1} =0}^{1}\ldots\sum_{k_{n}= 0}^{1}{e^{2\pi ij(\sum_{l =1}^{n}{k_{l}2^{- l}})}\left.  |k_{1}\ldots k_{n} \right\rangle} \\

&= \frac{1}{\sqrt{N}} \sum_{k_{1} =0}^{1}\ldots\sum_{k_{n}= 0}^{1}{\otimes_{l =1}^{n}e^{2\pi ijk_{l}2^{- l}}\left.  |k_{l} \right\rangle} \\

&= \frac{1}{\sqrt{N}} \otimes_{l =1}^{n}\left\lbrack \sum_{k_{l}= 0}^{1}{e^{2\pi ijk_{l}2^{- l}}\left.  |k_{l} \right\rangle} \right\rbrack \\

&= \frac{1}{\sqrt{N}} \otimes_{l =1}^{n}\left\lbrack \left.  |0 \right\rangle  +  e^{2\pi ijk_{l}2^{- l}}\left.  |1 \right\rangle \right\rbrack \\

&= \frac{\left( \left.  |0 \right\rangle + e^{2\pi ij0.j_{n}}\left.  |1 \right\rangle \right)\ldots\left( \left.  |0 \right\rangle + e^{2\pi ij0.{j_{1}\ldots j}_{n}}\left.  |1 \right\rangle \right)}{\sqrt{N}} \\
\end{align*}\]

알고리듬의 시간 복잡도는 $$O( \left( \log N \right)^{2})$$으로 (또는 $$O(n^{2})$$) 고전 컴퓨터에서 고속 푸리에 변환의 시간 복잡도 $$O(N\log{N)}$$에 비해 지수적으로 빠르게 수행된다.

* 구현
<blockquote>하다마드 게이트(Hadamard gate)와 조건부 위상 게이트(controlled phase gate)로 구성된다. 게이트에 대한 보다 상세한 내용은 [[양자 게이트]]를 참고하라.</blockquote>

* 하다마드 게이트 (Hadamard Gate)
<blockquote>기본적인 [[중첩]] 상태를 만드는 게이트로 계산 기저(computational basis)에 대하여 다음과 같이 정의된다.</blockquote>

\[H= \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1 \\ 1 & -1 \\ \end{pmatrix}\]

* 조건부 위상 게이트 (Controlled Phase Gate)
조건부 [[큐비트]]의 값에 따라 항등 게이트(identity gate)로 작용하거나 특정 각도의 회전으로 작용한다. 특정 각도 회전 게이트는 계산 기저에 대해 다음과 같이 표현된다.

\[R_{m}= \begin{pmatrix}
1 & 0 \\
0 & e^{\frac{2\pi i}{2^{m}}}\\
\end{pmatrix}\]

각 [[큐비트]]가 알고리듬이 요구하는 상태가 되기 위해서는 $$i$$번째 [[큐비트]]가 $$n - i + 1$$개의 [[게이트]]를 필요로 하기 때문에 전체 필요한 [[게이트]]의 수는 다음과 같다.

\[\sum_{i= 1}^{n}{(n - i + 1)} =\frac{n(n + 1)}{2}\]

즉, [[게이트]]의 수는 [[큐비트]] 개수의 제곱에 비례하게 증가하며 [[큐비트]]의 개수는 입력 크기의 로그에 비례하여 증가한다. 따라서 시간 복잡도는 $$O( \left( \log N \right)^{2} )$$ 이며 공간 복잡도는 추가적인 큐비트를 필요로 하지 않기 때문에 $$O(\log N)$$이다.

[[File:기술백서_전체수정_6차_4_resize.jpg|none|thumb|500px|양자 푸리에 변환 회로.<ref>https://en.wikipedia.org/wiki/Quantum_Fourier_transform</ref> 참고문헌 [2]의 그림을 재구성함.
]]

요약:

한국양자정보학회 위키에서의 모든 기여는 다른 기여자가 편집, 수정, 삭제할 수 있다는 점을 유의해 주세요. 만약 여기에 동의하지 않는다면, 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다(자세한 사항은 한국양자정보학회 위키:저작권 문서를 보세요). 저작권이 있는 내용을 허가 없이 저장하지 마세요!

취소 편집 도움말 (새 창에서 열림)

원본 주소 "https://wiki.qisk.or.kr/양자_알고리듬_(Quantum_Algorithm)"

양자 알고리듬 (Quantum Algorithm) 편집하기 (부분)

둘러보기 메뉴

검색