Transferred QAOA Parameters Remember the Penalty Scale: A $\lambda$-Resonance Law for Constrained Quantum Optimization

기술 요약: 전이된 QAOA 파라미터의 페널티 스케일 기억 현상

문제 정의
양자 근사 최적화 알고리즘(QAOA)은 결정적인 확장성 병목 현상에 직면해 있다. 즉, 모든 새로운 문제 인스턴스마다 변분 파라미터 $(\beta, \gamma)$를 훈련시키는 것은 "정확한 시뮬레이션 장벽(exact-simulation wall)"으로 인해 근미래 하드웨어에서 계산적으로 매우 불가능하다. 표준적인 해결책은 **파라미터 전이(parameter transfer)**로, 작은 인스턴스에서 훈련된 각도를 더 큰 인스턴스에 재사용하는 것이다. 기존 문헌은 이러한 전이의 성공을 거의 전적으로 구조적 유사성(예: 공유된 그래프 토폴로지, 차수 패리티 또는 로컬 서브그래프 구성) 덕분이라고 설명한다.

그러나 제약 조건이 있는 최적화 문제(페널티 방법을 통해 인코딩된 경우)에서는 독특한 실패 모드가 지속된다. 이러한 문제에서는 비용 함수에 정수 위반 횟수 $v(x)$와 스칼라 가중치 $\lambda$를 곱한 페널티 항 $\lambda v(x)$를 추가하여 제약 조건을 강제한다. 실무자들은 훈련된 각도를 전이할 때, 설령 구조적 특성이 동일하더라도 배포 인스턴스가 훈련 인스턴스와 다른 페널티 가중치 $\lambda$를 사용하는 경우 예측 불가능하게 실패하는 현상을 관찰한다. 현재의 설명들은 이를 "에너지적(energetic)" 튜닝 문제(목적 함수의 신호와 제약 페널티 사이의 균형 문제)로 취급하지만, 왜 $\lambda$에 대해 비단조적인(non-monotonic) 민감도가 나타나는지는 설명하지 못한다.

방법론 및 이론적 프레임워크
본 논문은 페널티 기반 정식화에서 QAOA 파라미터의 전이 가능성이 구조나 에너지에 의해 결정되는 것이 아니라, **양자 간섭(quantum interference)**에 의해 결정된다고 주장한다. 저자들은 고정된 훈련 각도 하에서 페이직 가능한 확률 질량 $F(\lambda)$를 $\lambda$의 함수로서 엄밀하게 수학적으로 규명한다.

1. 경로 확장 및 위상 인자 분해 (Path Expansion and Phase Factorization):
   저자들은 QAOA 상태 진폭을 계산 기저 경로들의 합으로 확장한다. 이들은 특정 위반 횟수 시퀀스 $v = (v_1, \dots, v_p)$를 가진 임의의 경로에 대해, $\lambda$에 대한 의존성이 오직 전역 위상 인자 $e^{-i\lambda \sum_k \gamma_k v_k}$로만 나타남을 입증한다.

2. $\lambda$-공명 정리 ($\lambda$-Resonance Theorem):
   진폭을 제곱하여 확률 $F(\lambda)$를 얻음으로써, 저자들은 $F(\lambda)$가 $\lambda$에 대한 **유한한 실수 삼각 다항식(finite real trigonometric polynomial)**임을 증명한다.

• 스펙트럼 지지 집합 (Spectral Support): 이 다항식의 각주파수 $\omega$는 훈련된 $\gamma$ 파라미터들에 의해 생성된 정수 격자 위에 존재한다: $\Omega = \{ \sum_{k=1}^p \gamma_k m_k \mid m_k \in \mathbb{Z}, |m_k| \le v_{\max} \}$.
• 독립성: 이 결과는 각도가 어떻게 얻어졌는지(경사 하강법, 무작위 등)와 무관하며, 목적 함수 $C(x)$와도 독립적이다. 이는 위반 횟수 $v(x)$의 정수성에만 의존한다.

주요 기여
본 논문은 세 가지 주요 이론적 및 경험적 기여를 확립한다:

