Refuting the QAOA fixed-angle conjecture

기술 요약: QAOA 고정 각도 가설(Fixed-Angle Conjecture)에 대한 반증

문제 정의
양자 근사 최적화 알고리즘(QAOA)은 조합 최적화 문제, 특히 MaxCut 문제를 위한 선도적인 근사 양자 알고리즘이다. QAOA의 주요 과제는 대규모 문제 인스턴스에 대해 전역 최적 파라미터($\beta, \gamma$)를 찾는 데 드는 계산 비용이며, 이는 고차원 비볼록(non-convex) 최적화 문제를 수반한다. 이를 해결하기 위해 "고정 각도 가설"(Wurtz와 Love [9]에 의해 시작되어 Wurtz와 Lykov [10]에 의해 확장됨)이 제안되었다. 이 가설은 임의의 $d$-정규 그래프(d-regular graph)에 대해, "트리 형태의" 부분 그래프(가irth(girth)가 $girth \ge 2(p+1)$인 그래프)에 특화하여 최적화된 QAOA 성능이 동일한 차수를 가진 임의의 $d$-정규 그래프에 대한 성능의 하한선 역할을 할 것이라고 상정한다. 만약 이 가설이 참이라면, 재최적화 없이 작은 트리 형태의 인스턴스로부터 얻은 파라미터를 임의의 크고 복잡한 그래프로 전이할 수 있게 된다. 이는 $d=3$ 및 $p \le 2$인 경우에 대해 증명되었고 $p=11$까지 수치적으로 지지되었으나, 임의의 깊이 $p$와 차수 $d$에 대한 일반적인 타당성은 아직 증명되지 않은 상태였다.

방법론
본 논문은 다양한 깊이($p$)와 정규성($d$)의 영역에 걸쳐 가설을 테스트하기 위해 분석적 증명과 엄격한 수치적 검증의 결합을 사용한다.

1. 특수 사례에 대한 분석적 증명:

   • Case $p=1$: 저자는 Wang 등 [13]에서 유도된 단일 에지 기대값의 폐형식(closed-form) 표현식을 활용한다. 트리 최적 성능과 일반 그래프에서의 성능 차이를 분석함으로써, 이 증명은 이항 항등식을 사용하여 삼각형(triangle)의 개수에 따른 단조성을 보여준다. 이를 통해 $p=1$일 때 가설이 모든 $d$에 대해 성립함을 입증한다.
   • Case $d \le 2$: 2-정규 그래프(사이클의 불가분 합집합)의 경우, 본 논문은 QAOA를 양자 신호 처리(quantum signal processing) 및 로랑 다항식(Laurent polynomials)과 연결하는 Marwaha [14]의 최근 연구를 활용한다. 이 프레임워크를 통해 사이클에서의 근사 비율을 트리 최적 파라미터를 사용하여 엄격하게 하한하는 방식을 통해, 모든 $p$에 대해 $d \le 2$일 때 가설이 성립함을 증명한다.

2. 반례 구축 ($p=2, d=9$):

   • 가설 생성: 저자는 이진 그래프(bipartite graphs)가 QAOA가 $p=2$에서 관측할 수 있는 짧은 짝수 사이클(특히 4-사이클)을 많이 포함하고 있을 때 가설이 실패할 것이라고 가설을 세운다. 이러한 사이클들은 최대 컷(maximum cut)에서 끊기지 않는 에지($\nu$)의 수를 증가시키지 않는다. 완전 이진 그래프 $K_{d,d}$는 에지당 4-사이클을 극대화하는 구조로 식별되었다.
   • 시뮬레이션 전략: 수치 탐색의 국소 최적해(local optima) 함정을 피하기 위해, 저자는 정밀한 디케 상태(Dicke state) 시뮬레이터를 사용한다. 이는 $K_{d,d}$의 대칭성(구체적으로 $Sym(d) \times Sym(d) \rtimes \mathbb{Z}_2$ 자기동형군)을 활용하여 시뮬레이션 차원을 $2^{2d}$에서 $(d+1)(d+2)/2$로 축소한다.
   • 엄격한 검증: 단순히 트리에서 더 좋은 성능을 보이는 로컬 최적해를 찾는 대신, 본 논문은 더 강력한 명제를 증명한다. 즉, 트리 성능이 특정 임계값 $b$ 이상인 모든 파라미터 $(\beta, \gamma)$에 대하여, $K_{9,9}$에서의 성능은 엄격히 더 낮다. 이는 부동 소수점 오차나 국소 탐색의 한계로 인해 전역 최적해를 놓치는 일을 방지하기 위해 임의 정밀도 중간값-반경 구간 산술(Arb)을 사용하여 전체 유계 파라미터 공간을 포괄함으로써 달성된다.

