기술 요약: 유틸리티 규모의 최대 독립 집합 문제를 위한 양자 변분 접근법

문제 정의

최대 독립 집합(Maximum Independent Set, MIS) 문제는 인접한 두 정점이 존재하지 않는 무방향 그래프 내의 가장 큰 정점 부분 집합을 찾는 문제입니다. 이는 주파수 할당, 단백질 상호작용 분석, VLSI 설계 등에 응용되는 전형적인 NP-난해(NP-hard) 문제입니다. 고전적인 정확 해법(branch-and-bound, 정수 계획법)은 수백 개의 정점을 가진 어려운 인스턴스에서 어려움을 겪는 반면, 양자 컴퓨팅은 잠재적인 휴리스틱을 제공합니다. 그러나 게이트 기반 변분 알고리즘은 제한된 큐비트 수, 짧은 결맞음 시간, 그리고 기울기가 지수적으로 소실되는 "바렌 플래토(barren plateau)" 현상과 같은 NISQ(Noisy Intermediate-Scale Quantum) 시대의 상당한 과제에 직면해 있습니다.

특정한 구조적 과제는 MIS가 전체 정점의 아주 작은 부분(예: 180개 중 15개)을 차지하는 크고 조밀한 그래프에서 발생합니다. 이러한 경우, 최적해는 힐베르트 공간(Hilbert space) 내에서 지수적으로 작은 영역을 차지합니다. 균일한 중첩(uniform superposition)으로 초기화하는 표준 방식은 MIS에 미미한 진폭만을 할당하며, 이로 인해 변분 회로는 조정된 다중 큐비트 변화 없이는 탈출하기 어려운 하위 최적 에너지 분지(suboptimal energy basins)로 수렴하게 됩니다.

방법론

저자들은 세 가지 벤치마크 인스턴스(64, 99, 180 노드)에 걸쳐 이러한 과제를 해결하기 위해 회로 전처리, 변분 최적화 및 고전적 후처리를 결합한 계층적 프레임워크를 제안합니다.

1. 전처리 및 회로 구성

• 정점 재정렬(Vertex Reordering): SWAP 오버헤드를 최소화하고 얽힘 효율을 개선하기 위해, 저자들은 세 가지 재정렬 전략인 Coupling-weighted BFS, Reverse Cuthill-McKee (RCM), Spectral Reordering(Fiedler vector 사용)을 비교합니다. Spectral reordering은 구조적으로 인접한 정점들을 그룹화하여 강하게 결합된 큐비트 간의 인덱스 거리를 최소화함으로써 조밀한 인스턴스에서 일관되게 가장 우수한 성능을 보여 채택되었습니다.
• 거리 기반 희소화(Distance-Based Sparsification): QAOA 회로에 특화되어 적용된 이 기술은 에너지 계산 시에는 전체 해밀토니안을 평가하면서도, 회로 구성 시에는 장거리 상호작용을 제거합니다(즉, $|i-j| \le k$인 엣지만 유지). 이는 회로 깊이를 크게 줄여 Matrix Product State (MPS) 시뮬레이터에서 실행 가능하게 만듭니다.
• 알고리즘: 본 연구는 EfficientSU2 안사츠(ansatz)를 사용하는 변분 양자 고유값 솔버(VQE)와 양자 근사 최적화 알고리즘(QAOA)을 비교합니다. 최적화 도구로는 COBYLA와 SPSA(Simultaneous Perturbation Stochastic Approximation)를 사용합니다. 측정 분포의 최저 에너지 꼬리 부분에 집중하기 위해 조건부 가치 위험(Conditional Value at Risk, CVaR) 목적 함수를 사용합니다.

2. 고전적 후처리 파이프라인

두 단계의 비트스트링 휴리스틱 파이프라인은 원시 양자 측정값을 유효한 MIS 후보로 변환합니다:

• 이력 가이드 억제(History-Guided Suppression): 지수 이동 평균(EMA)을 사용하여 상위 성능 비트스트링 전반에서 큐비트가 $|0\rangle$ 상태에 있는 빈도를 추적합니다. 이를 통해 과다 선택된 정점(독립성 위반)을 제거하고 과소 선택된 정점을 추가하기 위한 억제 마스크를 생성합니다.
• 탐욕적 교정 및 극대성 확장(Greedy Correction & Maximality Extension): 두 단계의 탐욕적 알고리즘은 먼저 고중량 위반을 제거하여 부적절한 집합을 복구한 다음, 차수가 낮은 순서대로 호환 가능한 정점을 추가하여 집합을 극대성(maximality)까지 확장합니다.

3. 보조 큐비트 지원 중첩 초기화 (180-노드 인스턴스)

180-노드 인스턴스의 경우, 표준 VQE는 크기 14에서 정체됩니다. 이를 극복하기 위해 저자들은 새로운 초기화 기술을 도입합니다:

