Methods for non-variational heuristic quantum optimisation

기술 요약: 비변분적 휴리스틱 양자 최적화 방법론

문제 정의
최적화는 과학 및 산업 응용 분야의 핵심이지만, 고전적인 정확한 방법들은 조합 최문제에 대해 지수적인 시간을 요구하는 경우가 많아 휴리스틱 솔버의 사용이 필수적입니다. 변분 양자 알고리즘(VQA)과 양자 어닐링(QA)이 현재 노이즈에 강한 양자 최적화 연구를 주도하고 있으나, 이들은 수렴성, 회로 깊이 및 하드웨어 요구 사항 측면에서 어려움에 직면해 있습니다. 또한, 기존의 많은 양자 접근 방식은 아직 가용하지 않은 결함 허용(fault-tolerant) 기술이나 특정 하드웨어 아키텍처에 의존합니다. 따라서 근사적인 양자 장치(NISQ)를 활용하여 하이브리드 양자-고전 프레임워크를 통해 문제를 해결할 수 있는 대안적인 비변분적 양자 휴리스틱이 필요합니다. 특히, 고전적 마르코프 연쇄 몬테카를로(MCMC) 방법이 에너지 장벽으로 인해 느린 열평형화(thermalisation) 문제를 겪는 "유리질(glassy)" 특성의 비용 함수(예: Sherrington-Kirkpatrick 모델)를 다루는 데 초점을 맞춥니다.

방법론
저자들은 고전적 MCMC 기반 알고리즘의 국소 제안(local proposal) 단계를 실시간 진화(real-time evolution)에 기반한 양자 서브루틴으로 대체하는 새로운 클래스의 양자 최적화 휴리스틱을 제안합니다. 이 접근 방식은 변분 프레임워크를 완전히 배제합니다.

1. 핵심 메커니즘 (QeMCMC): 기초는 양자 강화 마르코프 연쇄 몬테카를로(QeMCMC)입니다. 고전적인 국소 제안(예: 단일 스핀 반전) 대신, 이 알고리즘은 계산 기저 상태 $|s\rangle$에서 양자 컴퓨터를 초기화하고, 유니터리 진화 $U = e^{-iHt}$를 적용한 후 결과를 측정하여 새로운 구성 $s'$을 얻습니다.

   • 해밀토니안 $H$는 구동 항(단열 양자 컴퓨팅과 관련되어 에너지 준위 간의 확산을 유도함)과 문제 특유의 이징(Ising) 해밀토니안의 합으로 구성됩니다.
   • 하이퍼파라미터 $\gamma$(혼합)와 $t$(진화 시간)는 특정 범위에서 샘플링됩니다.
   • 이 설계는 작은 에너지 차이($\Delta f$)와 큰 해밍 거리($\Delta H$)를 갖는 제안을 생성함으로써, 고전적 국소 제안보다 더 효과적으로 지역 최솟값(local minima)을 탈출할 수 있는 비국소적 이동을 용이하게 하는 것을 목표로 합니다.

2. 제안된 알고리즘:

   • 양자 강화 시뮬레이티드 어닐링 (QeSA): 로그 냉각 스케줄을 따르면서 고전적 국소 제안을 양자 제안 메커니즘으로 대체하여 고전적 시뮬레이티드 어닐링(SA)을 확장합니다.
   • 양자 강화 병렬 템퍼링 (QePT): 여러 개의 마르코프 연쇄를 서로 다른 온도에서 병렬로 실행하고 주기적인 구성 스왑을 수행하는 병렬 템퍼링(PT)을 확장합니다. QePT에서 저자들은 특정 체인(특히 열평형화가 가장 어려운 저온 체인들)만 양자 방식으로 강화하고, 고온 체인은 고전적 방식을 유지하는 하이브리드 접근 방식을 제안합니다.

주요 기여

