Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

기술 요약: 제약 최적화를 위한 기하학 기반 다항 시간 양자 근사 스킴

문제 정의
제약 조건이 있는 조합 최적화(Constrained combinatorial optimization)는 엄격한 제약 조건(예: 할당, 매칭, 라우팅)을 준수하면서 최적의 구성을 찾는 것을 포함합니다. 특정 가측 하위 클래스에 대해서는 고전적 알고리즘이 존재하지만, 많은 이러한 문제들은 NP-난해(NP-hard)입니다. 양자 접근 방식, 특히 양자 근사 최적화 알고리즘(QAOA)은 근미래 장치(near-term devices)에서 다음과 같은 문제에 직면합니다:

1. 실행 가능성(Feasibility): 표준 QAOA는 종종 엄격한 제약 조건으로 정의된 실행 가능한 부분 공간 외부의 샘플을 추출합니다.
2. 노이즈(Noise): 장치 노이즈는 제약 조건 위반을 유발하여 샘플의 품질을 저하시킵니다.
3. 보장(Guarantees): 기존 방법들은 현실적인 노이즈 조건 하에서 엄격한 엔드 투 엔드 성능 보장(높은 확률로 최적해를 찾는 다항 시간 실행)이 부족한 경우가 많습니다.

본 논문은 다음 질문을 다룹니다: 노이즈가 있는 양자 샘플러가 언제 성능 보장을 갖는 엔드 투 엔드 다항 시간 알고리즘을 가능하게 하는가?

방법론
저자들은 양자 샘플링과 결정론적 고전 사후 처리(deterministic classical post-processing)를 통합하는 완전한 파이프라인인 Noisy Polytime Hybrid Quantum-Classical (NP-HQ) 알고리즘을 제안합니다. 이 방법론은 세 가지 핵심 축에 기반합니다:

1. OFM 커널 및 CE-QAOA:
   본 접근 방식은 TSP(Travelling Salesman Problem) 및 QAP(Quadratic Assignment Problem)와 같은 문제에 대한 특정 인코딩을 정의하는 Onah–Firt–Michielsen (OFM) 커널을 활용합니다.

   • 인코딩: 각 논리적 블록에 정확히 하나의 들뜸(excitation)이 있는 원-핫 인코딩(one-hot encoding)을 사용합니다.
   • 역학(Dynamics): 원-핫 부분 공간을 보존하는 블록 국소 XY 믹서(block-local XY mixer)를 사용하는 **Constraint-Enhanced QAOA (CE-QAOA)**를 채택합니다.
   • 보장: 선행 연구 [1]를 바탕으로, 이상적인 CE-QAOA 샘플러는 특정 기하학적 조건(위상 분리)이 충족되는 경우 최적해 집합에 역다항식 확률 질량($p_0 = \Omega(n^{-k})$)을 할당함을 보여줍니다.

2. 결정론적 복구 및 스코어링(Deterministic Repair and Scoring):
   노이즈와 실행 불가능한 샘플을 처리하기 위해 파이프라인에는 고전적 사후 처리기가 포함됩니다:

   • 실행 가능성 검사: 원-핫 제약 조건을 확인합니다.
   • 복구(Repair): 결정론적 다항 시간 알고리즘(특히 할당 문제를 위한 헝가리안 알고리즘 또는 스왑 기반 휴리스틱)을 사용하여 노이즈가 있는 실행 불가능한 비트 문자열을 가장 가까운 실행 가능한 솔루션(예: 유효한 순열)으로 투영합니다.
   • 스코어링: 복구된 후보들에 대해 정확한 목적 함수를 평가합니다.
   • 이론적 근거: 복구 맵은 총 변동 거리(total variation distance)에서 수축(contraction)임을 보이며, 최적해의 확률 질량을 감소시키지 않습니다.

3. 노이즈 강건성 분석(Noise-Robust Analysis):
   저자들은 장치 노이즈와 최적 샘플링 질량의 저하 사이의 관계를 나타내는 리프시츠 유형(Lipschitz-type) 경계(bound)를 도출합니다. 이들은 유효 에러 당 레이어별 에러가 충분히 낮을 경우, 노이즈가 있는 최적 질량이 역다항식 수준을 유지하는 "노이즈 윈도우"를 설정합니다. 이를 통해 높은 확률로 최적해를 회복하는 데 필요한 다항 샷 버젯(shot budget)을 계산할 수 있습니다.

주요 기여