• 시드 선택(Seed Selection): 고전적 후처리를 통해 다양하고 최적에 가까운 크기-14 독립 집합들을 식별합니다.
• 보조 큐비트 중첩(Ancilla Superposition): 단일 시드나 균일 중첩 대신, 인덱스 레지스터로서 보조 큐비트를 사용하여 이 $m$개의 서로 다른 크기-14 해들의 균일한 양자 중첩을 준비합니다.
• 흥분 보존 안사츠(Excitation-Preserving Ansatz): 총 해밍 가중치(흥분 수)를 보존하는 fSim(fermionic simulation) 게이트로 구성된 안사츠 하에서 상태가 진화합니다. 이는 탐색 범위를 크기-14 구성으로 제한하여 패널티 항의 필요성을 없애고, 미세한 최적화를 위한 에너지 지형을 날카롭게 만듭나다.
• 양자 병렬 탐색: 변분 파라미터는 모든 시드 브랜치 전반에 걸쳐 집합적으로 최적화됩니다. 결과 분포는 고전적 휴리스틱에 의해 처리되며, 이 과정에서 크기-14 집합을 크기-15 MIS로 확장할 수 있습니다.

주요 결과

벤치마크 인스턴스 (64, 99, 및 180 노드)

• 64-노드 인스턴스: SPSA와 CVaR를 사용한 VQE는 반복 실행을 통해 9개의 모든 인증된 MIS(크기 10)를 성공적으로 복구합니다. QAOA는 더 적은 수의 집합(실행당 0~5개)을 복구하며, 모든 복구된 집합을 극대성으로 유도하는 전략 2를 사용할 때 크기 10에 도달하는 데 실패하여 솔루션 다양성의 중요성을 강조합니다.
• 99-노드 인스턴스: VQE는 실행당 최대 10개의 고유한 MIS(크기 7)를 복구하며, 56개의 인증된 솔루션 중 의미 있는 비율을 샘플링합니다. QAOA는 MPS 시뮬레이터의 희소화 제한으로 인해 추진되지 않았습니다.
• 180-노드 인스턴스: 표준 VQE(단계 1)는 크기 14에서 수렴하지만 크기 15에는 도달하지 못합니다. 보조 큐비트 지원 단계 3(흥분 보존 VQE)는 크기-15 MIS를 성공적으로 발견합니다. 절제 연구(ablation studies)는 단일 시드에 적용된 고전적 휴리스틱이나 단일 시드에서 시작된 흥분 보존 회로가 크기-15 MIS를 찾는 데 실패함을 확인했습니다. 오직 다중 시드 양자 중첩만이 국소 최적점 장벽을 깨뜨릴 수 있었습니다.

하드웨어 검증 (IBM Quantum ibm_marrakesh)

• VQE: 노이즈 없는 시뮬레이션에서 직접 전송된 파라미터를 사용하여, VQE는 40%의 샷 예산으로 노이즈 없는 MIS 다양성의 약 50%를 복구합니다. 64-노드 인스턴스의 경우 3개의 고유한 MIS(크기 10)를 찾았고, 99-노드 인스턴스의 경우 5개의 고유한 MIS(크기 7)를 찾았습니다.
• QAOA: 동일한 파라미터 전송 프로토콜 하에서 QAOA는 하드웨어에서 유효한 독립 집합을 전혀 복구하지 못했습니다. 저자들은 이를 제한된 회로 대역폭(깊은 SWAP 체인 필요), 얕은 클래식 최적화, 그리고 하드웨어 노이즈의 결합 효과 때문이라고 설명합니다.

의의 및 주장

본 논문은 다음과 같은 기여와 의의를 주장합니다:

1. 유틸리티 규모 시뮬레이션: 저자들의 지식 범위 내에서, 180-큐비트 MPS 시뮬레이션은 게이트 기반 변분 알고리즘이 MIS 문제를 최적으로 해결한 가장 큰 규모의 사례입니다.
2. 방법론적 돌파구: 주요 기여는 보조 큐비트 중첩 기술입니다. 이는 고전적 휴리스틱과 표준 변분 접근법을 모두 가두는 국소 최적점을 깨뜨리는 원칙적인 프레임워크를 제공합니다. 여러 최적에 가까운 고전적 시드 위에서 균일한 양자 중첩을 준비하고 흥분 보존 안사츠 하에서 진화시킴으로써, 이 방법은 "하이브리드 양자-고전 병렬 탐색"을 수행합니다. 이를 통해 단일 시드 방식으로는 접근할 수 없는 솔루션(크기 15)을 발견할 수 있게 합니다.
3. 노이즈에 대한 견고성: 하드웨어 검증은 비트스트링 휴리틱 파이프라인이 하드웨어 인지 재최적화 없이도 상당한 솔루션 다양성을 복구할 만큼 실제 노이즈 조건에 견고함을 입증합니다.
4. 양자 우위에 대한 신중한 주장: 저자들은 이 특정 인스턴스들에 대해 양자 계산 우위를 주장하지 않음을 명시적으로 밝힙니다. 연구된 회로들은 낮은 얽힘 구조 덕분에 MPS(결합 차원 $\chi_{max} = 2$)를 통해 고전적으로 효율적으로 시뮬레이션 가능합니다. 본 연구의 의의는 방법론이 작동함을 입증하고, 더 깊은 안사츠와 더 큰 시드 집단이 진정한 양자 우위를 창출할 수 있는 미래의 하드웨어 구현을 위한 토대를 마련했다는 데 있습니다.

본 연구는 180-노드 사례에서의 MIS 발견이 고전적 후처리 때문만이 아니라, 여러 최적에 가까운 초기화에 대한 양자 병렬 탐색의 결과임을 확립합니다. 이 프레임워크는 Ising 정식화가 가능한 조합 최적화 문제에 대한 확장 가능한 접근 방식으로 제시됩니다.