Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models

기술 요약: 이싱 모델(Ising Models)을 위한 레벨-1 QAOA의 근사 최적 파라미터 튜닝

문제 정의
양자 근사 최적화 알고리즘(QAOA)은 해를 해밀토니안의 바닥 상태(ground state)에 인코딩함으로써 이차 무제약 이진 최적화(QUBO)와 같은 조합 최적화 문제를 해결하기 위해 설계된 하이브리드 양자-고전 알고리즘이다. 회로 깊이($p$)를 높이면 이론적으로 솔루션의 품질이 향상되지만, 실제 구현은 게이트 노이즈, 연결성 제한, 상태 준비 오류 등으로 인해 제약이 있는 노이즈가 있는 중간 규모 양자(NISQ) 장치의 얕은 깊이($p=1$, 또는 QAOA1)에 국한된다.

QAOA1의 핵심적인 병목 현상은 두 개의 변분 파라미터인 $\gamma$와 $\beta$를 최적화하는 것이다. 차원이 낮음에도 불구하고, 비용 지형(cost landscape)은 매우 진동적이며, 진동율은 문제의 크기, 밀도 및 가중치 가변성에 따라 증가한다. 기존의 관행은 거친 그리드 탐색(coarse grid search) 후 국소 최적화(local minimisation)를 수행하는 것으로 충분하다고 제안하지만, 본 연구는 이러한 접근 방식이 지형 왜곡 및 에일리어싱(aliasing)으로 인해 진정한 전역 최적해(global optimum)를 포착하지 못하고 하위 최적의 파라미터 추정치를 도출할 수 있음을 보여준다. 또한, 기존의 파라미터 초기화 휴리스틱 방법들은 성능 보장이 부족하거나 미가중 정규 그래프(unweighted regular graphs)와 같은 특정 그래프 구조에 의존하여, 복잡하고 가중치가 부여된 실제 사례로 일반화되지 못한다.

방법론
저자들은 이싱 모델(QUBO의 양자적 등가물)에 대해 다항 시간 내에 QAOA1 파라미터를 최적화하는 엄격하고 문제 불가지론적인(problem-agnostic) 전략을 제안한다. 이 방법론은 네 가지 주요 이론적 및 알고리즘 단계를 거친다:

1. 푸리에 분석 및 샘플링 요구사항:
   본 논문은 QAOA1 기대값을 부분 푸리에 급수(partial Fourier series)로 모델링한다. 기대값에 대한 폐쇄형 표현식(Theorem 1 및 Corollary 1)을 유도함으로써, 저자들은 비용 지형의 $\gamma$ 차원에 따른 최대 주파수($\omega_{\max}$)를 분석적으로 결정한다. 이 주파수는 특정 문제 인스턴스의 결합 강도($J_{uv}$)와 외부 필드($h_i$)에 따라 달라진다. 나이퀴스트-섀넌 샘플링 정리(Nyquist-Shannon Sampling Theorem)를 적용하여, 저자들은 지형의 왜곡 없이 비용 지형을 정확하게 재구성하는 데 필요한 최소 샘플링 해상도($\Delta\gamma$)를 설정한다. 이는 거친 그리드 탐색에서의 언더샘플링 문제를 해결한다.

2. 차원 축소:
   본 연구의 핵심적인 이론적 기여는 $(\gamma, \beta)$에 대한 2차원 최적화 문제를 $\gamma$에 대한 1차원 탐색으로 축소하는 것이다.

• 외부 필드가 없는 이싱 모델의 경우, 최적의 $\beta^*$는 $\gamma$의 함수로서 분석적으로 유도된다 (Theorem 5).
• 외부 필드가 있는 모델의 경우, 최적의 $\beta^*$는 1차 최적 조건에서 유도된 4차 다항식을 푸는 데 의해 발견된다 (Theorem 6).
  이러한 변환을 통해 알고리즘은 각 지점에서 최적의 $\beta^*$를 계산하면서 $\gamma$에 대한 라인 서치(line search)를 수행할 수 있으며, 이는 계산 복잡도를 크게 줄여준다.

