Improving the efficiency of QAOA using efficient parameter transfer initialization and targeted-single-layer regularized optimization with minimal performance degradation

기술 요약: 파라미터 전이 및 표적 정규화 최적화를 통한 QAOA 효율성 개선

문제 정의
양자 근사 최적화 알고리즘(QAOA)은 근미래 양자 장치에서 조합 최적화 문제(COP), 특히 MaxCut 문제를 해결하기 위한 유력한 후보입니다. 그러나 QAOA는 문제의 크기($n$)와 회로 깊이($p$)가 증가함에 따라 상당한 어려움에 직면합니다. 최적화 지형은 비볼록성(non-convexity)이 매우 강해지며, 이는 지수적으로 증가하는 솔루션 공간($2^n$)과 선형적으로 증가하는 파라미터 수($2p$)로 인해 발생합니다. 이러한 복잡성은 클래식 최적화 도구를 특히 가중치가 있는 그래프 패밀리에서 하위 최적의 로컬 미니마(local minima)에 빠지게 하여, 낮은 근사 비율($r$)을 초래합니다. 또한, 모든 $2p$ 파라미터를 전체 최적화하는 것은 계산적으로 매우 비용이 많이 들어 많은 시간과 자원을 소모하며, 이는 실질적인 양자 우위 입증을 저해합니다.

방법론
저자들은 성능 저하를 최소화하면서 QAOA의 효율성을 높이기 위해 **파라미터 전이 초기화(parameter transfer initialization)**와 표적 단일 레이어 최적화(targeted-single-layer optimization), 그리고 **L2 정규화(L2 regularization)**를 결합한 하이브리드 전략을 제안합니다.

1. 파라미터 전이 초기화:

   • 이 접근 방식은 유사한 문제 인스턴스들에 대해 최적화된 파라미터들이 서로 군집을 이루는 경향이 있다는 관찰에 기반합니다.
   • "도너(donor)" 그래프($G_1$, 노드 수 $n_d = 8$)를 사용하여 Trotterized Quantum Annealing($t=0.75$)으로 초기화한 후, Adagrad 옵티마이저를 사용하여 전체 최적화를 수행합니다.
   • 이렇게 얻은 최적 파라미터 $\{\gamma^*_i, \beta^*_i\}$를 동일한 그래프 패밀리 내의 더 큰 노드 수를 가진 "액셉터(acceptor)" 그래프($G_2, n_a \ge n_d$)로 전이합니다.

2. 표적 단일 레이어 최적화:

   • 모든 $2p$ 파라미터를 다시 최적화하는 대신, 개별적으로 최적화했을 때 가장 좋은 근사 비율을 제공하는 특정 "표적" 레이어($p_k$)를 식별합니다.
   • 고정된 깊이 $p=15$에 대해, 저자들은 다양한 그래프 패밀리(3-Regular, Erdős–Rényi, Barabási–Albert)에 대해 가장 확률 높은 최적 레이어를 결정하기 위해 각 레이어 $p_k \in [1, 15]$를 체계적으로 테스트했습니다.
   • 이 방법은 다른 모든 레이어를 전이된 값으로 고정한 상태에서, 오직 이 단일 레이어의 파라미터만을 COBYLA(Constrained Optimization By Linear Approximation) 옵티마이저를 사용하여 최적화합니다.

3. 정규화 (L2/Ridge):

   • 전체 최적화 과정 중 옵티마이저가 로컬 미니마에 갇힘으로써 표적 단일 레이어 최적화($r_s$)가 전체 최적화($r_f$)보다 가끔 더 나은 성능을 보이는 불일치 문제를 해결하기 위해, 저자들은 L2(Ridge) 정규화를 도입했습니다.
   • 비용 함수에 패널티 항 $\lambda \sum (\gamma_k^2 + \beta_k^2)$을 추가합니다. 이는 솔루션 지형을 매끄럽게 만들어 옵티마이저가 로컬 미니마를 탈출하도록 돕고, 전체 최적화($r_f$)의 신뢰성을 향상시킵니다.

주요 기여 및 결과
연구는 세 가지 무가중 그래프 패밀리(3-Regular, Erdős–Rényi, Barabási–Albert)와 세 가지 가중치 그래프 패밀리를 대상으로, 노드 수가 8에서 24까지인 그래프들을 사용하여 수행되었습니다.

