기술 요약: 조합 최적화를 위한 양자 정보 기반 대리 샘플링 (QISS)

1. 문제 정의

MaxCut(최대 컷) 및 MIS(최대 독립 집합)와 같은 조합 최적화 문제는 규모가 커질수록 계산적으로 매우 까다로워집니다. 양자 근사 최적화 알고리즘(QAOA)은 유망한 하이브리드 양자-고전 접근 방식을 제공하지만, 노이즈와 결맞음(coherence)의 한계로 인해 현재의 근시-기기(near-term) 하드웨어에서의 성능이 제약됩니다. 이러한 제약은 일반적으로 QAOA 구현을 얕은 회로(낮은 깊이 $p$)로 제한합니다.

얕은 QAOA의 근본적인 한계는 **국소성(locality)**입니다. 희소 그래프(sparse graphs)의 경우, 회로의 "라이트 콘(light cone)"은 문제의 크기 $N$이 아니라 깊이 $p$에 의해 제한됩니다. 결과적으로, 고정된 $p$를 사용하는 QAOA는 전역적인 문제 구조를 활용하지 못하며, 로컬 클래식 알고리즘과 유사한 한계를 물려받게 됩니다. 또한, 양자 상태의 전체 출력 분포는 일반적으로 고전적으로 샘플링하기 불가능하며, 얕은 깊이에 제한된 양자 장치는 직접적으로 고품질의 해를 생성할 수 없습니다.

본 논문은 근시 양자 장치의 강점인 저차 로컬 통계량(low-order local statistics)의 효율적인 추정 능력을 활용하는 동시에, 후보 해 생성 작업은 확장 가능한 고전적 후처리 과정으로 위임하는 방법의 필요성을 다룹니다.

2. 방법론: 양자 정보 기반 대리 샘플링 (QISS)

저자들은 샘플링 단계에서 조합 문제의 구조에 대한 명시적인 의존성 없이도 저중량 양자 상관관계(low-weight quantum correlations)로부터 후보 해를 생성하는 후처리 프레임워크인 **양자 정보 기반 대리 샘플링(QISS)**을 제안합니다.

핵심 워크플로우

1. 양자 추정: 양자 장치(또는 시뮬레이터)에서 선택된 저중량 기댓값(상관관계) $\mu_{S_\alpha}$를 추정하기 위해 얕은 QAOA 회로(깊이 $p$)를 실행합니다:
   $$\mu_{S_\alpha} = \langle \psi_p(\gamma, \beta) | \prod_{i \in S_\alpha} Z_i | \psi_p(\gamma, \beta) \rangle$$
   본 논문은 가중치 $|S_\alpha| \in \{1, 2\}$에 집중합니다. 이 값들은 반복 측정을 통해 접근 가능하며 오차 완화(error mitigation)에 용이합니다.

2. 대리 분포 구축: 측정된 상관관계들을 파라미터로 사용하여 해 공간 $\{-1, +1\}^N$에 대한 고전적 인자 분포 $P(z)$를 구축합니다:
   $$P(z) \propto \prod_{S_\alpha \in \mathcal{S}} \left( 1 + \mu_{S_\alpha} \chi_{S_\alpha}(z) \right)$$
   여기서 $\chi_{S_\alpha}(z) = \prod_{i \in S_\alpha} z_i$는 패리티 함수입니다. 이 분포는 결합 상수 $J_{S_\alpha} = -\text{arctanh}(\mu_{S_\alpha})$를 갖는 유효 이징 해밀토니안(effective Ising Hamiltonian) $H'$의 깁스 분포와 동일합니다.

3. 고전적 샘플링: 마르코프 연쇄 몬테카를로(MCMC)를 사용하여 $P(z)$로부터 후보 해를 추출합니다. 샘플링은 단일 사이트 조건부 업데이트(single-site conditional updates)를 사용하며, 이는 스핀 플립에 대한 조건부 확률이 해당 스핀을 포함하는 로컬 인자에만 의존하기 때문에 매우 효율적입니다. 정규화 상수(분배 함수)는 전혀 필요하지 않습니다.

4. 상관관계 선택: 본 논문은 두 가지 상관관계 세트를 구분합니다:

   • 에지 세트 ($\mathcal{S} = E \cup V$): 문제 그래프의 직접적인 에지만 포함합니다. 국소 트리 구조(locally tree-like) 그래프에서는 QAOA의 모멘트를 재현할 뿐 개선을 가져오지 못합니다.
   • 확장된 세트 ($\mathcal{S}' = E' \cup V$): 라이트 콘 거리 $d_G(i, j) \le 2p$ 내의 모든 쌍 $(i, j)$를 포함합니다. 이는 조밀하고 비-트리 형태의 인자 그래프(factor graph)를 생성하여, 대리 모델이 고차 상관관계를 암시적으로 포착하고 원시 QAOA 출력보다 우수한 해를 생성할 수 있게 합니다.

주요 특징

• 훈련 불필요(Training-Free): 이 방법은 고정된 트리 최적 QAOA 각도(Ref. [61]에서 가져옴)를 사용하므로, 대리 모델의 변분 최적화(variational optimization)를 요구하지 않습니다.
• 모듈성: 샘플링 단계는 비용 함수에 무관(agnostic)하며, 오직 상관관계만을 필요로 합니다.
• 노이즈 탄력성: 상관관계에서 결합 상수로의 매핑($\text{arctanh}$)은 매끄럽기 때문에, 측정된 통계량의 노이즈에 대해 대리 모델이 견고합니다.

