Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks

기술 요약: 연속 시간 양자 워크(Continuous-Time Quantum Walks)에 기반한 반복적 최소 정점 커버 알고리즘

문제 정의
본 논문은 전형적인 NP-완전 조합 최적화 과제인 최소 정점 커버(Minimum Vertex Cover, MVC) 및 최대 독립 집합(Maximum Independent Set, MIS) 문제를 다룹다. 그래프 $G=(V, E)$가 주어졌을 때, 목표는 모든 에지를 커버하는 최소 크기의 정점 부분 집합을 찾는 것이다. 저자들은 이를 제약 조건이 있는 최적화 문제로 프레임화하며, 여기서 가용 부분 공간(feasible subspace)은 에지 제약 조건($x_i + x_j \geq 1$ for all $(i,j) \in E$)을 만족하는 비트 문자열로 구성된다. 고전적인 탐욕적 휴리스틱(예: Largest-Degree-First)은 국소적인 그래프 구조에 의존하기 때문에 글로벌 상관관계를 놓치기 쉽다는 한계가 있다. 반면, QAOA나 VQE와 같은 표준 양자 접근 방식은 페널티 항을 사용하여 문제를 무제약 해밀토니안으로 매핑하는 경우가 많은데, 이는 파라미터 튜닝 문제를 야기하고 부적절한(infeasible) 저에너지 상태들이 존재하는 에너지 지형을 생성한다.

방법론
저자들은 페널티 항이나 변분 학습(variational training)을 피하는 제약 조건 보존형 하이브리드 양자-고전 탐욕적 프레임워크를 제안한다. 핵심 방법론은 세 단계로 구성된다:

1. 제약 조건 보존 연산자(Constraint-Preserving Operators):
   가용 부분 공간은 투영된 파울리-X 연산자 $\hat{X}_i = \Pi_{N(i)} X_i$에 의해 정의된다. 여기서 $\Pi_{N(i)}$는 정점 $i$의 모든 이웃이 이미 커버에 포함되어 있는 부분 공간으로 투영하는 연산자이다. 이는 비트 $i$를 뒤집는 것(커버에서 제거하는 것)이 에지 제약 조건을 위반하지 않을 때만 허용되도록 보장한다. 이러한 연산자들은 연속 시간 양자 워크(CTQW) 해밀토니안 $H_{MVC} = \sum_i \hat{X}_i$를 생성한다.

2. 유도된 가용 상태 그래프 및 CTQW:
   $H_{MVC}$의 역학은 유도된 가용 상태 그래프 $G_{VC}(G)$ 상의 CTQW로 해석된다. 이 그래프의 정점들은 유효한 정점 커버들이며, 에지는 단일 비트 플립(feasibility-preserving bit flip)에 의해 차이가 나는 커버들을 연결한다. 이 그래프는 "모든 정점이 커버에 포함된" 상태($\Omega = |1\rangle^{\otimes |V|}$)를 루트로 가지며 연결되어 있다. 따라서 워크는 $\Omega$로부터 모든 가용 커버에 도달할 수 있다. 워크는 루트로부터 해밍 가중치(Hamming weight)가 감소하는 층(layer)을 향해 진폭을 전파한다.

3. 반복적 탐욕적 감소(Iterative Greedy Reduction):
   최소 커버를 직접 측정하려고 시도하는 대신(논문에서는 대규모 시스템에서 확률이 지수적으로 억제됨을 보여준다), 알고리즘은 CTQW 상태를 사용하여 재귀적 고전 감소를 가이드하는 **정점 점수(vertex scores)**를 생성한다:

   • 양자 확률적 탐욕(Quantum Probabilistic Greedy, QPG): CTQW 상태에서의 주변 점유 확률 $P_v(t) = \langle \psi(t) | \Pi_v | \psi(t) \rangle$를 기준으로 정점의 점수를 매긴다.
   • 양자 에너지 탐욕(Quantum Energy Greedy, QEG): 특정 정점 $v$를 커버에 고정했을 때 얻어지는 기대 커버 크기를 기준으로 정점의 점수를 매긴다. 이는 각 후보 정점에 대해 별도의 조건부 워크를 실행하는 것을 포함한다.
   • 감소 규칙(Reduction Rules): 각 단계에서 알고리즘은 이 점수들을 기반으로 정점을 선택한다(커버에 포함하기 위해 가장 높은 점수를 가진 정점을 선택하거나, 커버에서 제외하고 그 이웃을 포함하기 위해 가장 낮은 점수를 가진 정점을 선택함). 이 과정은 그래프가 비어 있거나 고전적으로 해결 가능할 때까지 반복된다.