1. FPRAS$_q$ (Exact-Hit):
   이상적인 샘플러가 최적해에 역다항식 질량을 할당하는 저노이즈 영역에서, NP-HQ 파이프라인은 **완전 다항 시간 무작위 근사 스킴(Fully Polynomial Randomized Approximation Scheme, FPRAS$_q$)**을 구성합니다. 이는 다항 시간(양자 회로 호출 + 고전 사후 처리) 내에 확률 $1-\delta$로 전역 최적해를 찾는 것을 보장합니다.

2. $\varepsilon$-PTQAS (Approximation):
   Exact-hit 영역을 넘어, 본 파이프라인은 **$\varepsilon$-다항 시간 양자 근사 스킴($\varepsilon$-PTQAS)**을 제공합니다. 복구로 인한 목적 함수 팽창(inflation)이 제어된다면, 이 알고리즘은 다항 시간 실행 시간 내에 $(1+\varepsilon)$-근사치를 산출합니다.

3. 양자-고전 분리(Quantum-Classical Separation):
   본 논문은 NP-HQ 파이프라인과 순수 고전적 전략 사이의 조건부 분리를 확립합니다. 만약 고전적 샘플러가 다음을 갖더라도:

   • 동일한 효율적인 복구 맵(헝가리안 투영)에 대한 접근 권한.
   • 제약 구조에 대한 완벽한 접근(예: 행 원-핫 문자열에서 균등하게 샘플링).
   • 다항 시간 실행 능력.
     이 방식은 NP $\subseteq$ BPP가 아닌 한, NP-난해 커널 허용 가족(kernel-admissible families)에 대한 역다항식 최적 중첩(optimal overlap)을 재현할 수 없습니다. 양자 우위는 오직 샘플링 분포의 생성 단계에 엄격히 국한됩니다.

4. Heavy-Hitter QAOA (HH-QAOA):
   고전 사후 처리 비용을 줄이는 개선된 방식입니다. 양자 분포의 기하학적 구조를 활용하여, 알고리즘은 "헤비 히터(heavy hitters, 고빈도 샘플)"를 식별하고 후보 집합을 필터링합니다. 이를 통해 근사 보장을 희생하지 않으면서 고전 사후 처리 복잡도를 $O(n^{k+4})$에서 $O(n^{k+3})$(또는 추가 압축 시 그 이하)로 줄입니다.

5. 하드웨어 시연:
   완전한 파이프라인은 최대 100개의 논리 변수를 가진 QOptlib TSP 인스턴스를 사용하여 두 개의 서로 다른 127-큐비트 IBM Eagle-r3 프로세서(ibm_brisbane 및 ibm_sherbrooke)에서 실행되었습니다.

   • 결과: 강력한 노이즈(두 큐비트 에러율 $\sim 10^{-3}$ ~ $10^{-2}$)에도 불구하고, 결정론적 복구가 모든 샘플에 대해 실행 가능성을 복구했습니다.
   • 성능: 복구된 솔루션은 테스트된 모든 케이스에서 발표된 참조 투어(reference tours)와 일치하거나 이를 능가하였으며, 이는 본 접근 방식의 현행 하드웨어 상의 생존 가능성을 입증합니다.

의의 및 주장
본 논문은 다음을 결려한 최초의 엔드 투 엔드 최적화 보장을 제공한다고 주장합니다:

• 유한 샷 최적해 회복.
• 결정론적 실행 가능성 복구.
• 회복된 최적 질량에 대한 명시적인 유한 노이즈 하한선.
• 다항 샷 복잡도 및 다항 사후 처리 실행 시간.

저자들은 제약이 있는 양자 최적화가 (OFM 커널을 통한) 양자 역학적 구조와 (복구 맵을 통한) 고전적 처리 모두에서 문제 구조를 활용하는 통합된 파이프라인으로 간주되어야 한다고 주장합니다. 본 연구는 NISQ 시대에도 얕은 제약 회로와 엄격한 고전적 사후 처리를 결합하면 증명 가능한 근사 스킴과 경쟁력 있는 결과를 실제 하드웨어에서 얻을 수 있음을 보여줍니다.

한계 및 범위

• 보장은 **인스턴스 의존적(instance-dependent)**이며, 양의 위상 분리($\delta > 0$)와 충분한 믹서 엔벨로프 가중치의 존재에 의존합니다.
• "Exact-hit" 보장은 특정 노이즈 윈도우 내에서만 유효하며, 이 범위를 벗어나면 근사 스킴으로 저하됩니다.
• 양자-고전 분리는 NP $\not\subseteq$ BPP라는 가정에 대한 조건부 사항입니다.
• 하드웨어 실험은 하드웨어 네이티브 재최적화보다는 일반적인 QAOA 최적화로부터 얻은 고정된 웜 스타트(warm-start) 파라미터를 사용하였으므로, 노이즈가 있는 장치로의 파라미터 전이 가능성을 테스트합니다.