3. 최적화 알고리즘:
   결과적인 단변량 함수(univariate function)의 전역 최적해를 찾기 위해, 저자들은 구간 분석(interval analysis, Green's algorithm)에 기반한 세분화 알고리즘(subdivision algorithm, Algorithm 1)을 채택한다. 이 방법은 삼각 다항식의 최대 모듈러스(maximum modulus)를 효율적으로 추정하여, 단순한 그리드 탐색 없이도 근사 최적의 $\gamma^*$를 식별할 수 있게 한다.

4. 최적점의 집중(Concentration of Optima):
   본 논문은 크고 조밀한 정규 그래프에 대해, 전역 최적 $\gamma^*$가 0에 매우 가깝게 집중되며 첫 번째 국소 최적점과 일치함을 엄격하게 증명한다 (Theorem 7). 유한 크기 그래프에 대한 경험적 분석은 "적대적(adversarial)" 인스턴스(첫 번째 국소 최적점이 전역 최적점과 다른 경우)가 드물며, 주로 작고 희소한 그래프에서 발생함을 확인한다. 이 통찰은 추가적인 단순화를 가능하게 한다: 즉, 최대 주파수에 의해 유도된 샘플링 경계(sampling bound)를 준수하는 단계 크기를 갖는다면, $\gamma \approx 0$ 근처에서 시작하는 경사 하강법(gradient descent)을 사용할 수 있다.

주요 결과
제안된 전략은 QAOA1을 서브루틴으로 사용하여 문제 크기를 재귀적으로 줄이는 방법인 재귀적 QAOA(RQAOA)를 통해 검증되었다. 저자들은 다양한 엣지 확률과 가중치 분포를 가진 대규모, 고밀도, 가중치 부여된 에르도스-레니(Erdős-Rényi) 그래프(128 및 256 정점)를 대상으로 벤치마킹을 수행했다.

• 외부 필드가 없는 경우: 제안된 방법(근사 최적 파라미터를 사용한 RQAOA1)은 테스트된 모든 인스턴스에서 거칠게 최적화된 RQAOA1과 고전적 반정부정 프로그래밍(SDP)을 일관되게 능가했다. 반면, 거칠게 최적화된 RQAOA1은 일반적으로 SDP를 넘어서는 데 실패했다.
• 외부 필드가 있는 경우: 저자들은 표준 RQAOA1이 필드가 있는 모델에서 일관되지 않은 성능을 보이는 것을 관찰했다. 이를 해결하기 위해, 단순화된 반복 반올림 절차를 사용하는 변형인 "Iter-QAOA"를 도입했다. Iter-QAOA는 제안된 파라미터 튜닝 전략과 결합되었을 때, 다양한 그래프 밀도에 걸쳐 SDP 및 표준 RQAOA1 변형보다 일관되게 우수한 성능을 보였다.
• 적대적 인스턴스: 경험적 테스트 결과, 적대적 그래프(첫 번째 국소 최적점이 전역 최적이 아닌 경우)를 만날 확률은 노드가 $n > 14$인 그래프에서 약 1%로 안정화되었으며, 이는 대부분의 실질적인 경우에 대해 0 근처에서 경사 하강법을 사용하는 전략을 정당화한다.

의의 및 주장
본 논문은 임의의 QUBO 문제에 대해 전역적으로 근사 최적에 가까운 파라미터를 효율적으로 찾는 과제를 해결한다고 주장한다. 이 연구의 의의는 다음과 같다:

• 엄격한 보장: 이전의 휴리스틱 접근 방식과 달리, 이 방법은 시스템 크기에 따라 지수적으로 증가하지 않는 공통 가능한(commensurable) 가중치에 대해 증명 가능한 근사 최적성을 가진 다항 시간 알고리즘을 제공한다.
• 문제 불가지론: 이 전략은 그래프의 대칭성, 구조 또는 가중치 분포에 대한 가정을 따르지 않으므로 일반적인 가중치 부여된 이싱 모델에 적용 가능하다.
• 실용적 효율성: 탐색 공간을 축소하고 $\beta^*$에 대한 분석적 해를 활용함으로써, 고해상도 2D 그리드 탐색의 계산 불가능성을 피하면서도 거친 샘플링의 함정을 피한다.
• 성능 향 향상: 적절한 파라미터 튜닝을 통해 얕은 깊이의 양자 알고리즘(QAOA1)이 밀집된 가중치 인스턴스에서 최첨단 고전적 휴리스틱(SDP)을 능가할 수 있음을 보여주며, 이는 변분 양자 알고리즘에서 파라미터 최적화의 결정적인 역할을 강조한다.

저자들은 자신들의 접근 방식이 QAOA1의 파라미터 튜닝 병목 현상을 효과적으로 해결하여, 현재 및 근미래의 양자 하드웨어에서 조합 최적화 문제를 위한 더 신뢰할 수 있고 고품질의 근사치를 제공할 수 있다고 결론짓는다.