Role of overparametrization in quantum approximate optimization

기술 요약: 양자 근사 최적화에서 과매개변수화(Overparametrization)의 역할

문제 정의
변분 양자 알고리즘(Variational Quantum Algorithms, VQAs)은 짧은 결맞음 시간(coherence times)과 게이트 오류로 인해 제약을 받는 노이즈가 있는 중규모 양자(NISQ) 장치에서 문제를 해결하기 위한 주요 접근 방식입니다. 이 분야의 핵심적인 미결 과제는 실질적인 문제를 효율적으로 해결하는 데 필요한 최소한의 양자 자원(특히 회로 깊이)을 결정하는 것입니다. 과매개변수화—즉, 특정 임계값을 초과하는 수의 매개변수를 사용하는 것—는 고전 머신러 러닝과 일부 양자 맥락에서 수렴성을 개선하고 바렌 플래토(barren plateaus)를 피하는 데 도움이 된다는 것이 입증되었으나, 종종 NISQ의 역량을 초과하는 회로 깊이를 요구합니다. 본 연구는 양자 근사 최적화 알고리즘(QAOA)을 사용하여 조합 최적화 문제를 높은 확률로 해결하기 위해 과매개변수화가 충분조건인지, 그리고 필요조건인지를 조사합니다.

방법론
저자들은 양자 피셔 정보(Quantum Fisher Information, QFI) 행렬의 계수(rank)를 기반으로 변분 회로의 표현력을 정량화하는 개념인 **유효 양자 차원(Effective Quantum Dimension, EQD)**을 사용하여 과매개변수화를 정의합니다. 회로의 매개변수 수(깊이)를 늘려도 EQD가 더 이상 증가하지 않을 때, 해당 회로는 과매개변수화된 것으로 간주됩니다.

본 연구는 두 가지 대표적인 NP-hard 조합 최적화 문제에 집중합니다:

1. MAX-CUT: 2-정규 그래프(disagrees의 링), $k$-정규 그래프, 그리고 무작위 가중치 없는 그래프에서 조사되었습니다.
2. MAX-2-SAT: 다양한 절(clause) 밀도를 가진 무작위 인스턴스에 대해 조사되었습니다.

각 문제에 대해 저자들은 과매개변수화 깊이($p_c$, EQD가 포화되는 지점)와 최적 깊이($p^*$, 특정 에너지 오차 허용 범위 $\epsilon$ 내에서 해를 얻기 위해 필요한 최소 깊이)를 비교합니다. 저자들은 레이어별 휴리스틱 전략(layerwise heuristic strategies)과 무작위 매개변수 초기화를 사용하여 서로 다른 회로 깊이에 따른 에너지 오차와 성공 확률을 추적하기 위해 수치 시뮬레이션을 수행했습니다.

주요 기여 및 결과

• 2-정규 그래프에서의 MAX-CUT:

  • 저자들은 큐비트의 수가 $n$인 짝수인 경우, 최적의 QAOA 깊이가 $p^* = \lfloor n/2 \rfloor$로 스케일링된다는 분석적 증명을 제공합니다.
  • 수치적 결과는 $n=20$까지의 시스템에 대해 과매개변수화 깊이 $p_c$가 이 최적 깊이와 정확히 일치함($p_c = p^*$)을 확인해 줍니다.
  • 결론: 이 특정 클래스의 문제에 대해, 과매개변수화는 높은 확률로 해를 찾기 위한 충분조건이자 필요조건입니다.

• 일반 그래프(정규 및 무작위)에서의 MAX-CUT:

  • 수치 분석 결과, 대부분의 인스턴스에서 최적의 해는 과매개변수화 깊이와 정확히 일치하거나 그 직근방에서 발견됩니다.
  • 해를 찾는 성공 확률은 과매개변수화 미달(underparametrized) 영역에서 과매개변수화 영역으로 전환될 때 급격히 증가합니다.
  • 결론: 과매개변수화는 높은 확률의 성공을 위한 충분조건입니다. 모든 개별 인스턴스에 대해 엄격하게 필요하지는 않지만, 지배적인 비율의 인스턴스들에 대해서는 통계적으로 필요합니다.

• MAX-2-SAT:

  • MAX-CUT과는 극명하게 대조적으로, MAX-2-SAT 인스턴스의 대다수는 과매개변수화 미달 영역($p/p_c \ll 1$) 내에서 잘 해결됩니다.
  • $n=7$인 경우, 약 85%의 인스턴스가 과매개변수화 깊이의 절반 수준에 불과한 낮은 회로 깊이로 해결되었습니다.
  • 최적 깊이는 $p^* \sim \sqrt{2^n}$으로 스케일링되는 반면, 과매개변수화 깊이는 $p_c \sim 2^n$으로 스케일링됩니다. 결과적으로, 비율 $p^*/p_c$는 문제 크기에 따라 지수적으로 감소합니다.
  • 결론: 과매개변수화는 MAX-2-SAT 인스턴스를 해결하기 위해 필요하지 않습니다. 훨씬 더 얕은 회로를 통해서도 높은 성공 확률을 달성할 수 있습니다.

의의 및 주장
본 논문은 과매개변수화와 최적 회로 깊이 사이의 관계가 **문제 의존적(problem-dependent)**이라고 주장합니다.

• MAX-CUT의 경우, 과매개변수화는 임계값 역할을 합니다. 회로의 표현력(EQD)을 포화시키는 데 필요한 깊이가 문제를 해결하는 데 필요한 깊이와 일치합니다.
• MAX-2-SAT의 경우, 연구 결과는 QAOA가 과매개변수화 미달 영역에서도 유망함을 보여줍니다. 이러한 문제들은 과매개변수화 깊이보다 훨씬 얕은 회로로도 해결될 수 있으므로, QAOA는 과매개변수화된 영역만을 중심으로 한 기존 연구들이 제시했던 것보다 현재의 NISQ 장치에서 더 실행 가능할 수 있습니다.

저자들은 과매개변수화가 특정 이론적 프레임워크에서는 수렴을 보장하지만, 모든 조합 최적화 문제에 대한 보편적인 요구 사항은 아니라는 점을 강조합니다. 이러한 발견은 MAX-2-SAT와 같은 특정 문제 클래스의 경우, 노이즈와 훈련 문제(예: 바렌 플래토)를 유발하는 깊은 회로 없이도 자원 효율적인 솔루션을 찾을 수 있음을 시사합니다. 그러나 저자들은 과매개변수화 미달 영역에서도 큰 규모의 문제에 대해서는 바렌 플래토와 같은 훈련 제한 문제가 여전히 지속될 수 있다고 언급했습니다.