Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

기술 요약: 조합 최적화를 위한 생성적 양자 탐색 (Generative Quantum Search for Combinatorial Optimization)

문제 정의
본 연구는 얕은 양자 샘플러(shallow quantum samplers)가 "고전적 회복 베이슨(classical recovery basin)" 내에 더 높은 확률 질량을 배치함으로써 조합 최적화에서 고전적 샘플러보다 우수한 성능을 보일 수 있는지 조사한다. 본 연구는 원래 양자 화학 분야를 위해 개발된 GQE+QSCI(Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction) 아키텍처를 그래프 최적화(특히 최대 가중 독립 집합, MWIS) 영역에 맞게 변형하였다. 핵심 가설은 양자 샘플러가 클래식한 복구 및 확장 알고리즘(repair and expansion algorithm)에 의해 정제될 때, 더 높은 성공률을 산출하는 후보 해의 분포를 생성할 수 있다는 것이다.

방법론
저자는 다음의 4단계 파이프라인을 따르는 GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search) 프레임워크를 제안한다:

1. 생성 정책 (Generative Policy): 머신러닝 모델(그래프 조건부 정책)이 양자 회로 프로그램(예: QAOA 파라미터)을 생성한다.
2. 양자 샘플링 (Quantum Sampling): 시뮬레이터 또는 QPU(Piast-Q)에서 회로를 실행하여 비트 문자열(후보 해)을 생성한다.
3. 고전적 회복 (Classical Recovery): 문제 특화된 복구 함수가 불가능한 해를 수정하고, 이어서 국소 확장($r$-flip neighborhood)을 수행하여 제한된 탐색 서브스페이스를 생성한다.
4. 제한된 솔버 (Restricted Solver): 이 제한된 서브스페이스 내에서 최적해를 찾는 정밀한 고전적 솔버를 실행한다.

주요 이론적 정식화
본 논문은 회복 베이슨 질량(recovery-basin mass) $p_r$을 사용하여 "양자 이득(quantum benefit)" 문제를 공식화한다:
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
여기서 $A_r(G)$는 복구 및 $r$-flip 확장을 거친 후 전역 최적해를 포함하게 되는 상태들의 집합이다. $B$번의 샷(shots)에 대한 성공 확률은 $P_{success} = 1 - (1 - p_r)^B$이다. 본 연구는 핵심 지표가 샘플링된 서브스페이스의 크기($|S_Q|/2^n$)가 아니라, 샘플러가 회복 가능한 베이슨에 배치하는 확률 질량 $p_r$이라고 상정한다.

실험 프로토콜

• 데이터셋: 브루트 포스(brute-force) 검증 및 CBC를 통해 정답이 인증된 150개의 MWIS 인스턴스.
• 베이스라인: 균등 무작위(uniform random), 그리디(greedy), 시뮬레이티드 어닐링(SA), 타부 서치(tabu search), 멀티 스타트 로컬 서치(multi-start local search), 메트로폴리스(Metropolis), 웜 스타트 QAOA(warm-start QAOA), 오라클 QAOA(oracle QAOA, 50개 구성 중 최적 선택), 그리고 매칭된 학습된 고전적 정책(matched learned classical policy)을 포함한 9개의 샘플러를 비교하였다.
• 제약 조건: 샘플러당 200 샷의 고정된 예산을 가진 사전 등록된(preregistered) 고정 프로토콜.
• 하드웨어: 실험에는 시뮬레이션과 20 큐비트의 Piast-Q 트랩 이온 프로세서에서의 실행이 포함되었다.

주요 결과