주요 기여 및 결과
본 논문은 고정 각도 가설에 관한 세 가지 주요 발견을 제시한다:

1. $p=1$에 대한 검증: $p=1$인 경우 모든 $d$-정규 그래프에 대해 가설이 참임을 증명한다. 이 증명은 기대값의 해석적 형태와 이진 그래프(최악의 후보들)가 삼각형이 없다는 사실에 기반한다.
2. $d \le 2$에 대한 검증: 모든 깊이 $p$에 대해 1-정규 및 2-정규 그래프에서 가설이 참임을 증명한다. 이는 QAOA와 양자 신호 처리를 연결하여 사이클에서의 성능을 하한하는 방식을 사용한다.
3. 일반 $d$ 및 $p$에 대한 반증: 본 논문은 일반적인 경우에 대해 고정 각도 가설을 반증하는 구체적인 반례를 제공한다. 구체적으로, 깊이 $p=2$와 차수 $d=9$인 경우, 완전 이진 그래프 $K_{9,9}$는 트리 최적 파라미터를 사용할 때 트리 자체보다 엄격히 낮은 근사 비율을 나타낸다.
   • 트리 최적 값 $f^{tree,*}_{2,9}$는 $b \approx 0.6391275$로 하한된다.
   • 해당 트리 성능을 달성하는 모든 파라미터에 대해, $K_{9,9}$에서의 성능은 최소 $c \approx 0.0029$만큼 엄격히 더 낮다.
   • 이는 트리 구조를 위해 최적화된 파라미터가 밀도가 높은 이진 그래프(짧은 짝수 사이클을 가진)에서 최적 또는 최소한의 성능 보장을 보장하지 못함을 보여준다.

의의 및 주장
본 논문은 $d$-정규 그래프에 대한 QAOA의 일반적인 "고정 각도 가설"을 결정적으로 반증한다고 주장한다. 그 의의는 트리 형태의 부분 그래프로부터 파라미터를 전이하는 전략이 보편적으로 유효하지 않음을 보여주는 데 있다.

• 전략의 한계: $d=9$에서의 반례는 트리 형태의 부분 그래프가 제공하는 "성능 보장"이 모든 정규 그래프, 특히 차수가 높고 짧은 짝수 사이클을 가진 그래프로 자연스럽게 확장되지 않음을 보여준다.
• 대 루프(Large-loop) 가설과의 구별: 본 논문은 고정 각도 가설(트리 파라미터를 임의의 그래프에 사용하는 것)은 거짓이지만, 더 약한 형태인 "대 루프 가설"(그래프 자신의 최적 파라미터를 트리의 최적 성능과 비교하는 것)은 여전히 반증되지 않았음을 명확히 한다. 실제로 $K_{9,9}$의 경우, 그래프 자신의 최적 파라미터는 여전히 트리의 최적 성능보다 우수한 성능을 보이는데, 이는 대 루프 가설과 일치한다.
• 유효 범위: 긍정적인 결과는 특정 영역($p=1$인 모든 $d$, 그리고 모든 $p$에 대해 $d \le 2$)으로 제한된다. 저자는 $d=1, 2$의 경우 MaxCut 문제가 자명하다는 점을 언급하며, 비자명한 양자 이득 시나리오에서 높은 $d$와 $p$에서 가설이 실패한다는 점이 핵심적인 발견이라고 기술한다.

결론적으로, 고정 각도 접근법은 특정 저차수 또는 저차수 영역에서는 유망한 파라미터 프리(parameter-free) 전략을 제공할 수 있지만, 재최적화 없이 임의의 $d$-정규 그래프에 대한 일반적인 솔루션으로 채택될 수는 없다.