QAOA 상관관계로 클러스터 탐색 안내하는 양자-고전 하이브리드 최적화 알고리즘

문제 배경: 조합 최적화의 험준한 지형

스케줄링·경로 탐색·포트폴리오 구성 등 실용적 조합 최적화 문제들은 국소 탐색이 지역 최솟값에 쉽게 갇히는 험준한 에너지 지형을 갖는다. 고전적 대표 기법인 시뮬레이티드 어닐링은 한 번에 변수 하나씩 뒤집는 단일-스핀 갱신 방식으로 평탄한 지형에서는 효과적이지만, 상충하는 제약이 많은 '좌절(frustrated)' 문제에서는 대형 장벽을 넘지 못한다.

이를 보완하기 위해 Swendsen-Wang·Wolff·Houdayer 등 클러스터 알고리즘이 개발되었다. 이 방법들은 상관된 변수 집합을 한꺼번에 뒤집어 탐색 공간을 크게 이동할 수 있다. 그러나 일반적인 좌절 최적화 문제에 적용하면 클러스터가 시스템 전체 크기로 폭발하거나 유효한 구조를 포착하지 못해 단일-스핀 갱신보다 나은 성능을 보장하기 어렵다.

QGCA의 핵심 설계

연구진이 제안한 QGCA는 최적화 실행 전 단계에서 변수 쌍 간 상관관계 행렬을 미리 계산해 둔다. 이 상관관계는 문제 결합 상수, 반정확 프로그래밍(SDP), 몬테카를로 샘플링, 또는 QAOA처럼 저에너지 상태를 준비하는 양자 알고리즘 등 다양한 출처에서 얻을 수 있다.

최적화 루프 내에서는 임의 변수 하나를 시작점으로 삼아 상관관계 강도에 비례한 확률로 이웃 변수를 클러스터에 추가한다. 이렇게 형성된 클러스터를 일괄 뒤집은 뒤 시뮬레이티드 어닐링과 동일한 메트로폴리스 판정 규칙으로 수용 여부를 결정하며, 수렴을 위해 온도를 단계적으로 낮춘다. 상관관계 행렬은 실행 초기에 한 번만 계산되므로 추가 양자 자원이 반복적으로 소모되지 않는다는 점이 실용성 측면에서 중요하다.

실험 설정 및 결과

실험에는 CUDA 가속 QAOA 시뮬레이션 프레임워크인 CUAOA를 활용해 고전 컴퓨터에서 QAOA 회로를 시뮬레이션했다. 주 벤치마크로 노드 수 28개의 10-정칙 Max-Cut 그래프를 사용했다.

QAOA 깊이 p=1에서는 QGCA의 성능이 결합 상수만 활용한 기준선과 유사한 수준을 보였다. 깊이가 p=2로 증가하면 QAOA 상관관계가 클러스터 구성을 개선하기 시작해 결합 상수 기준선과 시뮬레이티드 어닐링 모두를 앞질렀으며, 이 추세는 p=10까지 지속되었다.

더 큰 그래프에 대한 추가 실험에서는 3-정칙 그래프에서 QGCA가 시뮬레이티드 어닐링을 명확히 상회했다. 반면 20-정칙 그래프에서는 밀도가 높을수록 좌절도가 높아져 결합 상수만으로 안내할 경우 오히려 잘못된 방향을 제시할 수 있었고, 이 경우 시뮬레이티드 어닐링이 소폭 우위를 보였다.

의미와 한계

QGCA는 양자 정보를 고전 메타휴리스틱에 주입하는 구조로, 양자 이점의 실용적 활용 경로를 보여 준다. 현재 실험 규모(28노드)는 실제 산업용 문제에 비해 작으며, 더 큰 그래프에서 QAOA 상관관계를 확장 적용하는 문제는 여전히 열린 과제다. 또한 밀집 그래프에서 상관관계 품질이 떨어지는 현상은 해결해야 할 기술적 과제로 남는다. 이 연구는 양자-고전 협력 최적화 전략의 가능성을 실험적으로 뒷받침하는 초기 사례로서의 의의를 갖는다.