A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

기술 요약: 양자 교대 연산자 안사츠(Quantum Alternating Operator Ansatz)를 위한 파라미터 설정 휴리스틱

문제 정의
양자 교대 연산자 안사츠(QAOA)는 조합 최적화 문제를 해결하기 위한 저명한 매개변수화된 양자 알고리즘이다. 그러나 고품질의 매개변수($\vec{\gamma}, \vec{\beta}$)를 효율적으로 찾는 것은 여전히 중요한 실질적 과제로 남아 있다. 매개변수 설정 과정은 일반적으로 비용 함수의 기댓값을 양자 하드웨어에서 평가하거나 비용이 많이 드는 클래식 시뮬레이션을 통해 업데이트하는 변분 양자-클래식 루프를 포함한다. 이 과정은 바렌 플래토(barren plateaus), 수많은 국소 최적해(local optima), 그리고 큐비트 수($n$) 또는 회로 깊이($p$)가 증가함에 따라 기댓값의 정확한 클래식 평가에 필요한 자원의 지수적 스케일링 문제에 직면한다. 또한, 현재의 노이즈 중간 규모 양자(NISQ) 장치들은 노이즈와 유한한 샘플링 오류를 통해 이러한 문제를 악화시킨다.

방법론
저자들은 비용 함수 기댓값의 비용이 많이 드는 양자 또는 클래식 평가를 효율적인 클래식 모델로 대체하기 위해 설계된 클래식 전략인 "동질적 휴리스틱(Homogeneous Heuristic)을 위한 파라미터 설정"을 제안한다. 이 접근 방식의 핵심은 완전 동질성(Perfect Homogeneity) 개념에 기초한다.

