양자 어닐링

양자 어닐링은 양자 역학적 현상을 이용하여 수학적 최적화 문제를 해결하는 방법론이다. 특히 탐색 공간이 이산적이고 수많은 국소 최솟값이 존재하는 조합 최적화 문제에서 전역 최솟값을 찾는 데 효과적이다. 고전적인 시뮬레이티드 어닐링이 열적 요동을 이용해 에너지 장벽을 넘는 것과 달리, 양자 어닐링은 양자 터널링을 통해 장벽을 통과하여 더 효율적으로 최적해를 탐색한다.

양자 어닐링이라는 용어는 1988년 B. 아폴로니, N. 체사 비안키, D. 드 팔코에 의해 양자 영감을 받은 고전 알고리즘으로 처음 제안되었다. 이후 1994년 A. B. 핀닐라 등이 양자 결맞음이 없는 허수 시간 변형에 대해 논의하였으며, 1998년 T. 가도와키와 H. 니시모리에 의해 현재의 수식화된 형태로 정립되었다.

양자 어닐링의 과정은 다음과 같은 단계로 진행된다.

1. 초기화: 모든 가능한 상태가 동일한 가중치를 가지는 양자역학적 중첩 상태에서 시작한다.
2. 진화: 시스템은 시간에 의존하는 슈뢰딩거 방정식을 따라 진화한다. 이때 횡단 필드(transverse field)의 강도를 조절하여 양자 터널링을 유발한다.
3. 단열 과정: 횡단 필드의 변화율이 충분히 느리면 시스템은 순간 해밀토니언의 바닥 상태를 유지하며 최적해에 접근한다. 이를 단열 양자 계산이라 한다.
4. 종료: 최종적으로 횡단 필드를 끄면 시스템은 원래 최적화 문제의 해에 해당하는 고전 이징 모형의 바닥 상태에 도달하게 된다.

양자 어닐링은 다양한 복잡한 문제 해결에 응용된다.

• 조합 최적화: 외판원 문제(TSP), 최대 절단(Max-Cut), 그래프 색칠 문제 등.
• 물리학 연구: 스핀 유리(spin glass)의 바닥 상태 탐색.
• QUBO 문제: 제약 없는 이차 형식 이진 최적화(Quadratic Unconstrained Binary Optimization) 문제를 해결하는 데 주로 사용된다.