1. 고전적 우위 (Classical Dominance): 모든 테스트된 문제 크기($n=16$ ~ $n=28$)에서 타부 서치와 시뮬레이티드 어닐링(SA)이 모든 양자 및 학습된 고전적 샘플러를 크게 앞질렀다. 타부 서치는 $n=16$에서 0.822, $n=18$에서 0.944, $n=20$에서 0.878, $n=24$에서 0.943, $n=28$에서 0.901의 회복 베이슨 질량($p_r$)을 달성했다. SA는 이 크기들에서 0.088에서 0.428 사이의 값을 기록했다.
2. 양자 성능 미달 (Quantum Underperformance): 공정한 사전 등록 프로토콜 하에서 모든 양자 샘플러(warm-start QAOA, oracle QAло, 생성적 정책)는 모든 문제 크기에서 SA와 타부 서치에 패배했다.
3. "오라클" 아티팩트 (The "Oracle" Artifact): QAOA가 SA보다 우수함을 보여주었던 이전의 긍정적인 결과들은 인스턴스별로 구성을 선택하는 "오라클(oracle)" 상한값의 결과물임이 확인되었다. 실제 배포 가능한 방법인 무작위 구성을 사용하여 평가했을 때, oracle QAOA는 $n=28$에서 $p_r = 0.014$를 기록하여 SA의 0.088보다 훨씬 낮았다.
4. 학습된 고전적 모델과의 동등성 (Learned Classical Parity): 140K 개의 파라미터를 가진 학습된 고전적 정책은 oracle QAOA와 유사한 성능($p_r = 0.005–0.101$ vs $0.014–0.113$)을 보였으며, 이는 양자 회로가 이 설정에서 매칭된 고전적 모델에 비해 구조적 이점을 제공하지 못함을 나타낸다.
5. 하드웨어 견고성 (Hardware Robustness): Piast-Q에서의 실험은 QPU와 시뮬레이터 샘플 간에 93.4%의 회복 일관성을 보여주어 하드웨어의 견고함을 확인했으나, 최적화 품질에 있어서는 양자 이득이 없음을 드러냈다.
6. 회복 전이 (Recovery Transition): 본 연구는 고전적 회복이 $n \le 16$에서는 충분하지만, 2-flip 확장을 사용할 경우 $n \ge 20$에서 실패하기 시작하는 "회복 전이"를 매핑했다. 그러나 이 전이 영역에서도 강력한 고전적 베이스라인(SA, Tabu)은 우수한 성능을 유지했다.

의의 및 주장
본 논문은 스스로를 **반증 연구(falsification study)**로 제시한다. 주요 주장은 엄격하고 사전 등록된 평가와 매칭된 학습 베이스라인을 적용했을 때, 얕은 QAOA 유도 제안 분포가 MWIS의 고전적 회복 베이슨을 포착하는 데 있어 매칭된 고전적 제안 모델보다 우수하지 않다는 것이다.

• 양자 이득 없음 (No Quantum Advantage): 저자는 테스트된 영역에서 GQO+QSS 아키텍처에 대한 양자 이득이 없음을 명시적으로 주장한다.
• 이전 주장에 대한 반박: 이전의 긍정적인 결과들을 실제 배포가 불가능한 방법인 "오라클" 구성 선택 효과 때문이라고 규명한다.
• 지표 교정 (Metric Correction): 본 논문은 고정된 샷 예산 하에서 "서브스페이스 분율"($|S_Q|/2^n$)은 동어반복적인 지표이며, **회복 베이슨 질량($p_r$)**이 측정에 있어 과학적으로 정확한 양이라고 주장한다.
• 향후 방향: 저자는 양자 샘플링이 가치를 가지려면, 고전적 회복이 실패하는 영역($n \ge 55$)에서 강력한 고전적 베이스라인(SA 등)보다 지속적으로 더 많은 질량을 회복 베이슨에 배치해야 한다고 제안하며, 현재의 얕은 회로들은 이 과제를 충족하지 못하고 있다고 밝혔다.

결론적으로, 본 연구는 GQO+QSS 아키텍처가 하이브리드 최적화를 위한 유효한 프레임워크이기는 하나, 현재의 얕은 양자 샘플러는 MWIS의 회복 베이슨 포착이라는 특정 작업에서 강력한 고전적 확률론적 탐색 방법(SA 등)에 비해 구조적 이점을 제공하지 못한다는 것을 보여준다.