양자 최적화 알고리즘: 하이브리드 컴퓨팅의 원리 및 응용

## 핵심 원리 고전-양자 하이브리드 컴퓨팅(Hybrid Quantum-Classical Computing, HQCC)은 양자 컴퓨터의 특정 연산 능력과 고전 컴퓨터의 정밀한 제어 및 최적화 능력을 결합하여 복잡한 문제를 해결합니다 (Lee, 2025, Journal of the Korea Academia-Industrial cooperation Society). 이 방식은 양자 장치가 양자 상태의 중첩과 얽힘을 활용하여 고차원 계산을 수행하고, 고전 컴퓨터가 이 양자 계산의 결과를 바탕으로 최적화 파라미터를 업데이트하는 반복적인 루프를 형성합니다. 가장 대표적인 양자 최적화 알고리즘 중 하나인 **변분 양자 고유값 알고리즘(Variational Quantum Eigensolver, VQE)**은 양자 시스템의 바닥 상태 에너지를 찾는 데 활용됩니다. VQE는 다음과 같은 단계로 작동합니다. 1. **양자 회로 초기화**: 양자 연산 장치(QPU)는 고정된 양자 회로 구조 $U(\vec{\theta})$를 사용하여 변분 양자 상태 $|\psi(\vec{\theta})\rangle$를 준비합니다. 여기서 $\vec{\theta}$는 회로의 게이트 파라미터를 나타냅니다. 2. **기댓값 측정**: 준비된 상태 $|\psi(\vec{\theta})\rangle$에 대해 해밀토니안 $H$의 기댓값 $\langle H \rangle = \langle \psi(\vec{\theta}) | H | \psi(\vec{\theta}) \rangle$를 측정합니다. 이는 양자 장치에서 여러 번의 측정으로 얻어집니다. 3. **고전 최적화**: 측정된 기댓값 $\langle H \rangle$를 목적 함수로 사용하여 고전 컴퓨터는 $\vec{\theta}$를 조정하여 $\langle H \rangle$를 최소화합니다. 경사 하강법이나 기타 고전 최적화 기법이 사용될 수 있습니다. 4. **반복**: 새로운 $\vec{\theta}$ 값으로 양자 회로를 재구성하고 2, 3단계를 반복하여 $\langle H \rangle$가 수렴할 때까지 이 과정을 수행합니다. 이때, 해밀토니안 $H$는 파울리 연산자들의 선형 결합으로 표현됩니다: $H = \sum_{k} h_k P_k$, 여기서 $P_k$는 파울리 연산자의 텐서 곱($I, X, Y, Z$)이고 $h_k$는 실수 계수입니다. 측정하고자 하는 기댓값은 다음과 같습니다: $$ E(\vec{\theta}) = \langle \psi(\vec{\theta}) | H | \psi(\vec{\theta}) \rangle = \sum_k h_k \langle \psi(\vec{\theta}) | P_k | \psi(\vec{\theta}) \rangle $$ 여기서 $\langle \psi(\vec{\theta}) | P_k | \psi(\vec{\theta}) \rangle$는 양자 장치에서 측정됩니다. 또 다른 핵심 알고리즘인 **양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm, QAOA)**은 조합 최적화 문제, 예를 들어 최대 컷(Max-Cut) 문제와 같은 난해한 문제를 해결하는 데 사용됩니다 (Lee, 2025). QAOA는 특정 해밀토니안을 따르는 양자 연산을 통해 목적 함수를 최적화합니다. QAOA는 $p$개의 층(layer)으로 구성된 양자 회로를 사용하며, 각 층은 문제 해밀토니안 $H_C$에 해당하는 연산자 $U_C(\gamma) = e^{-i\gamma H_C}$와 혼합 해밀토니안 $H_B$에 해당하는 연산자 $U_B(\beta) = e^{-i\beta H_B}$로 구성됩니다. 여기서 $\gamma = (\gamma_1, \dots, \gamma_p)$와 $\beta = (\beta_1, \dots, \beta_p)$는 고전적으로 최적화될 파라미터입니다. 알고리즘 단계는 다음과 같습니다. 1. **초기 상태 준비**: 모든 큐비트가 균일한 중첩 상태 $|+\rangle^{\otimes n}$로 초기화됩니다. 2. **양자 회로 적용**: 파라미터 $(\vec{\gamma}, \vec{\beta})$에 의해 정의된 양자 회로를 적용하여 최종 상태 $|\psi(\vec{\gamma}, \vec{\beta})\rangle = U_B(\beta_p) U_C(\gamma_p) \cdots U_B(\beta_1) U_C(\gamma_1) |+\rangle^{\otimes n}$를 생성합니다. 3. **기댓값 측정**: 이 상태에 대해 비용 해밀토니안 $H_C$의 기댓값 $\langle H_C \rangle = \langle \psi(\vec{\gamma}, \vec{\beta}) | H_C | \psi(\vec{\gamma}, \vec{\beta}) \rangle$를 측정합니다. 4. **고전 최적화**: 고전 컴퓨터는 측정된 $\langle H_C \rangle$를 최소화하는 $(\vec{\gamma}, \vec{\beta})$를 찾습니다. QAOA에서 비용 해밀토니안 $H_C$는 최적화하려는 이진 변수 문제의 목적 함수를 양자 연산자로 인코딩한 것입니다. 예를 들어, 2차 비제한 이진 최적화(QUBO) 문제의 경우 $H_C = \sum_{i<j} J_{ij} Z_i Z_j + \sum_i h_i Z_i$ 형태로 표현될 수 있습니다. 혼합 해밀토니안 $H_B$는 보통 $H_B = \sum_i X_i$로 정의되어 큐비트 상태를 혼합(superposition)하여 전역 최적해를 탐색하도록 돕습니다. 이러한 하이브리드 알고리즘들은 현재 NISQ(Noisy Intermediate-Scale Quantum) 시대의 양자 컴퓨터에서 가장 실현 가능성이 높은 접근 방식입니다. NISQ 장치는 50~100개 큐비트 범위에 있으며, 수 밀리초(ms) 수준의 짧은 결맞음 시간(coherence time)과 높은 오류율($10^{-2}$~ $10^{-3}$/게이트)을 가집니다. 따라서 복잡한 오류 수정 없이 회로 깊이가 제한되어야 합니다. VQE 및 QAOA는 이러한 제약 하에서 유