1. 공명 동작 (Resonance Behavior): 전이 가능성은 $\lambda$에 대해 단조적이지 않다. 대신, 배포 페널티 $\lambda_{deploy}$가 훈련 페널티 $\lambda_{train}$과 일치할 때 공명 피크를 보인다. 이 일치가 어긋나면 "위반 이력 채널(violation-history channels)" 간의 파괴적 간섭이 발생하여, 실행 가능한 해를 찾을 확률을 급격히 억제한다.
2. 폭 스케일링 법칙 (Width Scaling Law): 공명 피크의 폭은 번스타인 부등식(Bernstein's inequality)에 의해 하한이 제한된다. 최소 폭은 $1 / (v_{\max} \sum_k |\gamma_k|)$에 비례하여 스케일링된다.
   • 시사점: "날카로운(sharp)" 각도 집합(큰 $\sum |\gamma_k|$)은 좁고 취약한 공명을 생성한다. "뭉툭한(blunt)" 각도 집합(작은 $\sum |\gamma_k|$)은 넓고 견고한 플래토(plateau)를 생성하여 캘리브레이션 드리프트와 인스턴스 변화를 더 잘 견뎌낸다.
3. 회생 현상 (Revival Phenomena): 주파수가 이산 격도에 존재하기 때문에, 간섭 패턴은 준주기적(quasi-periodic)이다. 저자들은 $\Delta \lambda \approx 2\pi / \gamma_k$의 간격에서 실행 가능성이 다시 회복되는 "회생 피크(revival peaks)"를 예측하고 관찰한다. 즉, $\lambda$가 훈련 값에서 크게 벗어나더라도 실행 가능성이 복구될 수 있다.

실험 결과
저자들은 20-큐비트 멀티 유저 자원 할당 QUBO(6개 제약 그룹, $v_{\max}=6$)를 사용하여 정확한 상태 벡터 시뮬레이션을 통해 이러한 예측을 검증했다.

• 설정: $\lambda_0 \approx 2.2$에서 동일한 인스턴스로 훈련된 두 가지 서로 다른 각도 집합을 테스트했다: "날카로운" 집합 ($\sum |\gamma_k| \approx 4.29$)과 "뭉툭한" 집합 ($\sum |\gamma_k| \approx 0.61$).
• 피크 위치: 두 집합 모두 $\lambda \approx \lambda_0$에서 피크를 보였으며, 이는 공명 가설을 확인시켜 준다.
• 폭 스케일링: "뭉툭한" 집합은 "날카로운" 집합보다 약 5.4배 더 넓은 공명 폭을 보였으며, 이는 예측된 위상 예산 비율과 일치한다.
• 회생: "날카로운" 집합은 $\lambda_0 \pm 2\pi/\gamma_1$ (약 0.41 및 3.99)에서 명확한 회생 피크를 보인 반면, "뭉툭한" 집합은 테스트된 구간 내에서 회생을 보이지 않았다.
• 스펙트럼 지문: 훈련된 $\gamma$ 값들에 의해 생성된 정수 격도와 정확히 일치하는 주파수 라인을 최소 제곱 스펙트럼 분석을 통해 확인했으며, 이는 에너지적 또는 구조적 설명을 배제하는 "결정적인 테스트"를 제공했다.

의의 및 주장
본 논문은 페널티 기반 QAOA에서 널리 보고된 실패 모드를 "에너지적 튜닝 문제"에서 결정론적이고 예측 가능한 위상 간섭(phase interference) 현상으로 재정의한다고 주장한다.

• 패러다임 전환: 저자들은 구조에 집중한 전이 문헌과 에너지에 집중한 페널티 문헌이 "간섭"이라는 축을 놓쳤다고 주장한다. 훈련된 각도는 특정 훈련 페널티 가중치의 위상 패턴을 효과적으로 기억한다.
• 실무 프로토콜: 저자들은 실무자를 위한 두 가지 비용 제로 프로토콜을 제안한다:
  1. $\lambda$-매칭 ($\lambda$-Matching): 파라미터를 전이할 때, 배포 페널티 가중치는 반드시 기여자(donor)의 훈련 가중치와 일치해야 한다. "안전을 위해" $\lambda$를 휴리스틱하게 높이는 것은 공명을 탈조(detune)시키므로 역효등 효과를 낳는다.
  2. 뭉툭한 기여자 (Blunt Donors): 거의 퇴화된(near-degenerate) 훈련 최적해들 중에서는 작은 $\sum |\gamma_k|$ (낮은 위상 예산)를 가진 해를 선호하라. 이러한 "뭉툭한" 기여자들은 훨씬 더 넓은 공명 폭을 제공하여 캘리브레이션 드리프트와 인스턴스 스케일링에 대해 훨씬 더 견고하다.
• 확장성 경고: 문제 규모가 커짐에 따라 $v_{\max}$가 증가하고, 이로 인해 공명 폭이 줄어든다 ($1/v_{\max}$). 이는 대규모 문제에서는 엄격한 $\lambda$-매칭이 선택이 아닌 필수임을 의미하며, 불일치에 대한 허용 오차가 사라짐을 뜻한다.

결론적으로, 본 논문은 "예측 불가능한" 실행 가능성 붕괴가 실제로는 예측 가능한 스펙트럼 불일치이며, 그 해결책은 재훈련이나 구조적 정렬이 아니라 정밀한 파라미터 매칭과 낮은 위상 예산을 가진 각도 집합의 선택임을 밝힌다.