기술 요약: 밀집 그래프에서의 최대 독립 집합을 위한 최적 근사 시드 기반 양자 중첩

문제 정의

최대 독립 집합(Maximum Independent Set, MIS) 문제는 인접하지 않은 정점들의 가장 큰 부분 집합을 찾는 것으로, 주파수 할당, 단백질 상호작용 분석, VLSI 설계 등 다양한 분야에 응용되는 전형적인 NP-난해(NP-hard) 문제입니다. 고전적인 정확 해법(분기 한정법, 정수 계획법)은 수백 개의 정점을 가진 어려운 인스턴스에서 고전하는 반면, 양자 접근 방식은 NISQ(노이즈가 있는 중간 규모 양자) 시대의 특정 과제에 직면해 있습니다.

밀집 그래프에서는 최적의 독립 집합이 전체 정점의 매우 작은 비율(예: 180개 중 15개)을 차지할 때 결정적인 구조적 문제가 발생합니다. 이 경우, 최적해는 힐베르트 공간 내에서 지수적으로 작은 영역을 점유하게 됩니다. 표준 변분 알고리즘을 균등 중첩(uniform superposition)이나 단일 클래식 시드(classical seed)로 초기화하면, 국소 최적해(예: 크기 14)로 수렴하는 경향이 있으며, 이는 그리디(greedy) 수정 및 극대성 확장(maximality extension)을 통해서도 벗어날 수 없는 상태가 됩니다. 에너지 지형(energy landscape)은 국소적 섭동만으로는 도달할 수 없는, 협응된 다중 큐비트 변화를 요구하는 장벽을 제시합니다.

방법론

저자들은 그래프 전처리, 변분 최적화, 그리고 클래식 후처리를 결합한 계층적 프레임워크를 제안합니다. 이 파이프라인은 현재 하드웨어 성능을 초과하는 크기의 인스턴스를 처리하기 위한 특정 기법들을 포함하여 최대 400개의 노드를 처리하도록 설계되었습니다.

1. 전처리: 재정렬 및 희소화

• 스펙트럼 재정렬(Spectral Reordering): 그래프 라플라시안의 피들러 벡터(Fiedler vector)를 사용하여 정점을 재정렬합니다. 이는 구조적으로 인접한 정점들을 서로 가까운 큐비트 인덱스에 배치함으로써, 결합된 쌍의 인덱스 거리 $|\pi(i) - \pi(j)|$를 최소화합니다. 이를 통해 SWAP 게이트의 필요성을 줄이고 문제의 결합 구조를 하드웨어 연결성과 일치시킵니다.
• 거리 기반 희소화(Distance-Based Sparsification): QAOA의 경우, 대역폭 파라미터 $k$를 기준으로 긴 거리의 에지를 코스트 유니터리(cost unitary)에서 제거하되, 에너지 평가를 위한 전체 해밀토니안은 유지합니다. 이는 회로 깊이를 제어 가능한 수준으로 유지하면서(특히 MPS 시뮬레이션 시), 최적화 도구가 정확한 에너지 피드백을 받을 수 있도록 보장합니다.

2. 변분 알고리즘

• 표준 VQE: 최대 125개 노드의 인스턴스에 대해, 저자들은 EfficientSU2 안사츠(ansatz)를 사용하는 변분 양자 고유값 솔버(VQE)를 사용합니다. 최적화에는 SPSA(Simultaneous Perturbation Stochastic Approximation) 최적화 도구와 CVaR(Conditional Value at Risk) 목적 함수를 사용하여 측정 분포의 꼬리 부분에 집중함으로써 솔루션의 다양성을 높입니다.
• 흥분 보존 안사츠(Excitation-Preserving Ansatz): 180개 이상의 더 크고 밀집된 인스턴스를 위해, 저자들은 $fSim(\theta, \phi)$ 게이트로 구축된 안사츠를 도입합니다. 이 게이트는 상태의 총 해밍 가중치(Hamming weight, 흥분의 수)를 보존합니다. 탐색 범위를 고정된 해밍 가중치 부분 공간으로 제한함으로써, 알고리즘이 타당성(feasibility)을 강제하기 위한 거대한 페널티 항을 사용할 필요 없이, 최적에 가까운 구성들 사이의 미세한 에너지 차이를 구분할 수 있게 합니다.

