Fair sampling with temperature-targeted QAOA based on quantum-classical correspondence theory

기술 요약: 온도 타겟팅 QAOA를 통한 공정 샘플링 (Fair Sampling)

문제 정의
퇴화된 기저 상태(degenerate ground states)를 특징으로 하는 조합 최적화 문제에서, 편향 없이 모든 퇴화된 해에 대해 균등한 분포를 얻는 "공정 샘플링(fair sampling)" 능력은 매우 중요하다. 양자 어닐링(QA)과 양자 근사 최적화 알고리즘(QAOA)은 이러한 문제들을 위한 유망한 메타휴리스틱이지만, 횡장(transverse-field) 믹서를 사용하는 표준 구현 방식은 공정한 샘플링을 달emic 못하는 경우가 많다. 이론적 및 실험적 증거에 따르면, 회로 깊이(circuit depth)가 증가함에 따라 표준 QAOA는 퇴화된 상태들 사이에 편향을 유도하며, 근사 비율(approximation ratio)이 1로 수렴하더라도 특정 해를 선호하는 경향을 보인다. 기존의 해결책들, 예를 들어 특화된 믹서나 하이브리드 후처리 방식은 회로 복잡도를 높이거나 추가적인 고전적 계산 단계를 요구한다.

방법론
저자들은 믹서를 수정하는 대신, 양자-고전 대응 이론(quantum–classical correspondence theory)에 기반하여 타겟(비용) 해밀토니안을 재설계함으로써 샘플링 편향 문제를 해결하는 QAOA의 변형인 SBO-QAOA를 제안한다.

• 이론적 프레임워크: 표준 QAOA가 고전 이징 해밀토니안 $\hat{H}_0$의 기저 상태를 타겟팅하는 것과 달리, SBO-QAOA는 Somma 등이 제시한 유효 해밀토니안 $\hat{H}_S(T)$의 기저 상태를 타겟팅한다. 이 해밀토니안은 특정 온도 $T$에서 고전 시스템의 볼츠만 인자(Boltzmann factors)의 제곱근을 확률 진폭으로 갖는 양자 상태 $|\psi_{Gibbs}(T)\rangle$에 대응하도록 구성된다.
• 해밀토니안 구성: SBO 해밀토니안은 다음과 같이 정의된다:
  $$\hat{H}_S(T) = -e^{-\alpha/T} \sum_{i=1}^N \left( \hat{\sigma}_i^x - e^{\hat{H}_i/T} \right)$$
  여기서 $\hat{H}_i$는 스핀 $i$에 의존하는 $\hat{H}_0$의 국소 항(local terms)을 나타내며, $\alpha$는 $T \to 0$일 때 발산을 방지하는 스케일링 인자이다. SBO-QAOA에서는 $\hat{H}_C$를 $\hat{H}_S(T)$로 설정하고, 표준 횡장 믹서 $\hat{H}_X$는 그대로 유지한다.
• 파라미터화 방식: 본 연구는 변분 각도(variational angles) $\{\gamma_k, \beta_k\}$에 대해 두 가지 파라미터화 전략을 평가한다:
  1. 전체 파라미터(Full-parameter): 회로 깊이 $p$에 대해 $2p$개의 독립 변수를 사용한다.
  2. 선형화(Linearized): 각도가 깊이 인덱스의 선형 함수가 되도록 하여, 깊이에 관계없이 최적화 변수를 4개($\gamma_{slope}, \gamma_{intcp}, \beta_{slope}, \beta_{intcp}$)로 줄이는 축소 방식이다.
• 실험 설정: 6중 기저 상태 퇴화를 가진 5-스핀 좌절 이징(frustrated Ising) 토이 모델에 대해 수치 시뮬레이션을 수행하였다. 시스템은 정확한 비교(전체 행렬 진화)를 위해 정확하게 시뮬레이션되었으며, 다양한 회로 깊이($p=1$부터 $100$까지)와 온도에 걸쳐 표준 QAOA와 SBO-QAOA를 비교하였다.

주요 결과

• 표준 QAOA의 편향: 표준 QAOA( $\hat{H}_0$ 타겟팅)의 경우, 회로 깊이 $p$가 증가함에 따라 전체 기저 상태 확률($P_{GS}$)은 1을 향해 수렴한다. 그러나 퇴화된 부분 공간(subspace) 내의 분포는 여전히 편향되어 있으며, 전체 파라미터 또는 선형화된 파라미터를 사용하든 관계없이 특정 상태 쌍이 지배적으로 나타나고 다른 상태들은 억제된다.
• SBO-QAOA의 공정성: $\hat{H}_S(T)$를 타겟팅할 때, SBO-QAOA는 근본적으로 다른 동작을 보인다:
  • 온도 타겟팅: 전체 기저 상태 확률 $P_{GS}$는 1로 접근하지 않고, 지정된 온도 $T$에서의 깁스 분포 확률과 일치하는 값(예: $T=1$일 때 $\approx 0.83$)에서 포화된다.
  • 균등 샘플링: $p$가 증가함에 따라, 퇴화된 기저 상태들에 대한 확률 분포는 균등해진다. 서로 다른 상태 쌍들의 확률이 동일한 값으로 수렴하며, 이는 공정한 샘플링을 확인시켜 준다.
  • 총 변동 거리(Total Variation Distance, TVD): 출력 분포와 타겟 깁스 분포 사이의 TVD는 $p$가 증가함에 따라 감소하여 0 근처로 수렴한다. 이는 알고리즘이 단순히 기저 상태뿐만 아니라 전체 유한 온도 분포를 재현함을 확인해 준다.
• 파라미터 축소에 대한 강건성: SBO-QAOA의 공정 샘플링 및 온도 타겟팅 특성은 변수가 $2p$에서 단 4개로 줄어든 선형화 방식에서도 유지된다.

의의 및 주장
본 논문은 믹서의 복잡도를 높이거나 고전적인 후처리 단계를 추가하지 않고도 QAOA에서 공정한 샘플링을 달성할 수 있다고 주장한다. 타겟 해밀토니안을 SBO 해밀토니안으로 교체함으로써, 알고리즘은 깁스 분포를 그 기저 상태로서 내재적으로 인코딩한다. 저자들은 이 접근 방식이 다음을 가능하게 함을 입증하였다:

1. 공정 샘플링: 퇴화된 기저 상태들에 대해 균등한 분포를 달성함.
2. 온도 타겟팅: 파라미터 $T$를 통해 샘플링 분포를 제어함.
3. 효율성: 최소한의 변분 파라미터 세트(4개)를 유지하면서 이러한 특성을 유지하여, 최적화 복잡도 측면에서 확장 가능성을 높임.

저자들은 현재의 작업이 정확한 대각화(exact diagonalization)를 통해 소규모 시스템에서 이러한 특성들을 검증했음을 언급하며, 향-후 연구에서는 확장성 문제를 다루어야 한다고 밝혔다. 구체적으로, 게이트 기반 장치에서 $\hat{H}_S(T)$를 구현하려면 효율적인 파울리-스트링 확장(Pauli-string expansion)과 회로 분해가 필요한데, 이는 해당 해밀토니안이 일반적으로 다체 상호작용(many-body interactions)을 유발하기 때문이다.