기술 요약: 최대 독립 집합 문제를 위한 확장 가능한 양자 강화 그리디 알고리즘

문제 정의

본 논문은 그래프 이론의 근본적인 NP-난해(NP-hard) 조합 최적화 과제인 최대 독립 집합(Maximum Independent Set, MIS) 문제를 다룹다. 그래프 $G=(V, E)$가 주어졌을 때, 목표는 인접한 두 정점이 존재하지 않는 가장 큰 정점 부분 집합 $I \subseteq V$를 찾는 것이다. 고전적 그리디(greedy) 알고리즘은 선형 시간의 확장성을 제공하지만, 종종 복잡한 전역 구조를 포착하는 데 실패하여 하위 최적(suboptimal) 솔루션을 도출한다. 반면, **양자 근사 최적화 알고리즘(QAOA)**과 같은 단독 양자 알고리즘은 노이즈가 있는 중간 규모 양자(NISQ) 시대에 상당한 어려움에 직면한다. 즉, 최적해에 도달하기 위해 깊은 회로가 필요하지만 현재의 하드웨어는 노이로 인해 이를 지원할 수 없으며, 변분 파라미터 최적화 과정에서 "배런 플래토(barren plateau)" 문제로 고통받는다. 또한, 이론적 결과에 따르면 상수 깊이의 QAOA는 국소성 제약으로 인해 MIS를 근사 최적해까지 해결할 수 없음을 시사한다.

방법론

저자들은 QAOA를 클래식 그리디 프레임워크 내의 서브루틴으로 통합하는 하이브리드 양자-클래식 알고리즘을 제안한다. 핵심 방법론은 다음 구성 요소들로 이루어진다:

1. 고정 각도 QAOA (Fixed-Angle QAOA): 인스턴스별 변분 파라미터 최적화(계산 비용이 높고 배런 플래토에 취약함)를 수행하는 대신, 알고-리즘은 사전 계산된 QAOA 각도를 활용한다. 이 각도들은 대규모 $d$-정규 그래프의 국소 이웃을 정확하게 근사하는 베테 래티스(Bethe lattices) 상의 깊이-$p$ QAOA 회로로부터 유도된다.
2. 양자 강화 그리디 선택 (Quantum-Enhanced Greedy Selection):
   • 알고리즘은 독립 집합을 반복적으로 구축한다.
   • 각 단계에서, 단순히 차수(degree)를 기준으로 노드를 선택하는 대신(최소 차수 그리디 방식), QAOA 상태 $|\gamma^*, \beta^*\rangle$로부터 유도된 국소 기대값 $\langle Z_i \rangle_p$를 최대화하는 노드 $i$를 선택한다.
   • 이 기대값은 후보 노드의 라이트 콘(light-cone) 서브그래프(반경 $p$ 이내의 이웃)에 제한된 얕은 QAOA 회로를 실행함으로써 추정된다.
   • 선택된 노드는 독립 집합에 추가되며, 해당 노드와 그 이웃들은 그래프에서 제거된다.
3. 효율성 메커니즘:
   • 국소 재계산 (Local Recomputation): QAOA의 국소성 덕분에, 노드를 제거하는 것은 오직 거리 $p+1$ 이내의 노드들의 기대값에만 영향을 미친다. 알고리즘은 영향을 받는 이 값들만을 재계산한다.
   • 캐싱 (Caching): 중복 계산을 피하기 위해 동형(isomorphic) 라이트 콘 서브그래프에 대한 기대값을 캐싱한다.
   • 복잡도: 고정된 깊이 $p$에 대해, 국소 기대값을 계산하는 비용은 그래프 크기 $N$에 관계없이 일정하다. 따라서 전체 런타임은 $O(N)$으로 스케일링되며, 이는 순수 클래식 그리디 알고리즘의 복잡도와 일치한다.

주요 기여