3. 보조 큐비트 중첩 및 간섭(Ancilla Superposition and Interference)

국소 최적해 장벽(특히 표준 방식이 크기 14에서 멈추는 180개 노드 인스턴스)을 극복하기 위해, 저자들은 새로운 초기화 및 진화 전략을 도입합니다:

• 보조 큐비트 중첩: 단일 시드나 제로 상태에서 시작하는 대신, 알고리즘은 여러 클래식 근사 최적 시드(예: 크기 14인 네 개의 독립 집합)를 보조 큐비트를 인덱스 레지스터로 사용하여 균등 양자 중첩 상태로 준비합니다. 상태는 $|\Psi_0\rangle = \frac{1}{\sqrt{m}} \sum |s(j)\rangle |j\rangle_{anc}$ 입니다.
• 병렬 최적화: 흥분 보존 안사츠는 공유된 변분 파라미터 하에서 모든 시드 브랜치를 동시에 진화시킵니다. 이를 통해 최적화 도구는 모든 시드에 대해 집단적 에너지를 개선할 수 있는 파라미터를 찾을 수 있으며, 단일 시드 최적화로는 도달할 수 없는 솔루션 공간 영역에 접근할 수 있습니다.
• 보조 큐비트 간섭: 제어된 RZ(CRZ) 위상 층과 보조 큐비트에 대한 Hadamard 게이트, 그리고 $|0\rangle^{\otimes a}$ 상태에 대한 사후 선택(post-selection)을 사용하여 시드 브랜치 간의 간섭을 생성합니다. 이는 클래식 확률적 혼합에서 버려지는 교차 항($Re[A_k A^*_{k'}]$)을 유지합니다. 저자들은 이러한 항을 측정하여 간섭이 여러 시드에 의해 지지되는 구성을 증폭시키는지 확인합니다.

4. 클래식 후처리

두 단계의 비트스트링 휴리스틱 파이프라인은 원시 양자 출력을 유효한 독립 집합으로 변환합니다:

• 이력 가이드 억제(History-Guided Suppression): 지수 이동 평균(EMA)을 사용하여 고품질 샘플에서 큐비트가 0 또는 1인 빈도를 추적하고, 과다 선택된 정점을 제거하고 과소 선택된 정점을 추가하기 위한 억제 마스크를 생성합니다.
• 그리디 수정 및 확장: 두 패스의 그리디 알고리즘이 독립성 위반을 수선하고, 최소 차수 선택 규칙을 사용하여 집합을 극대성까지 확장합니다. 이 단계는 일반적으로 원시 양자 출력보다 2~3개의 정점을 추가로 확보합니다.

주요 결과

벤치마크 성능

• 64, 99, 125 노드: 제안된 파이프라인을 적용한 표준 VQE는 이 모든 인스턴스에 대해 인증된 최대 독립 집합(MIS)을 찾아냈습니다. 125개 노드 인스턴스($c125-9$)는 노이즈 없는 시뮬레이션으로부터 파라미터를 전이하여 IBM의 $ibm\_marrakesh$ 하드웨어(156 큐비트)에서 성공적으로 실행되었으며, 크기 34인 4개의 서로 다른 MIS를 복구했습니다.
• 180 노드: 표준 VQE와 비트스트링 휴리스틱은 지속적으로 크기 14에서 멈춥니다. 보조 큐비트 중첩 기술은 이 장벽을 깨고 인증된 크기 15의 MIS를 복구합니다. 절제 연구(Ablation studies)에 따르면, 비트스트링 휴리틱 단독이나 단일 시드에서 시작된 흥분 보존 회로는 크기 14의 국소 최적해를 벗어날 수 없으므로, 여러 시드에 대한 병렬 탐색이 필수적임을 확인했습니다.
• 200 노드: 파이프라인은 시뮬레이션에서 QOBLIB 스위트의 다섯 가지 인스턴스($brock200$및$c-fat200$ 포함)를 최적으로 해결했습니다.
• **400 노드 ($brock400-1$):** 인증된 MIS는 27입니다. 표준 VQE는 크기 23–24에 도달합니다. 흥분 보존 안사츠와 보조 큐비트 중첩을 사용하면$p=3$레이어에서 크기 25(최적의 92.6$\chi_{max} \le m \cdot 2^p$)으로 인해 현재의 클래식 MPS 시뮬레이션 한계를 초과하는 더 깊은 회로($p \ge 4$)가 필요할 것이라고 언급했습니다.

하드웨어 검증

• $ibm\_marrakesh$ 하드웨어에서의 실험은 파이프라인이 노이즈에 강건함을 입증했습니다. 노이즈 없는 시뮬레이션에서 최적화된 파라미터를 하드웨어로 직접 전이했을 때, 64개 노드 인스턴스에서 3개, 99개 노드 인스턴스에서 5개의 서로 다른 MIS를 복구했으며, 샷 예산의 40%만을 사용하고도 노이즈 없는 솔루션 다양성의 약 50%를 유지했습니다.
• 하드웨어에서의 QAOA 구성은 유효한 독립 집합을 전혀 복구하지 못했는데, 이는 얕은 클래식 최적화와 깊은 회로에서의 결맞음(decoherence) 효과가 결합된 결과로 분석되었습니다.

간섭 분석

• 180개 노드 인스술에서 교차 항을 측정한 결과 그 값이 작음을 발견했습니다. 간섭 메커니즘은 시뮬레이션된 환경에서 확률적 혼합(stochastic mixture) 베이스라인과 비교했을 때 솔루션 품질을 크게 변화시키지 않았습니다.
• 이는 재정렬된 큐비트 체인 상에서 구별되는 정점들 사이의 기하학적 거리 때문이라고 저자들은 설명합니다. 시뮬레이션된 깊이에서는 각 시드 브랜치들이 동일한 비트스트링에서 겹치는 경우가 드뭅니다. 저자들은 더 깊은 회로(하드웨어 구현 필요)가 흥분 전달의 "도달 범위"를 넓혀, 측정 가능한 간섭을 가능하게 할 수 있다고 가정합니다.

의의 및 주장

본 논문은 다음과 같이 신중하지만 중요한 주장을 펼칩니다:

1. 국소 최적해 장벽 돌파: 주요 기여는 여러 근사 최적 시드를 양자 중첩에 인코딩하고 이를 집단적으로 최적화함으로써 밀집 그래프 MIS 문제의 국소 최적해 장벽을 깨는 기술입니다. 이는 다른 모든 방법이 실패한 180개 노드 인스턴스를 해결함으로써 입증되었습니다.
2. 확장성: 이 프레 framework는 전체 회로가 직접 최적화되는 일반 그래프 MIS에 대한 가장 큰 게이트 기반 변분 알고리즘 적용 사례를 나타내며, 시뮬레이션에서 200개 노드에 도달하고 400개 노드에서도 부분적인 진전을 보였습니다.
3. 하드웨어 준비성: 파이프라인은 최대 125개 노드 인스턴스에 대해 실제 양자 하드웨어에서 검증되었으며, 하드웨어 인식 재최적화 없이도 현재의 노이즈 수준에 강건함을 확인했습니다.
4. 양자 우위 주장 없음: 저자들은 시뮬레이션된 인스턴스에 대해 양자 계산 우위를 주장하지 않음을 명시했습니다. 이는 낮은 얽힘(얕은 깊이, 적은 시드 수)으로 인해 MPS를 통해 효율적으로 시뮬레이션 가능하기 때문입니다. 이 연구의 가치는 병렬 시드 최적화라는 원칙적인 메커니즘을 보여주고, 하드웨어 실행이 필수적인 영역(더 깊은 회로, 더 큰 본드 차원)을 식별하는 데 있습니다.
5. 미래 메커니즘으로서의 간섭: 현재 시뮬레이션에서는 간섭이 유의미한 요소로 측정되지 않았으나, 저자들은 시드 브랜치들이 겹칠 수 있는 더 깊은 회량의 하드웨어가 제공된다면 간섭이 활용될 수 있는 메커니즘이 될 수 있다고 상정합니다.

결론적으로, 솔루션이 희소한 밀집 그래프의 경우, 스펙트럼 재정렬, 흥분 보존 안사츠, 그리고 다중 시드 중첩의 결합이 유망한 경로를 제공하며, 궁극적인 병목 현상은 알고리즘 설계에서 더 깊고 노이즈에 강한 양자 하드웨어의 가용성으로 이동할 것임을 시사합니다.