양자컴퓨팅 (Quantum Computing) 편집하기 (부분)

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

== AQC 계산 모델과 최적화 문제 ==

단열 양자 컴퓨팅(AQC)은 범용성(universality)을 지닌 것으로 알려져 있지만, 임의의 문제를 AQC 문제로 변환하는 것은 쉽지 않기 때문에 대부분의 범용 양자 컴퓨터는 게이트 기반 모델을 채택하여 연구되고 있다. 그러나 고전 컴퓨터가 해결하기 어려운 것으로 잘 알려진 NP 문제들의 전역적 최적해를 찾는 문제들에 대해서는 AQC 문제로 변환하는 과정이 간단하며, 현재 대부분의 AQC 기반 모델들은 이러한 최적화 문제를 해결하기 위해 사용되고 있다.

AQC 모델을 기반으로 알고리듬을 설계할 때 최종 해밀토니안($$H_{\text{final}})$$의 바닥 상태를 찾아내는 것은 매우 어렵다. 반면 최적화 문제에 대해서는 최종 해밀토니안의 바닥 상태가 계산하고자 하는 최적화 문제의 해답과 일치하도록 구성하는 것은 쉽다. 이는 대개 NP 문제의 특성에서 기인한다. NP 문제의 특징은 문제 공간은 지수적으로 크지만, 문제를 기술하거나 찾은 답을 확인하기 위한 절차는 간소하다는 것이다. 대부분의 경우 최적해가 만족해야 할 성질은 사람이 쉽게 모델링 할 수 있다. 이러한 모델링을 기반으로 최적해가 만족해야 할 성질을 만족하지 않는 상태에 대해 페널티를 부과하면 아무런 페널티도 없는 상태, 즉 바닥 상태는 최적해의 답이 된다. 나아가, 이러한 모델링은 최적해를 찾을 수 없는 문제에 대해서도 페널티를 최소화하는 답을 도출해낸다는 점이다. SAT, Max-Cut 등 유명한 문제에 대해서는 해밀토니안 구성 방법이 이미 개발되어 있다.

최적화 문제를 AQC 모델을 이용해 푸는 과정은 다음 같다.

# 쉽게 구성할 수 있는 초기 상태를 그라운드로 지니는 초기 해밀토니안을 설정한다. 임의의 상태를 그라운드로 설정하는 것은 어려운 일이므로 쉽게 만들 수 있는 초기 상태를 그라운드로 설정하는 것이 중요하다. 일반적으로 초기 상태는 균등 분포를 지니도록 한다.
# 계산하고자 하는 최적화 문제의 해답을 바닥 상태로 가지는 최종 해밀토니안을 설정한다. 대부분의 경우 이 과정은 간단하게 수행된다.
<blockquote>예. 3-SAT 문제

3-SAT 문제는 3개의 부울 표현식으로 구성된 항들을 모두 만족시키는 해가 있는지 찾는 문제로 대표적인 NP 문제이다.$$ C_{1}, C_{2},\ldots, C_{M}$$ 의 $$M$$개의 항으로 구성된 3-SAT 문제가 주어졌다고 가정하자. 이 때, AQC를 위한 목적 해밀토니안을 아래와 같이 구성하면 각 항들을 만족시키지 않는 상태에 대해서 페널티를 부과하게 된다. 따라서 아무런 페널티도 없는 바닥 상태와 최적해가 일치하게 된다.

</blockquote>

\[h_{C}\left( z_{i_C}, z_{j_C}, z_{k_C} \right)= \begin{cases}

0,  &   \left( z_{i_C}, z_{j_C}, z_{k_C} \right)\text{가 $C$를 만족시킬 때} \\

1,  & \left( z_{i_C}, z_{j_C}, z_{k_C} \right)\text{가 $C$를 만족시키지 않을 때}\\

\end{cases} \]

<ol start="3" style="list-style-type: decimal;">
<li><p>최종 해밀토니안은 시간에 따라 초기 해밀토니안에서 최종 해밀토니안으로 변화하도록 두 해밀토니안의 가중 평균으로 설정한다. 이 때, 최종 해밀토니안은 초기 상태$$(t= 0)$$에서는 1)에서 구성한 바닥 상태에 머물게 되며, 단열 정리에 의해 단열 과정이 끝난 뒤$$(t \rightarrow \infty)$$에는 최종 해밀토니안의 바닥 상태, 즉 최적해와 같은 상태에 놓이게 된다. 실제로는 여러 제반 사항을 고려하여 최대 사용할 시간 $$T$$를 정한 뒤 시간에 따른 변화를 기술한다.</p></li>
</ol>

\[H(t)= (1 - t/T)H_{\text{init}} + (t/T)H_{\text{final}}\]

\[H(s) = (1 - s)H_{\text{init}} + sH_{\text{final}} ~(s = \frac{t}{T})\]

<li><p>이론적으로 충분한 시간이 주어지면$$(time \rightarrow \infty),$$ 최종 측정 결과는 100% 확률로 최적해와 동일해야 한다. 당연하게도 실제 상황에서는 제약 조건 등을 고려하여 최대 사용할 시간 $$T$$를 정한 뒤, 오차 범위 이내에서 근사하는 과정이 필요하다.</p>
</li>
</ol>

특정 경우에 대해서는 AQC를 이용한 최적화 문제 해결이 다항 시간 안에 수행되는 것으로 알려져 있지만, 일반적인 경우에 대해서 다항 시간을 보장할 수 없고, 나아가 [[양자 이점]]이 있는지도 명확하지 않다. 오히려 단순한 AQC 모델은 실행 시간과 관련하여 결함을 지니고 있을 것으로 예측되며, 이러한 시간 문제를 해결하기 위한 [[양자 어닐링]]과 같은 기술이 사용된다.

요약:

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

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

원본 주소 "https://wiki.qisk.or.kr/양자컴퓨팅_(Quantum_Computing)"

양자컴퓨팅 (Quantum Computing) 편집하기 (부분)

둘러보기 메뉴

검색