3. 주요 기여 및 결과

A. 3-정규 그래프에서의 MaxCut

• Vanilla QAOA 대비 성능: 확장된 상관관계 세트(거리 $2p$ 내의 모든 쌍)를 사용할 때, QISS는 vanilla QAOA를 크게 능가합니다. 구체적으로, 깊이 $p=3$ 또는 $p=4$ QAOA 회로의 상관관계를 사용한 QISS는 트리 최적 각도가 알려진 최대 깊이인 $p=17$의 vanilla QAOA보다 더 높은 평균 컷 비율(cut fraction)을 달성합니다.
• 웜 스타트 통합: 이 방법은 정규화된 웜 스타트 QAOA(RWS-QAOA)와 결합되었습니다. 얕은 깊이($p=1, 2$)에서도 QISS 후처리는 RWS-QAOA의 해 품질을 개선하여 근사 비율을 최적 경계에 가깝게 밀어 올렸습니다.
• 하드웨어 검증: 실험은 54-큐비트 IQM Emerald QPU에서 수행되었습니다. 결과는 QISS가 노이즈에 매우 강하다는 것을 보여주었습니다. 원시(raw) 노이즈가 있는 QPU 상관관계로부터 얻은 근사 비율은 노이즈 없는 시뮬레이션에서 얻은 결과와 거의 구별할 수 없을 정도로 유사했습니다. 즉, 후처리 과정을 통해 장치의 노이즈가 효과적으로 "씻겨 내려갔으며", 이 영역에서는 복잡한 오차 완화 기술이 최종 해의 품질에 큰 영향을 미치지 않았습니다.
• 확장성: 이 방법은 $N=140$까지 성능을 유지했습니다(변수 동결 후 사용 가능한 큐비트 수에 의해 제한됨). 근사 비율은 안정적으로 유지되었으며 표준 SDP 보증치를 훨씬 상회했습니다.

B. 최대 독립 집합 (MIS)

• 제약 조건 처리: MaxCut과 달리 MIS는 제약이 있는 문제입니다. QISS 샘플에는 충돌(인접한 노드가 모두 선택됨)이 포함될 수 있습니다. 저자들은 충돌을 해결하고 유효한 노드를 탐욕적으로 추가하기 위한 간단한 후처리 가지치기(pruning) 루틴을 도입했습니다.
• 성능: MIS의 경우, 에지 상관관계만을 사용하면 $Z_2$ 대칭성과 중첩된 인자의 부재로 인해 vanilla QAOA보다 성능이 떨어졌습니다. 그러나 확장된 상관관계 세트와 가지치기 루틴을 결합하여 사용했을 때, QISS는 단독 QAOA를 능가하고 최첨단 고전적 휴리스틱(예: 선형 우선순위 탐색 및 양자 강화 탐욕 알고리즘)과 경쟁할 수 있는 수준에 도달했습니다.

C. 고전적 솔버와의 비교

QISS는 Simulated Annealing(SA) 및 Goemans–Williamson SDP의 Burer–Monteiro(BM) 랭크-2 완화(relaxation)와 벤치마킹되었습니다.

• RWS-QAOA와 결합된 QISS는 BM 솔버와 경쟁할 만한 결과를 생성했습니다.
• 고정된 시간 예산 하에서 시스템 크기가 증가함에 따라 성능이 저하되는 고전적 샘플러와 달리, QISS는 $N$에 관계없이 안정적인 QAOA 상관관계의 국소성을 활용합니다.

4. 의의 및 주장

본 논문은 QISS가 얕은 양자 회로가 직접적인 샘플러가 아니라, 확장 가능한 고전적 샘플링을 위한 정보가 풍부한 통계량을 생성하는 역할을 수행하는 새로운 근시 최적화 영역을 구축한다고 주장합니다.

• 역할 분담: 양자 장치는 저차 로컬 관측량(노이즈에 강하고 샘플 비용이 시스템 크기에 독립적인)을 효율적으로 추정하는 데 사용되며, 고전 컴퓨터는 이러한 통계량을 전역적인 해로 합성하는 복잡한 작업을 처리합니다.
• 노이즈 탄력성: 대리 분포가 매우 견고하여, 가공되지 않은 노이즈 섞인 하드웨어 데이터로부터 근사 최적해를 복구할 수 있다는 점이 핵심적인 발견입니다. 이는 특정 최적화 작업의 경우, QISS와 같은 견고한 후처리 계층을 사용한다면 복잡한 오차 완화 오버헤드가 불필요할 수 있음을 시사합니다.
• 확장성: QISS는 깊은 회로의 고전적 수축(contraction)에 따른 지수적 확장을 피하고, 얕은 회로와 고전적 MCMC에 의존함으로써 현재 하드웨어에서 직접적인 양자 샘플링이 허용하는 것보다 더 큰 문제를 해결할 수 있는 경로를 제공합니다.

저자들은 Q while QISS가 측정된 상관관계의 특정 구조에 의존하지만, 근시 양자 장치의 성능을 향상시키기 위한 실용적이고 훈련이 필요 없으며 하드웨어 효율적인 경로를 제공한다고 결론짓습니다.