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

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

= 그로버 알고리듬 (Grover’s Algorithm) =

그로버 알고리듬은 앞서 소개한 양자 푸리에 변환 기반 알고리듬과 함께 현재 알려진 양자 알고리듬의 두 가지 축 중 하나이다. $$N$$개의 원소에 대해 정의된 함수 $$f(x)= 1$$의 해인 $$M$$개의 $$x$$를 찾는 알고리즘이며, 앞서 소개된 알고리듬과 달리 지수적인 속도 상승을 보여주지는 못하지만 고전적 알고리듬보다 제곱근의 시간 복잡도를 갖는다.

* 구현
입력 $$\left| \left.  x \right\rangle \right. \left| \left.  q \right\rangle \right. $$ 에 대하여 출력 $$\left| \left.  x \right\rangle \right. \left| \left.  f(x) \oplus q \right\rangle \right. $$ 를 내보내는 오라클(oracle) $$O$$ 가 존재한다고 가정하자.

# 하다마드 [[게이트]]를 사용하여 $$\left| \left.  0 \right\rangle \right. ^{\otimes n}$$을 $${\frac{1}{\sqrt{2^{n}}}\left( \left.  \left| 0 \right.  \right\rangle + \left.  \left| 1 \right.  \right\rangle \right)}^{\otimes n}$$으로 변환, 보조 큐비트 $$\left| \left.  q \right\rangle \right. $$는 $$\left| \left.  1 \right\rangle \right. $$에 하다마드 게이트를 사용하여 $$\frac{1}{\sqrt{2}}\left( \left.  \left| 0 \right.  \right\rangle - \left.  \left| 1 \right.  \right\rangle \right)$$로 변환
# 오라클 $$O$$를 적용
# $$\left| \left.  x \right\rangle \right. $$에 대하여 하다마드 게이트를 적용
# 조건부 위상 변조(conditional phase shift)를 적용하여 $$\left| \left.  x \right\rangle \right.  \rightarrow - ( - 1)^{\delta _{x0}}\left| \left.  x \right\rangle \right. $$ 로 변환(여기에서 $$\delta$$는 크로네커 델타)
# $$\left| \left.  x \right\rangle \right. $$에 대하여 하다마드 게이트를 적용
# 2)~5) 를 반복 적용한 후 측정하여 $$f(x)= 1$$인 $$x$$를 얻음

3)~5) 과정은 ‘평균에 대한 반전(inversion about average)’ 이라고 불리며, 모든 계산기저의 평균이라고 할 수 있는 1) 단계 이후의 상태에 대해 뒤집는 변환을 말한다. 해당 상태는 하다마드 게이트에 의해 $$\left| \left.  0 \right\rangle \right. ^{\otimes n}$$으로 변환되므로 4) 단계의 앞뒤로 하다마드 게이트를 적용하여 평균에 대한 반전을 구현할 수 있다. 이러한 과정은 찾고자 하는 해가 측정될 확률을 증폭시켜줄 수 있는데, 2) 단계에서 오라클에 의해 $$f(x)= 1$$인 $$\left| \left.  x \right\rangle \right. $$들의 위상이 뒤집히기 때문이다. 그러나 일정 횟수 이상 실행하면 오히려 확률을 떨어뜨리기 때문에, 매번 증폭시키지는 않는다.

2)~5) 과정은 해 공간(solution space)에서 $$\theta$$ 회전에 해당하며,

\[\sin\theta= \frac{2\sqrt{M(N - M) }}{N}\]

$$M \ll N$$이면,

\[\theta \approx \sin\theta \approx 2\sqrt{\frac{M}{N}}\]

최대 $$\frac{\pi}{2} $$의 회전이 필요하므로 $$\theta$$ 회전의 개수는,

\[R \leq \left\lceil \frac{\pi}{4}\sqrt{\frac{N}{M}} \right\rceil\]

이다. 따라서 시간 복잡도는 $$O(\sqrt{N/M})$$ 이며 이는 고전 컴퓨터 알고리듬의 시간 복잡도 $$O(\frac{N}{M})$$ 에 비해 제곱근만큼 빠르게 작동한다. 이는 그로버 알고리듬이 $$N$$개의 입력을 동시에 처리함을 보여준다. 그러나 이를 위해서는 적절한 오라클을 구현하는 것이 중요하다.

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

요약:

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

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

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

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

둘러보기 메뉴

검색