• 변분 최적화의 제거: 본 연구는 트리 모델을 기반으로 QAOA 파라미터를 고정함으로써 비용이 많이 드는 클래식 최적화 루프를 제거하고, 이를 통해 알고리즘의 확장성을 확보하는 "플러그 앤 플레이(plug-and-play)" 접근 방식을 입증한다.
• 확장 가능한 하이브리드 아키텍처: 저자들은 얕은 양자 회로(NISQ 장치에 적합)를 유지하면서 양자 상관관계를 활용해 클래식 결정을 가이드하는 방법을 제시하며, 선형 시간 복잡도를 달야한다.
• 실험적 검증: 알고리즘은 **20-큐비트 IQM 초전도 양자 프로세서(Garnet)**에서 구현되었다. 본 연구는 수천 개의 노드를 가진 그래프에서 독립 집합을 성공적으로 찾아냄으로써 실제 하드웨어에서의 접근 방식을 검증했다.
• 텐서 네트워크 벤치마킹: 현재의 하드웨어 한계를 넘어 성능을 평가하기 위해, 저자들은 깊이 $p=4$ 및 그래프 크기 $N=5000$까지의 정확한 기대값을 계산하기 위해 텐서 네트워크 시뮬레이션(QUIMB 패키지 사용)을 채택했다.

결과

• 클래식 베이스라인과의 성능 비교:
  • 무작위 3-정규 그래프에서 양자 강화 그리디 알고리즘은 표준 최소 차수 그리디 베이스라인을 유의미하게 능가한다.
  • 깊이 $p=4$에서, 하이브리드 방법은 $N \approx 5000$ 크기의 그래프에 대해 최첨단(SOTA) 선형 시간 우선순위 탐색 알고리즘(Marino et al.)보다 통계적으로 유의미한 개선을 달성한다.
  • 낮은 깊이($p=2, 3$)에서도 양자 강화 방식은 순수 클래식 접근법보다 더 나은 독립도 비율(independence ratios)을 보여준다.
• 하드웨어 구현:
  • $p=2$ 및 $p=3$에서 IQM Garnet 장치를 이용한 실험은 노이즈가 있는 하드웨어에서 추출된 기대값이 그리디 선택을 효과적으로 가이드할 수 있음을 확인했다.
  • 알고리즘은 노이즈에 대한 강건성을 입증했다. 노이즘이 양자 프로세서가 제공하는 "조언"의 정밀도를 저하시키기는 하지만, 알고리즘이 유효하지 않은 독립 집합을 생성하게 만들지는 않는다.
• 스케일링 및 한계:
  • 텐서 네트워크 시뮬레이션 결과, 기대값을 계산하는 클래식 비용은 깊이 $p$에 따라 지수적으로 증가($p$에 대해 $O(\exp(O(p)))$)하는 반면, 양자 하드웨어 비용은 $p$에 대해 다항식적으로 스케일링됨을 밝혔다(전결합성 가정 시 폴리노미얼, 평면형 하드웨어 시 $O(\exp(p)^{1/2})$). 이는 양자 프로세서가 이러한 국소적 양들을 효율적으로 평가하는 데 필수적인 영역이 존재함을 시사한다.

의의 및 주장

본 논문은 이 작업이 **NISQ 시대의 양자 유용성(quantum utility)**을 위한 실질적인 경로를 보여준다고 주장한다. QAOA를 단독 솔버가 아니라 클래식 휴리스틱을 강화하는 서브루틴으로 재정의함으로써, 저자들은 얕은 회로의 한계와 파라미터 최적화의 어려움을 극복했다.

주요 의의에 대한 핵심 주장은 다음과 같다:

1. 적은 양자 자원으로 얻는 상당한 이득: 양자 자원(얕은 회로, 고정 각도)을 클래식 전략에 통합함으로써, 두 방법 각각을 단독으로 사용할 때보다 우수한 결과를 얻을 수 있다.
2. 확장성: 선형 시간 스케일링은 이 접근 방식이 현재 및 가까운 미래의 하드웨어에서 수천 개의 노드를 가진 대규모 문제에 적용 가능하게 만든다.
3. 강건성: 하이브리드 특성은 본질적인 강건성을 제공한다. 노이즈는 휴리스틱 가이드의 품질에는 영향을 미치지만, 솔루션의 유효성(독립 집합 제약 조건)은 보존한다.
4. 일반화 가능성: 저자들은 이 비변분(non-variational), 양자 강화 패러다임이 국소 구조가 지배적인 다른 희소 그래프 조합 최적화 문제(예: MaxCut, Minimum Vertex Cover)로 자연스럽게 확장될 수 있다고 제안한다.

저자들은 단독 QAOA가 낮은 깊이에서 단순 그리디 휴리스틱을 능가하기 어렵지만, 양자 강화 그리디 알고리즘은 양자 상관관계를 성공적으로 활용하여 결합을 깨고 솔루션 공간을 더 효과적으로 탐색함으로써, 확장 가능한 하이브리드 최적화의 강력한 후보임을 결론지었다.