• 알고리즘 제안: 비변분적, 하이브리드 양자-고전 최적화 휴리스틱으로서 QeSA 및 QePT를 도입했습니다.
• 하이브리드 아키텍처: 전체를 양자로 강화하는 것이 반드시 필요하지 않으며, 병렬 템퍼링 설정에서 "병목"이 되는 저온 체인만을 강화함으로써 상당한 이점을 얻을 수 있음을 입증했습니다. 이는 이 접근 방식이 현재의 HPC-QC(고성능 컴퓨팅-양자 컴퓨팅) 통합에 더 실용적임을 보여줍니다.
• 원리 증명 수치 해석: 저자들은 알고리즘의 수렴 특성을 고전적 벤치마크와 비교 검증하기 위해 Sherrington-Kirklerann (SK) 스핀 글래스 인스턴스($n \leq 10$)에 대한 시뮬레이션 수치 결과를 제공합니다.

결과

• 수렴 동작: 시뮬레이션에서 고전적 SA는 빈번하게 지역 최솟값에 갇히며 성공 확률에서 높은 분산을 보였습니다. 반면, QeSA는 전역 최솟값에 도달하는 데 있어 더 일관된 능력을 보여주었으며, 성공 확률이 단계 수에 따라 꾸준히 증가했습니다.
• 계산 노력: 저자들은 "계산 노력"($N_p$)을 체인 길이와 특정 확률로 바닥 상태를 찾기 위해 필요한 반복 횟수의 곱으로 정의합니다.
  • QeSA의 경우, 체인 길이를 최적화함으로써 양자 접근 방식이 테스트된 문제 크기에 대해 고전적 SA보다 현저히 낮은 총 노력으로 목표 성공 확률을 달성할 수 있음을 보여주었습니다.
  • QePT의 경우, 결과는 가장 낮은 온도 체인들(예: 4개의 복제본 중 2개)만 양자로 강화하는 것이 완전히 고전적인 PT보다 실질적인 개선을 제공하며, 완전히 양자로 강화된 시스템의 성능에 근접한다는 것을 나타냅니다. 이는 유리한 자원 대비 성능 트레이드오프를 시사합니다.
• 스케일링: 저자들은 평균적인 스핀 글래스 인스턴스에 대해 잠재적인 스케일링 이점(최대 4차항까지 가설)을 관찰했으나, 고전적 시뮬레이션의 한계와 실제 하드웨어 테스트의 부재로 인해 결정적인 양자 가속도를 정량화하지는 않았음을 명시했습니다.

의의 및 주장
본 논문은 이러한 방법론들이 근사적인 양자 장치를 사용하여 대규모 최적화 문제를 해결하기 위한 확장 가능하고 경쟁력 있는 경로라고 위치시킵니다.

• 강건성: 알고리즘은 본질적인 노이즈 강건성을 가진다고 주장됩니다. 완전한 디폴라이징 노이즈(fully depolarising noise)의 극한에서 양자 제안은 균등 샘플링(uniform sampling)으로 회귀하며, 이는 변분 방법론이 수렴에 실패할 수 있는 것과 달리 여전히 유효한 MCMC 단계로 남습니다.
• 병렬성: 이 접근 방식은 양자 및 고전 자원에 걸친 병렬 실행을 지원하며, 복제본 교환을 위해 오직 고전적 통신만을 필요로 하므로 현재의 HPC 아키텍처와 잘 부합합니다.
• 신중한 주장: 저자들은 이 방법들이 최악의 시나리오에 대한 분석적 보장 없이 휴리스틱 방법임을 명확히 하고 있습니다. 그들은 양자 제안의 성능이 분석적으로 완전히 이해되지 않았으며, 관찰된 이점은 현재 시뮬레이션된 하드웨어 상의 원리 증명 수치 해석에 기반하고 있다는 점을 인정합니다. 저자들은 이 연구가 결정적인 해결책이라기보다는 미래의 연구와 실험적 검증을 위한 동기 부여 역할을 한다고 밝히며, 이 방법들의 진정한 잠재력과 스케일링은 더 긴밀한 양자-고전 통합을 갖춘 실제 양자 하드웨어에서 테스트될 때만 검증될 수 있다고 명시했습니다.