1. 완전 동질성: 이는 모든 비트 문자열 $x$가 동일한 비용 값 $c(x)$를 공유할 때 동일한 양자 진폭을 갖는 상태 특성으로 정의된다. 이 성질은 특정 대칭 문제나 작은 매개변수의 극한에서만 정확하게 성립하지만, 경험적 관찰에 따르면 다양한 설정에서 QAOA 상태와 완전 동질적 상태 사이의 중첩(overlap)이 매우 높게 나타난다.
2. 클래식 동질적 프록시(Classical Homogeneous Proxy): 저자들은 완전 동질성을 가정함으로써 이를 강제하는 "클래식 동질적 프록시"라고 불리는 클래식 모델을 구축한다. 이 프록시에서 상태는 $2^n$개의 진폭이 아니라, 각 고유한 비용 값에 대응하는 진폭 집합 $Q(c)$로 기술된다.
   • 진화는 "경로의 합(sum-of-paths)" 관점을 사용하여 모델링된다. 저자들은 특정 해밍 거리(Hamming distance)에서의 비트 문자열의 정확한 개수를 $n(x; d, c)$ 대신, 오직 비용 클래스에만 의존하는 분석적으로 도출된 분포 $N(c'; d, c)$로 대체한다.
   • 이를 통해 각 레이어 $\ell$에서의 진폭 $Q_\ell(c)$를 식 (5)를 사용하여 재귀적으로 계산할 수 있으며, 이는 $|C|$가 $n$에 대해 다항식으로 성장한다는 조건하에 문제 크기 $n$과 고유한 비용 값의 수 $|C|$에 대해 다항식 시간 내에 스케일링된다.
3. 휴리스틱 루프: 파라미터 설정 절차(알고리즘 3)는 이 프록시를 내부 서브루틴으로 활용한다. 클래식 최적화 도구는 프록시로부터 도출된 비용 기댓값의 추정치를 최소화하는 파라미터 $(\vec{\gamma}, \vec{\beta})$를 탐색한다. 일단 프록시에 대한 최적 파라미터가 발견되면, 이를 실제 QAOA 회로에 직접 적용한다.

본 논문은 무작위로 추출된 절(clause)을 포함하는 무작위 $k$-SAT, Erdős-Rényi 그래프 상의 MaxCut, Max-$k$-XOR를 포함한 특정 제약 충족 문제(CSP) 클래스에 대해 필요한 분포($N(c'; d, c)$ 및 비용 확률 $P(c')$)를 계산하는 방법을 보여준다.

주요 기여

• 완전 동질성의 정의 및 프록시: 저자들은 완전 동질성을 공식화하고, 효율적인 상태 기술 및 기댓값 산출이 가능한 클래식 동질적 프록시를 정의한다.
• 다항식 스케일링: 제안된 방법은 정확한 상태 벡터 시뮬레이션과 관련된 지수적 자원 증가를 피하면서, 변수의 수 $n$과 깊이 $p$ 모두에 대해 다항식 시간으로 스해링되는 프록시 파라미터의 클래식 계산을 가능하게 한다.
• CSP 클래스로의 일반화: 논문은 네 가지 무작위 CSP 클래스에 대한 프록시 분포를 명시적으로 도출하여, 프록시가 단일 인스턴스가 아닌 전체 클래스의 문제를 설명할 수 있음을 보여준다.
• 휴리스틱 프레임워크: 저자들은 이 프록시를 표준 파라미터 최적화 루프에 통합하는 완전한 워크플로우(알고리즘 3)를 도입하며, 파라미터 업데이트 방식의 선택에 있어 유연성을 유지한다.

결과
저자들은 가중치가 없는 Erdős-Rényi 무작위 그래프($G(n, p_e)$) 상의 MaxCut 문제에 대해 휴리스틱을 수치적으로 평가하였다:

• 낮은 깊이 ($p \leq 3$): $n=20$인 그래프에 대해, 휴리스틱은 "파라미터 전이(parameter transfer)" 전략(더 작은 인스턴스로부터 전역적으로 최적화된 파라미터를 전달하는 방식)과 유사한 근사 비율을 얻는 파라미터를 찾아냈다. 성능 차이는 통계적으로 유의미하지 않았으나, 휴리틱이 일부 경우에서 약간 더 높은 평균 성능을 보였다.
• 높은 깊이 ($p \leq 20$): $p=20$까지의 깊이에 대해, 휴리스틱은 깊이가 증가함에 따라 단조 증가하는 근사 비율을 생성하는 파라미터를 성공적으로 식별했다. 반면, 동일한 클래식 자원을 사용한 파라미터 전이 전략은 수렴에 실패했다.
• 프록시 정확도: 수치 분석 결과, 프록시는 특히 선형 램프(linear ramp) 파라미터 스케줄을 사용하는 경우와 $\gamma$ 파라미터가 작은 영역에서 전체 상태 벡터 시뮬레이션과 큰 중첩을 유지함을 보여주었다. 프록시에 사용된 분석적 분포는 무작위 그래프 인스턴스들에 대한 경험적 평균과 높은 상관관계를 갖는 것으로 나타났다.

의의 및 주장
본 논문은 동질적 휴리스틱이 노이즈로 인해 NISQ 장치에서 다루기 어렵거나 지수적 스케일링으로 인해 클래식 방법이 어려운 영역에서 파라미터 설정을 위한 실질적인 경로를 제공한다고 주장한다. 비용이 많이 드는 기댓값 평가를 다항식 시간의 클래식 프록시로 대체함으로써, 이 방법은 이전 전략들이 수렴에 실패했던 더 깊은 QAOA 회로(예: $p=20$)의 탐색을 가능하게 한다.

저자들은 휴리스틱이 모든 특정 인스턴스에 대해 최적의 파라미터를 보장하지는 않지만, 낮은 깊이에서는 기존 방법들과 경쟁력 있는 성능을 보이고 높은 깊이에서는 이를 능가하는 견고한 클래스 단위 전략을 제공한다는 점을 강조한다. 본 연구는 완전 동질성 가정이 보편적으로 정확하지는 않더라도, 많은 조합 최적화 설정(특히 무작위 제약을 포함하는 경우)에서 파라미터 최적화를 유도하기 위한 충분히 정확한 근사치 역할을 한다는 것을 시사한다. 저자들은 인스턴스별 정보를 프록시에 통합하고, VQE와 같은 다른 변분 양자 알고리즘으로 접근 방식을 확장하는 등의 향후 방향을 제시하며 결론을 맺는다.