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

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

= 쇼어 알고리듬 (Shor’s Algorithm) =

$$n$$비트로 표현되는 자연수를 고전 컴퓨터로 소인수분해하는 알고리듬은 $$O(\text{exp}\left( n^{\frac{1}{3}}\log^{\frac{2}{3}}n \right))$$ 의 시간 복잡도를 가진다. 이러한 계산 복잡도는 지수적이므로 큰 수를 소인수분해하는 것은 다루기 힘든(intractable) 문제로 여겨지며 이는 현재 가장 대중적으로 사용되는 공개키 알고리듬인 RSA 알고리듬의 기반이 된다. 그러나 쇼어 알고리듬은 [[양자 푸리에 변환]]을 이용하여 $$O(n^{2}\log{n\log{\log{n)}}}$$의 시간 복잡도로 $$n$$비트 자연수의 소인수분해를 수행할 수 있다. 이는 다항시간이므로 현재 사용되는 암호화를 손쉽게 무력화할 수 있을 것으로 예상되며 이는 양자 컴퓨터의 킬러 애플리케이션이 될 것으로 예상된다.

* 차수 찾기 알고리듬 (Order Finding Algorithm)
어떤 수 $$x$$의 모듈로 $$N$$에 관한 차수(order of $$x$$ modulo $$N$$)는

\[x^{r} \equiv 1 \left( \text{mod}\,N \right)\]

을 만족하는 가장 작은 자연수 $$r$$로 정의된다.

양자 위상 추정 알고리듬을 사용하면 $$O(\left( \log N \right)^{3})$$의 시간 복잡도로 계산할 수 있다.<ref name=Nielsen /> 쇼어 알고리듬은 차수 찾기 알고리듬을 통해 효율적으로 소인수의 후보를 탐색하는 방식으로 작동한다.

* 구현
$$\left| \left.  j \right\rangle \right. \left| \left.  k \right\rangle \right.  \rightarrow  \left| \left.  j \right\rangle \right. \left| \left.  x^{j} k\, \text{mod}\, N \right\rangle \right. $$ 으로 변환하는 블랙박스 $$U_{x}$$가 구현되어 있다고 가정하자. $$t=  2L + 1 + \left\lceil \log(2 + 1/2\varepsilon) \right\rceil $$개의 양자 위상 추정을 위한 큐비트를 사용하면 $$O(L^{3}{) }$$의 시간 복잡도로 차수를 계산할 수 있다. 여기서 $$L{ =\left\lceil \log N \right\rceil\text{  }}$$이라고 한다. 쇼어 알고리듬은 $$x$$를 랜덤하게 선택하여 $$N$$의 소인수분해를 시도한다. 만약 $$x^{r} \equiv 1 \left( \text{mod}\,N \right)$$ 일 때, $$r$$이 짝수인 경우 $$\left( x^{\frac{r}{2}} - 1 \right)\left( x^{\frac{r}{2}} + 1 \right) \equiv 0 \left( \text{mod}\,N \right)$$ 이므로 $$\text{gcd}(\left( x^{\frac{r}{2}} - 1 \right), N)$$과 $$\text{gcd}(\left( x^{\frac{r}{2}} + 1 \right), N)$$을 계산하여 1이 아닌 최대공약수를 갖는다면 해당 자연수로 $$N$$을 인수분해한다. $$r$$이 홀수인 경우 다른 $$x$$를 선택한다.

이러한 과정을 반복하면 다항시간으로 $$N$$을 소인수분해할 수 있음이 알려져 있다.<ref name=Nielsen /> 간단하게 동작 원리를 알아 보면, 먼저 양자 위상 추정을 사용하기 위해 $$U_{a}$$의 고윳값과 고유벡터가 어떻게 되는지를 살펴봐야 한다. 그러면 $$s \in \{ 0,1,\ldots,r - 1\}$$ 에 대하여 고유벡터와 고윳값은 각각 $$\left| \left.  u_{s} \right\rangle \right.= \frac{1}{\sqrt{r}}\sum_{j =0}^{r - 1}e^{- \frac{2\pi isj}{r}}\left| \left.  a^{j}\,\text{mod}\,N \right\rangle \right. $$과 $$e^{\frac{2\pi is}{r}}$$이 됨을 알 수 있다. 이 때 모든 고유벡터를 [[중첩]]시키면 $$\frac{1}{\sqrt{r}}\sum_{s= 0}^{r - 1}\left| \left.  u_{s} \right\rangle \right. =\left| \left.  1 \right\rangle \right. $$이 된다. 그렇기 때문에 아래 그림에서 양자 위상 추정을 위한 고유벡터로 $$\left| \left.  1 \right\rangle \right. $$을 사용한 것이다. 이렇게 하면 양자 위상 추정을 통해 $$s/r$$를 추정할 수 있고, 이를 통해 $$r$$ 값을 추정하여 위에서 언급한 방법대로 인수분해가 가능한지 검사한다.

현재 큰 수의 소인수분해가 어렵다는 것은 RSA 암호를 비롯한 공개키 암호의 근간을 이루므로 해당 알고리듬은 현재 발견된 양자 알고리듬 중 가장 유용한 킬러 애플리케이션으로 여겨진다.

[[File:기술백서_전체수정_6차_6_resize.jpg|none|thumb|500px|쇼어 알고리듬의 회로도.<ref>https://en.wikipedia.org/wiki/Shor%27s_algorithm</ref> 참고문헌 [5]의 그림을 재구성함.
]]

요약:

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

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

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

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

둘러보기 메뉴

검색