An End-to-End Hybrid Quantum--Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study

기술 요약: 이산 마르코프 랜덤 필드를 위한 엔드 투 엔드 하이브리드 양자-고전 샘플링 워크플로우

문제 정의
이산 마르코프 랜덤 필드(MRF)로부터 샘플링하는 것은 확률적 추론, 컴퓨터 비전, 통계 물리학에서 핵심적인 과제이다. 핵심적인 어려움은 $2^n$개의 구성에 대해 합산되는 분할 함수 $Z(\theta)$에 의해 정규화되어야 하는 결합 분포 $P_\theta(x)$로부터 샘플을 추출하는 데 있다. 전통적인 마르코코프 체인 몬테카를로(MCMC) 방법이 표준이지만, 루프가 있는 그래프(loopy graphs)에서는 느린 혼합(mixing)과 높은 자기상관(autocorrelation) 문제를 겪는 경우가 많다. 반면, 변분 추론(variational inference)과 벨리프 프로파게이션(belief propagation)은 정확도 또는 수렴의 한계에 직면한다. 본 논문은 전체 분포를 고전적으로 사전 계산할 수 있는($O(2^n)$) 영역에서, 진폭 인코딩 양자 샘플링(amplitude-encoded quantum sampling)이 고전적 방법론에 비해 실질적인 이점을 제공하는지 조사한다. 이 영역은 지수적 양자 가속을 배제하지만, 샘플링 효율성과 독립성에 대한 엄격한 비교를 가능하게 한다.

방법론
본 연구는 서로 다른 문제 규모($n$)를 다루기 위해 이중 아키텍처 접근 방식을 채택한다:

1. 진폭 인코딩 (작은 $n$): $n \in \{8, 10, 12\}$에 대해, 저자들은 해밀토니안 $H_\theta$의 대각 성분을 $O(2^n)$ 시간 내에 고전적으로 계산하는 파이프라인을 구축한다. 타겟 확률은 정규화되며, 진폭 $\alpha_x = \sqrt{P_\theta(x)}$는 Qiskit의 StatePreparation 프리미티브를 사용하여 준비된다. 이는 양자 상태 $|\psi\rangle = \sum_x \sqrt{P_\theta(x)}|x\rangle$를 생성한다. 계산 기저(computational basis)에서의 측정은 독립 동일 분포(i.i.d.) 샘플을 산출한다. 이 방식은 전체 양자 회로 생성 모델링(QCGM)의 잠재적인 지수적 가속을 희생하는 대신, 샘플링 과정에 대한 깨끗하고 검증 가능한 감사를 가능하게 한다.
2. 변분 양자 회로 (VQC) (더 큰 $n$): 전체 열거가 불가능한 더 큰 $n$의 경우, 저자들은 하드웨어 효율적 안사츠(ansätze)를 훈련시킨다. 이 회로들은 단일 큐비트 $R_Y$ 회전과 인터리빙된 인탱글링 CNOT 게이트로 구성된 $d$개의 레이어로 구성된다. 세 가지 인탱글링 전략이 테스트되었다: 선형(인접 큐비트), 클리크 인식(clique-aware, MRF 그래프 토폴로지에 부합), 그리고 전체(all-to-all). 회로는 유도된 분포와 타겟 $P_\theta$ 사이의 쿨백-라이블러(KL) 발산을 최소화하도록 훈련된다.
3. 고전적 베이스라인: 양자 방법론은 네 가지 고전적 샘플러와 벤치마킹된다:
   • 싱글 사이트 깁스(Single-site Gibbs, random-scan).
   • 블록 깁스(Block Gibbs, 최대 클리크 업데이트).
   • 튜닝된 블록 깁스(Tuned-Block Gibbs, 적응형 블록 멤버십).
   • 8개의 레플리카를 사용하는 병렬 템퍼링(Parallel Tempering, PT).
   • 정확한 역-CDF(Exact Inverse-CDF): 사전 계산된 분포를 사용하여 i.i.d. 샘플을 추출하는 고전적 베이스라인으로, 진폭 인코더의 전처리 비용이 상쇄된 후의 "애플 투 애플(apples-to-apples)" 비교 대상이 된다.

주요 기여
본 논문은 양자 가속을 주장하지 않는다. 대신, 그 기여는 다음과 같은 엄격한 벤치마킹 및 부정적 결과 연구로 특징지어진다:

