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

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

= 양자 위상 추정 (Quantum Phase Estimation) =

[[양자 푸리에 변환]]을 이용하여 특정 유니타리(unitary) 연산자 $$U$$의 고윳값(eigenvalue) $$e^{2\pi i\varphi}$$ 을 추정하는 알고리듬을 양자 위상 추정이라고 한다. 고윳값에 해당하는 고유벡터(eigenvector) $$\left| \left.  u \right\rangle \right. $$와 controlled-$$U^{2^{j}}$$ [[게이트]]가 주어졌다고 가정하자. 양자 위상 추정 알고리듬은 위상 추정을 위한 $$t$$개의 [[큐비트]]와 $$\left| \left.  u \right\rangle \right. $$를 표현하기 위해 필요한 [[큐비트]]를 사용한다.

* 구현
$$t$$개의 [[큐비트]]를 $$\left| \left.  0 \right\rangle \right. $$으로 초기화한 후 하다마드 [[게이트]]를 적용한다. 이후 $$t$$개의 [[큐비트]]를 컨트롤로 하여 $$t$$개의 controlled-$$U^{2^{j}}$$ 게이트를 아래 그림에서와 같이 적절히 수행하면 출력은 다음과 같은 형태가 된다.

\[\frac{1}{2^{\frac{t}{2}}}\left( \left| \left.  0 \right\rangle \right.  + e^{2\pi i 2^{t - 1}\varphi}\left| \left.  1 \right\rangle \right.  \right)\left( \left| \left.  0 \right\rangle \right.  + e^{2\pi i 2^{t - 2}\varphi}\left| \left.  1 \right\rangle \right.  \right)\ldots \left( \left| \left.  0 \right\rangle \right.  + e^{2\pi i 2^{0}\varphi}\left| \left.  1 \right\rangle \right. \right) = \frac{1}{2^{\frac{t}{2}}}\sum_{k =0}^{2^{t} - 1}{e^{2\pi i\varphi k}\left| \left.  k \right\rangle \right.  }\]

해당 출력에 역 양자 푸리에 변환(inverse QFT)을 적용할 때 출력은 다음과 같다.

\[\frac{1}{2^{\frac{t}{2}}}\sum_{k= 0}^{2^{t} - 1}{e^{2\pi i\varphi k}\left| \left.  k \right\rangle \right.  } \rightarrow \left| \left.  \widetilde{\varphi} \right\rangle \right. \]

여기에서 $$\widetilde{\varphi}$$는 $$\varphi$$의 $$t$$-비트 근사값이 된다. 따라서 $$t$$개의 [[큐비트]]를 측정하면 고윳값 $$\varphi$$의 근사값을 얻는다.

각각의 controlled-$$U^{2^{j}}$$ 게이트가 상수시간으로 실행됨을 가정하면 시간 복잡도는 [[양자 푸리에 변환]]과 동일하게 $$O(t^{2})$$이 된다. $$U$$게이트의 고윳값이 $$t$$개의 [[큐비트]]로 나타낼 수 없는 경우에는 추정에 사용하는 [[큐비트]]의 개수를 늘림으로써 정확도를 상승시킬 수 있다.

만약 $$1 - \varepsilon$$의 확률로 $$2^{- n}$$의 정밀도로 올바른 추정값을 얻기 위해서는

\[t= n + \left\lceil \log\left( 2 + \frac{1}{2\varepsilon} \right) \right\rceil\]

개의 [[큐비트]]가 필요하다.<ref name=Nielsen>M. A. Nielsen and I. L. Chuang, ''Quantum computation and quantum information'' (Cambridge University Press, 2002)</ref>

요약:

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

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

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

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

둘러보기 메뉴

검색