주요 기여

• 페널티 없는 프레임워크: 본 연구는 투영된 파울리 연산자를 사용하여 제약 조건을 구성적으로 강제함으로써, 페널티 항이나 변분 파라미터 최적화가 필요 없는 방법을 도입했다.
• 유도된 그래프 관점: 제약 조건이 보존되는 역학이 가용 커버들의 연결된 층상 그래프 상의 CTQW와 일치함을 입증하여, 왜 워크가 솔루션 공간을 효과적으로 탐색하는지에 대한 이론적 근거를 제공한다.
• 두 가지 양자 정보 기반 휴리스틱: 논문은 QPG와 QEG 알고리즘을 정의하고 벤치마킹한다. QEG는 각 정점을 고정했을 때의 비용 영향을 평가함으로써 글로벌 구조 정보를 집계한다는 점에서 QPG보다 우수하다고 강조된다.
• 저심도 견고성(Low-Depth Robustness): 프레임워크는 근접 양자 장치(near-term devices)를 위해 설계되었다. 유계 차수(bounded-degree) 그래프의 경우, 각 트로터 층(Trotter layer)의 회로 깊이는 시스템 크기와 무관하다. 저자들은 QEG가 낮은 트로터 깊이($p=4$)에서도 정확한 연속 시간 극한에 가까운 성능을 유지함을 보여준다.

결과
3-정규, 4-정규 및 Erdős–Rényi 랜덤 그래프($n \in \{8, \dots, 20\}$)에 대해 수치적 벤치마크가 수행되었다.

• 성능: 양자 정보 기반 알고리즘(특히 QEG-LDF)은 고전적 탐욕 베이스라인(Greedy LDF, Greedy SDF) 및 FastVC 로컬 서치 휴리스틱에 비해 더 낮은 평균 근사 비율을 달성하고 더 많은 인스턴스를 최적으로 해결한다.
• 트로터화(Trotterization): 미세한 확률 대비(probability contrast)에 민다한 QPG는 낮은 트로터 깊이($p=4$)에서 성능이 크게 저하되는 반면, QEG는 정확한 연속 시간 극한에 가깝게 견고함을 유지한다. 이는 QEG가 회로 깊이가 제한된 하드웨어에 더 적합함을 시사한다.
• 워크 시간: 알고리즘은 정점 점수의 분리(separation)를 극대화하기 위해 특정 워크 시간 $t$를 요구한다(독립적인 앙상블에서 교정됨). 최적의 시간은 일반적으로 웨이브프런트(wavefront)가 최소 커버 층에 처음 도달하는 순간이 아니라, 웨이브프런트가 층들을 통과하고 간섭 패턴이 순위를 확립한 후에 발생한다.

의의 및 주장
본 논문은 양자 구성 요소의 주요 효용이 전체 솔루션을 직접 출력하는 것이 아니라, 가용 상태 공간의 비국소적 구조 정보를 인코딩하는 정점별 점수를 생성하는 데 있다고 주장한다. 이 점수들은 재귀적 고전 감소를 가이드하며, 제약 조건이 보존된 양자 탐색과 고전적 단순화를 효과적으로 결합한다.

저자들은 다음과 같이 그 의의를 겸손하게 규정한다:

• 이 방법은 조합 최적화를 위한 실용적인 페널티 없는 변분 알고리즘의 대안을 제공한다.
• 제약 조건 보존 양자 워크가 순수하게 국소적인 고전 휴리스틱보다 뛰어난 순위(ranking)를 생성할 수 있음을 보여준다.
• 본 연구는 트레이드오프를 식별한다: 에너지 기반 점수(QEG)는 높은 측정 오버헤드($\text{단계당 } O(|V|)$ 평가)를 감수하는 대신 더 큰 견고성을 제공하며, 확률 기반 점수(QPG)는 더 저렴하지만 노이즈에 더 민감하다.
• 결론적으로, 핵심적인 미결 과제는 이러한 워크가 유용한 순위를 생성하는지 여부가 아니라, 경쟁하는 점수들 사이의 통계적 분리가 문제 크기에 따라 어떻게 스케일링되는지이며, 이것이 실질적인 이점의 영역을 결정할 것이다.

저자들은 이 프레임워크가 MVC를 다항 시간 내에 해결하거나 결함 허용(fault-tolerant) 관점에서 정확한 최적화를 위한 양자 가속을 제공한다고 주장하지 않으며, 오히려 근접 하이브리드 알고리즘을 위한 휴리스틱 개선책을 제공한다고 명시하고 있다.