1. ESS 격차 규명: 60개의 인스턴스(5개의 그래프 패밀리)에 걸쳐 진폭 인코딩 i.i.d. 샘플링과 4가지 고전적 MCMC 베이스라인 간의 유효 샘플 크기(Effective Sample Size, ESS) 격차를 정량화하였다.
2. 벽시계 시간 상쇄(Wall-Clock Amortization): 진폭 인코더에 필요한 $O(2^n)$ 고전적 전처리 비용을 명시적으로 포함하여서, 정확한 역-CDF 샘플러와 비교함으로써 공정한 벽시계 시간 비교를 수행하였다.
3. 고전적 스케일링 천장: $n=40$까지의 행렬 곱 상태(Matrix Product States, MPS)에 대한 다중 시도 스케일링 연구를 통해, 향후 변분적 접근법을 위한 구체적인 고전적 충실도(fidelity) 천장을 설정하였다.
4. 재현성: 커밋된 JSON 데이터 파일로부터 모든 표와 그림을 재생성할 수 있는 오픈 소스 코드 및 실행 가능한 아티팩트를 공개하였다.

결과

• ESS 비율: 60개 인스턴스 전반에 걸쳐, 양자 ESS 대 고전적 ESS의 비율은 명확한 계층 구조를 보였다. 양자 샘플러는 싱글 사이트 깁스보다 평균 16.35배, 블록 깁스보다 7.29배, 튜닝된 블록 깁스보다 1.82배, 그리고 병렬 템퍼링보다 1.79배 우수한 성능을 보였다. 이는 양자 샘플링이 구조적 독립성($\tau \approx 1$)을 유지하지만, 현대적인 고전적 샘플러(특히 병렬 템퍼링)가 이 격차를 상당히 좁힌다는 것을 나타낸다.
• 벽시계 성능: $O(2^n)$ 전처리 비용을 상쇄했을 때, 정확한 역-CDF 샘플러는 평균 17,683,598 ESS/s를 달성한 반면, 양자 샘플러는 487,706 ESS/s를 기록했다. 이는 평균 속도에서 36배, 평균 인스턴스당 비율에서 153배의 우위를 나타내며, 이 영역에서 양자 워크플로우의 벽시계 시간적 이점이 없음을 확인시켜 준다.
• VQC 대 MPS (부정적 결과): 얕은 하드웨어 효율적 VQC(깊이 3)는 테스트된 모든 크기($n=8, 10, 12$)에서 매칭된 예산의 MPS에 비해 현저히 낮은 성능을 보였다. VQC의 충실도는 0.306, 0.210, 0.165였던 반면, MPS는 0.990, 0.958, 0.878이었다.
• VQC 대 평균장(Mean-Field): $n=8$ 및 $n=10$에서, 평균장 근사가 VQC보다 더 높은 글로벌 분포 충실도를 달取得하였으나, VQC는 싱글톤 마진 에러(singleton marginal errors) 측면에서는 고전적 방법론보다 우수했다.
• MPS 스케일링: $n=40$에서 결합 차원 $\chi=32$인 MPS는 0.721 ± 0.059의 충실도를 달성하여, 향후 양자 알고리즘을 위한 벤치마크를 설정하였다.
• 인탱글링 전략: 테스트된 규모에서 클리크 인식 인탱글링은 선형 인탱글링에 비해 측정 가능한 충실도 이점을 제공하지 않았다.

의의 및 주장
본 논문은 명시적으로 양자 우위를 주장하지 않는다. 그 의의는 다음과 같다:

1. "양자 우위" 서사의 명확화: 양자 샘플링의 이점은 고전적 베이스라인의 선택에 매우 민감하다는 것을 입증한다. 양자 샘플링은 구조적 독립성을 제공하지만, 최적화된 고전적 MCMC(예: 병렬 템퍼링)는 ESS 격차를 거의 제거하며, 고전적 정확한 샘플링(역-CDF)은 전처리를 고려할 때 벽시계 시간에서 압도적이다.
2. 유효 영역의 정의: 진폭 인코더는 i.i.d. 양자 샘플이나 다운스트림의 코히어런트 상태 준비(예: 진폭 추정)가 엄격히 요구되거나, 전체 분포를 열거할 수 없지만 고전적 베이스라인을 사용할 수 없는 경우에만 방어 가능한 도구이다.
3. 얕은 VQC에 대한 부정적 결과: 본 연구는 얕은 하드웨어 효율적 안사츠가 MPS와 같은 텐서 네트워크 방법론에 비해 피크가 있는(peaked) MRF 분포의 글로벌 구조를 포착하기에 불충분하다는 증거를 제공한다.
4. 벤치마킹: 향후 양자 알고리즘이 유용성을 입증하기 위해 넘어서야 할 구체적인 수치적 천장(예: $n=40$에서의 MPS)을 포함한 재현 가능한 프레임워크를 구축하였다.

저자들은 향히 양자 우위로 가는 가장 타당한 경로가 완전한 QCGM 해밀토니안 시뮬레이션, 더 깊거나 문제 인식적인 변분 안사츠, 또는 대규모 노이즈 하드웨어 벤치마킹에 있다고 결론지으며, 이들을 모두 향후 연구 과제로 식별하였다.