양자 어닐링

양자 어닐링은 수학적 최적화 문제를 해결하기 위해 양자 역학적 요동을 사용하는 방법론이다. 탐색 공간이 이산적이고 수많은 국소 최솟값이 존재하는 조합 최적화 문제에서 전역 최솟값을 찾는 데 효과적이다. 고전적인 시뮬레이티드 어닐링이 열적 요동을 통해 에너지 장벽을 넘는 것과 달리, 양자 어닐링은 양자 터널링을 통해 장벽을 직접 통과하여 더 효율적으로 최적해를 탐색한다. 이 과정은 시스템이 시간에 따라 변화하는 해밀토니언의 바닥 상태를 유지하도록 설계되는 단열 정리에 기반한다.

양자 어닐링이라는 용어는 1988년 B. 아폴로니, N. 체사 비안키, D. 드 팔코에 의해 양자 영감을 받은 고전 알고리즘으로 처음 제안되었다. 1994년 A. B. 핀닐라 등은 양자 결맞음이 없는 허수 시간 변형에 대해 논의하였으며, 현재의 수식화된 형태는 1998년 T. 가도와키와 H. 니시모리에 의해 정립되었다. 초기 연구는 주로 스핀 유리 모형의 바닥 상태 탐색에 집중되었으나, 이후 다양한 조합 최적화 문제로 확장되었다. 2010년대 들어 D-Wave Systems 사가 상용 양자 어닐링 프로세서를 출시하며 실용적 연구가 가속화되었다.

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

1. 초기화: 모든 가능한 상태가 동일한 가중치를 가지는 양자역학적 중첩 상태에서 시작한다. 이는 횡단 필드(transverse field)가 지배적인 초기 해밀토니언 $H_0$의 바닥 상태에 해당한다.
2. 진화: 시스템은 시간에 의존하는 슈뢰딩거 방정식을 따라 진화한다. 전체 해밀토니언은 $H(t) = A(t) H_0 + B(t) H_P$로 표현되며, 여기서 $H_P$는 최적화하려는 문제의 비용 함수를 나타낸다. $A(t)$와 $B(t)$는 시간에 따라 조절되어 초기에는 $A \gg B$, 최종에는 $B \gg A$가 된다.
3. 단열 및 비단열 과정: 횡단 필드의 변화율이 충분히 느리면 시스템은 순간 해밀토니언의 바닥 상태를 유지하며 최적해에 접근한다(단열 양자 계산). 변화율이 빠르면 시스템이 일시적으로 바닥 상태를 벗어날 수 있으나, 최종적으로 문제 해밀토니언의 바닥 상태에 도달할 확률을 높이는 비단열 과정이 활용되기도 한다.
4. 종료: 최종적으로 횡단 필드를 끄면 시스템은 원래 최적화 문제의 해에 해당하는 고전 이징 모형의 바닥 상태에 도달하게 된다.

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

• 조합 최적화: 외판원 문제(TSP), 최대 절단(Max-Cut), 그래프 색칠 문제, 충족 가능성 문제(SAT) 등.
• QUBO 문제: 제약 없는 이차 형식 이진 최적화(Quadratic Unconstrained Binary Optimization) 문제를 해결하는 표준적인 도구로 사용된다.
• 물류 및 경로 최적화: 대규모 창고 내 자율 주행 차량(AGV)의 경로 최적화와 실시간 우선순위 조절에 적용된다.
• 기계 학습 및 물리학: 특징 선택, 신경망 가중치 최적화, 스핀 유리(spin glass)의 바닥 상태 탐색 등 기초 과학 연구에 활용된다.