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

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

= 단열 양자 컴퓨팅 (Adiabatic Quantum Computing) =

== 개요==

단열 양자 컴퓨팅(Adiabatic quantum computing, AQC)은 계산하고자 하는 바를 양자 시스템의 해밀토니안(Hamiltonian)의 형태로 변환하고 이를 조작하여 결과값을 유도하는 양자 컴퓨팅의 한 형태이다. 게이트 기반 양자 컴퓨팅 모델(양자 회로 모델)과 같이 임의의 연산을 모델링 할 수 있다는 점에서, 즉 범용성(universality)을 보장한다는 점에서 큰 의미를 지닌다.<ref name=Hogg>T. Hogg, Quantum search heuristics, Physical Review A 61, 052311 (2000). doi:[https://doi.org/10.1103/PhysRevA.61.052311 10.1103/PhysRevA.61.052311].</ref> 그러나 대개 AQC는 특정 최적화 문제를 빠른 시간 안에 풀기 위한 양자 이점(quantum advantage)의 목적으로 사용되며, 보다 나은 성능을 위해 양자 어닐러(quantum annealer, QA) 혹은 양자 교대 연산자 가설풀이(quantum alternating operator ansatz)의 형태로 변용된다.

단열 양자 컴퓨팅은 Max Born과 Vladimir Fock이 정리한 단열 정리에 이론적 뿌리를 두고 있다<ref name=Born>M. Born &amp; V. Fock, Beweis des Adiabatensatzes, Zeitschrift für Physik 51, 165 (1928). doi:[https://doi.org/10.1007/BF01343193 10.1007/BF01343193].</ref>. 단열 정리에 따르면 임의의 양자 시스템에 대해 외부 조건이 충분한 시간 동안 천천히 변화하고, 해밀토니안의 에너지 스펙트럼 간의 차이가 존재할 때(non-degenerate) 해당 양자 시스템의 고유 상태(instantaneous eigenstate)가 지속된다. 해밀토니안이 변화하여 양자 시스템의 상태 공간도 변하지만, 변화가 충분히 천천히 일어난다면 시스템이 이에 적응하여 에너지 상태의 확률 분포도 대응하여 변화한다는 것이다.

단열 정리가 함의하는 바는 주어진 계산(혹은 최적화) 문제를 양자 시스템의 단열 과정(adiabatic process)으로 표현할 수 있다는 것이다. 우선, 이미 잘 알려진 바닥 상태를 지니는 초기 해밀토니안($$H_{\text{init}}$$)을 설정한다. 그리고 주어진 계산 문제의 해를 바닥 상태로 지니는 해밀토니안($$H_{\text{final}})$$을 설정한 뒤, 최종 해밀토니안($$H(t)$$)을 둘의 가중 평균($$H(s)= (1 - s)H_{\text{init}} + sH_{\text{final}}$$)으로 나타낸다. 슈뢰딩거 방정식에 따라 단열 과정을 진행하면 adiabatic 정리에 의해 초기 해밀토니안의 바닥 상태는 최종 해밀토니안의 바닥 상태로 변화하게 된다. 따라서 주어진 계산 문제는 최종 해밀토니안의 바닥 상태를 알아내는 쉬운 문제로 전환된다.

\[{H(s)= (1 - s)H_{\text{init}} + sH_{\text{final}}}\]
\[{H(0)= H_{\text{init}}}\]
\[{H(s)= H_{\text{final}} ~(s는~1에~매우~가까움)}\]

이 때 외부 조건이 얼마나 천천히 변화해야 하는지, 바꿔 말해 AQC가 완료되기까지 요구되는 실행 시간에 대해 정확히 알아내는 것은 어렵다. 나아가 실제 고전 컴퓨터보다 성능 상의 이점([[양자 이점]])이 있는지에 대해서도 알려진 바가 없다. 다만 해밀토니안의 에너지 스펙트럼 간의 차이가 클수록 고유 상태가 다른 상태로 변화할 가능성이 낮아져 빠른 실행이 가능하다. 실행 시간은 해밀토니안의 에너지 스펙트럼 간의 차이의 최소값의 제곱에 반비례하는 것으로 알려져 있다<ref name=Farhi>E. Farhi, J. Goldstone, S. Gutmann &amp; M. Sipser, Quantum Computation by Adiabatic Evolution, [https://arxiv.org/abs/quant-ph/0001106 arXiv:quant-ph/0001106] (2000).</ref>

== 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>최종 해밀토니안은 시간에 따라 초기 해밀토니안에서 최종 해밀토니안으로 변화하도록 두 해밀토니안의 가중 평균으로 설정한다. 이 때, 최종 해밀토니안은 초기 상태$$(t= 0)$$에서는 1)에서 구성한 바닥 상태에 머물게 되며, 단열 정리에 의해 단열 과정이 끝난 뒤$$(t \rightarrow \infty)$$에는 최종 해밀토니안의 바닥 상태, 즉 최적해와 같은 상태에 놓이게 된다. 실제로는 여러 제반 사항을 고려하여 최대 사용할 시간 $$T$$를 정한 뒤 시간에 따른 변화를 기술한다.</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>이론적으로 충분한 시간이 주어지면$$(time \rightarrow \infty),$$ 최종 측정 결과는 100% 확률로 최적해와 동일해야 한다. 당연하게도 실제 상황에서는 제약 조건 등을 고려하여 최대 사용할 시간 $$T$$를 정한 뒤, 오차 범위 이내에서 근사하는 과정이 필요하다.
</li>
</ol>

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

== 양자 어닐링 (Quantum Annealing, QA)과 양자 교대 연산자 가설풀이 (Quantum Alternating Operator Ansatz) ==

[[File:기술백서 전체수정_20.jpg|thumb|300px|D-wave systems에서 개발한 양자 어닐링 컴퓨터<ref name=Dwave/>.
]]

양자 어닐링(quantum annealing)은 [[AQC]]와 유사한 방식으로 최적화 문제를 풀기 위해 고안된 기술로 효율적인 실행 시간이 보장되지 않는 AQC의 문제점을 해결하기 위해 열역학적 현상을 이용해 양자 터널링(quantum tunneling) 기술을 이용하여 빠른 시간 안에 많은 상태를 탐색하도록 하는 기술이다. 양자 어닐링의 경우 AQC와 달리 범용성을 보장하지 않기 때문에 실제 특정 최적화 문제를 풀기 위해서만 사용된다. 캐나다의 D-wave systems는 양자 어닐링을 이용한 [[양자 컴퓨터]]를 상용화한 바 있다<ref name=Dwave>D-wave systems : https://docs.dwavesys.com/docs/latest/c_gs_2.html.</ref>.

양자 어닐링은 양자 터널링 현상을 이용해 AQC에 비해 단열 과정을 구현하기 쉽고 빠르게 작동하도록 만든다는 특징이 있다. 단열 정리의 조건을 만족시키기 위해서는 상태 공간의 변화 속도를 충분히 느리게 해야 하는데, AQC의 문제점은 현실적으로 이러한 조건을 만족시키는 것이 매우 어렵고 계산 시간이 느리다는 것에 있다. 빠르게 변화하는 상태 공간에 대해서는 해밀토니안의 고유 상태가 이를 쫓아가지 못하게 되고, 이에 따라 변화하는 시스템에서의 에너지 준위는 달라지게 된다. 쉽게 말해, 단열 과정에서 바닥 상태가 더 이상 유지되지 못하게 되어 오랜 시간이 지나도 전역적 해와 일치하지 않게 될 확률이 증가하는 것이다. 현실적으로 AQC는 구현하기 어려우며 여러가지 제약으로 인해 단열 과정에서 고유 상태가 극소(local minimum)에 머무르게 되는 현상이 발생할 수 있다.

이러한 문제를 해결하기 위해 양자 어닐링은 수직 방향 장(transverse field)를 가하여 양자 터널링(quantum tunneling) 현상을 발생시켜 극소에서 벗어날 수 있도록 한다. 양자 터널링 현상은 임의성을 지니고, 결정적이지 않으므로 최종 결과값의 최적성을 보장할 수 없는 휴리스틱(heuristic) 기술이다. 대신 양자 어닐러는 다수의 시뮬레이션을 실행하여 전역해에 가까운 값을 찾도록 시도한다. 양자 어닐러의 성능에 관해서는 논란이 있지만 현재 시점에서는 [[양자 이점]]이 없는 것으로 결론이 모아지고 있다<ref name=Ronnow>T. F. RØNNOW ''et al.'', Defining and detecting quantum speedup, Science 345, 420 (2014). doi:[https://doi.org/10.1126/science.1252319 10.1126/science.1252319].</ref>.

양자 교대 연산자 가설풀이(quantum alternating operator ansatz)도 AQC에 기반하여 최적화 문제를 푸는 양자 컴퓨팅 기술로 AQC와 달리 초기 해밀토니안과 최종 해밀토니안을 교대로 적용하는 방식으로 작동한다. 본질적으로 임의성을 지니는 양자 어닐링에서와 달리 양자 교대 연산자 가설풀이의 경우 교대(alternation) 적용 횟수를 늘릴수록 최적해를 찾을 확률을 높일 수 있다. 양자 교대 연산자 가설풀이는 이론적으로 완벽하지만 현실에서 구현하기 어려운 AQC와 현실에서 잘 동작하지만 최적해를 찾기 어려운 QA의 절충된 형태로 볼 수 있다<ref name=Hadfield>S. Hadfield ''et al.'', From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, [https://arxiv.org/abs/1709.03489 arXiv:1709.03489] (2017). 
</ref>.

<blockquote>
[[File:기술백서 전체수정_21.jpg|center|thumb|400px|양자 터널링 현상의 그래프 표현. 참고문헌 <ref>https://en.wikipedia.org/wiki/Quantum_annealing</ref>의 그림을 재구성함.
]]
</blockquote>

[[분류:단열 양자컴퓨팅 | ]]

요약:

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

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

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

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

둘러보기 메뉴

검색