• 무가중 그래프에서의 성능:

  • 무가중 3-Regular (u3R) 그래프의 경우, 파라미터 전이 접근 방식은 표적 단일 레이어 최적화($r_s$)에서 0.9443의 평균 근사 비율을 달축성했으며, 이는 전체 최적화($r_f$)의 0.9551과 비교했을 때 98.88% 수준입니다.
  • 결정적으로, 이 방식은 전체 최적화 대비 8.06배의 계산 속도 향상을 달성했습니다.
  • 무가중 Erdős–Rényi (uER) 및 Barabási–Albert (uBA) 그래프에서도 유사한 경향이 관찰되었으며, $r_s$는 최적화 시간($\tau$)을 크게 줄이면서도 $r_f$에 근접한 성능을 유지했습니다.

• 가중 그래프에서의 성능:

  • 가중 3-Regular (w3R): 초기화만으로도($r_n$) 종종 Goemans-Williamson 클래식 임계값($r_{GW} \ge 0.878$)을 상회하는 성과를 보였으며, 표적 최적화를 통해 결과가 더욱 개선되었습니다.
  • 가중 Erdős–Rény리 (wER): 노드 수가 커짐에 따라($n_a \ge 14$), $r_s$가 $r_{GW}$ 임계값 아래로 떨어지는 등 어려움을 겪었습니다. 이러한 복잡한 가중 패밀리의 경우, 고품질의 솔루션을 얻기 위해 전체 최적화가 여전히 필요했습니다.
  • 가중 Barabási–Albert (wBA): 이 패밀리는 혼합된 양상을 보였습니다. 전체 최적화가 약간 더 효율적이었으나, 표적 최적화 또한 실행 가능한 대안으로 남았습니다.

• 정규화의 영향:

  • 정규화가 없을 때, 표적 단일 레이어 최적화가 전체 최적화보다 더 우수한 경우가 8.92% 발생했습니다(이는 전체 최적화가 로컬 미니마에 갇혔음을 시사함).
  • L2 정규화를 적용한 결과 이러한 불일치는 **3.81%**로 감소하여, 전체 최적화의 견고성을 크게 향상시켰습니다.

• 옵티마이저 및 초기화 비교:

  • 다양한 옵티마이저(COBYLA, POWELL, GSLS, NELDER-MEAD, SPSA) 중에서 COBYLA가 유사한 정확도를 제공하면서도 가장 낮은 최적화 시간을 기록하여 가장 적합한 것으로 확인되었습니다.
  • 파라미터 전이 초기화는 근사 비율과 필요한 최적화 단계 수 모두에서 TQA 및 랜덤 초기화보다 일관되게 우수한 성능을 보였습니다.

의의 및 주장
본 논문은 효율적인 파라미터 초기화와 표적 단일 레이어 최적화를 결합하는 것이 최소한의 성능 저하로 QAOA의 효율성을 크게 개선할 수 있음을 보여줍니다.

저자들은 이 전략이 정확도와 계산 비용 사이의 트레이드오프를 효과적으로 조절한다고 주장합니다. 작은 규모의 완전히 최적화된 인스턴스로부터 파라미터를 전이함으로써, 이 방법은 탐색 공간을 줄여주는 "준최적(near-optimal)" 시작점을 제공합니다. 이후 전략적으로 선택된 단일 레이어를 최적화하는 과정은 전체 재최적화의 지수적 비용 없이 솔루션을 정교하게 다듬습니다.

이 연구는 이 접근 방식이 무가중 및 특정 가중 그래프 패밀리(w3R 등)에는 매우 효과적이지만, 전체 최적화가 여전히 필요한 복잡한 가중 토폴로지(특히 wER)에 대해서는 보편적인 해결책이 아님을 강조합니다. L2 정규화의 도입은 전체 최적화가 선택적 방법보다 성능이 떨어지지 않도록 안정화하는 핵심적인 완화 전략으로 제시됩니다. 궁극적으로, 본 연구는 파라미터 튜닝과 관련된 클래식 계산 오버헤드를 줄임으로써 QAOA를 더 큰 규모의 조합 문제에 실용적으로 적용할 수 있는 경로를 제시합니다.