The optimization landscape of peaked-circuit generation

기술 요약: 피크 회로 생성의 최적화 지형(Optimization Landscape)

문제 정의
본 논문은 검증 가능한 양자 우위(verifiable quantum advantage)를 위한 제안된 경로인 "피크 회로(peaked circuits)"의 생성 병목 현상을 다룬다. 피크 회로는 무작위하게 보임에도 불구하고, 출력 확률 질량의 일정 비율이 단일 계산 기저 문자열(computational-basis string)에 집중되는 무작위 양자 회로이다. 해당 출력을 검증하는 것은 타겟 문자열을 알고 있는 고전적 검증가에게는 효율적이지만, 해당 회로를 고전적으로 생성하는 것은 어렵다. Aaronson과 Zhang(AZ)은 변분적 접근 방식을 제안했다: 깊이 $n$인 무작위 Haar 브릭월(brickwall)에 깊이 $n/2$인 학습 가능한 브릭월을 부착한 후, 모든-0(all-zero) 문자열의 확률을 최대화하도록 파라미터를 최적화하는 방식이다. AZ는 그들의 경사 하강법 최적화 도구가 크기에 따라 결정되는 천장에 도달하여 정체되는 것을 관찰했으며, 이를 바렌 플래토(barren plateau)의 탓으로 돌렸다. 그들은 두 가지 가능성 사이의 이분법을 남겨두었다: 최적화 도구가 국소 최적해(local optima)에 갇힌 것인지(이는 더 나은 알고리즘이 더 높은 곳에 도달할 수 있음을 의미함), 아니면 효율적인 생성 방법 자체가 존재하지 않는 것인지에 대한 문제이다. 본 논문은 이 이분법을 해결하기 위해 최적화 지형을 매핑하고, 도달 가능한 피크도(peakedness)의 스케일링을 규명한다.

방법론
본 연구는 1차원 개방 경계 브릭월 회로의 노이즈 없는 상태 벡터 시뮬레이션을 사용하여 엄격하게 사전 등록된 실험 프로토콜을 채택한다.

• 회로 구조: 시스템은 무작위 섹션 $U_r$ (깊이 $\tau_r = n$)과 학습 가능한 섹션 $V(\theta)$ (깊이 $\tau_p = n/2$)로 구성된다. 학습 가능한 게이트는 2-큐비트 블록당 15개의 Pauli 회전의 곱으로 이루어지며, 파라미터 수는 $P = \Theta(n^2)$이다.
• 최적화 프로토콜: 주요 프로토콜은 특정 학습률 스케줄을 가진 Adam 최적화 도구를 사용하며 400단계를 수행한다. 연구에서는 "안정적-국소 클래스(stable-local class)"의 최적화 도구(다항식 단계 크기를 갖는 경사 흐름 유사 역학 및 독립적 재시작)를 정의한다.
• 실험 설계: 저자는 $n=8$에서 $14$까지의 크기에 대해 18개의 인스턴스를 테스트했으며,$n=16$에 대해서는 18개 인스턴스로의 "캐치업(catch-up)"을 사전 등록했다. 저자는 지형의 특성과 최적화 예산의 한계를 구분하기 위해 대규모 재시작 앙상블(최대 800회 재시작)을 활용했다.
• 지형 분석: 논문은 Weingarten 미적분법을 통해 정확한 모멘트(최대 4차)를 포함한 목적 함수 $\delta(\theta)$의 정적 특성, 경사 통계, 그리고 근접 최적해들 사이의 경로 최솟값을 측정하기 위한 스트링 방법(string methods)을 이용한 연결성을 분석한다.
• 최적화 도구 비교: 사전 등록된 블록에서는 서로 다른 초기화 조건 하에서 Adam을 L-BFGS-B 및 일반 SGD와 비교하여 최적화 도구 특유의 이점이 있는지 테스트했다.

주요 기여 및 결과

1. 고정 기반 스케일링 법칙의 거부:
   본 논문은 AZ가 제안한 고정 지수 감소 법칙($1.189^{-n}$)을 거부한다. 저자는 도달 가능한 피크도의 국소 감소율이 일정하지 않고 시스템 크기에 따라 단조 증가하며 가팔라진다는 것을 입증한다.

• 감소율은 $n=8$에서 큐비트당 약 $1.16$에서$n=16$에서 약$1.295$로 증가한다(수렴된 실행 기준).
• 결과적으로, 접근 가능한 크기에서 얻은 데이터를 바탕으로 할 때 AZ가 제공한 $n=50$에 대한 외삽(extrapolation)은 근거가 없다. 도달 가능한 피크도는 이전에 추정된 것보다 더 빠르게 축소된다.

2. 최적화 지형의 특성 규명:

• 바렌 플래토 없음: 평균 경사와 헤시안(Hessian)은 (Haar-무작위 상태에서 예상되는 대로) 동일하게 0이 되지만, 초기화 시 경사의 분산은 Haar 한계보다 $O(1)$만큼만 클 뿐이다. "바렌 플래토"는 급격히 줄어드는 도달 범위를 설명하지 못한다. 최적화 도구는 초기 상태에 존재하지 않았던, 최적화 과정 동안 획득된 구조를 활용한다.
• 연결된 선반(Connected Shelf), 오버랩 갭(Overlap Gap) 없음: 스트링 방법을 통한 직접적인 연결성 측정 결과, 근접 최적해들은 "트랩 스케일"(Haar floor $2^{-n}$)에서 단일 연결 성분을 형성한다. 탈상관화된 해들 사이의 경로는 트랩 스계보다 $10^2$–$10^3$배 높게 유지된다. 이는 트랩 스케일에서의 어려움이 클러스터링(금지된 중간 오버랩을 가진 군집화)을 특징으로 하는 오버랩 갭 메커니즘 때문이라는 주장을 반박한다.
• 심화되는 주름(Deepening Corrugation): 연결되어 있음에도 불구하고, "선반"은 점점 더 주름져 간다. 경로 최솟값에 대한 중앙값은 종점 값 대비 $\approx 0.871^n$으로 감소하며, 이는 어떤 고정된 멱함수(power law)보다 빠르다. 파편화(fragmentation)가 아닌, 이 심화되는 주름이 어려움의 본질을 규명한다.

3. 최적화 도구의 강건성 및 어려움에 대한 가설:

• 하향 실패(Downward Failure): 등록된 안정적-국소 클래스 내의 일반 SGD는 고정된 예산 내에서 Adam만큼의 피크도에 도달하는 데 실패하지만, 이는 지형 자체보다는 "페이싱(pacing, 단계 크기)"의 문제로 귀인된다.
• 상향 초과(Upward Exceedance): 사전 등록된 비교에서, 준-뉴턴 방법인 L-BFGS-B는 $n=16$에서 세 개의 인스턴스에 대해 수렴된 Adam보다 $3.9 \pm 1.6\%$ 더 높은 도달 범위를 달축했다.
• 어려움 가설의 철회: 이러한 초과는 사전 등록된 파실리파이어(falsifier)를 작동시켜, "클래스 내의 어떤 통계도 줄어드는 도달 범위를 이길 수 없다"는 저자의 가설을 철회하게 했다. 그러나 스케일링 법칙은 여전히 유효하다: L-BFGS-B의 도달 범위조차 큐비트당 약 $1.3$의 비율로 축소된다.

4. 이론적 경계:

• 심층 한계 천장(Deep Limit Ceiling): 저자는 심층 한계(scrambled state가 Haar인 경우)에서, $poly(n)$파라미터를 가진 어떠한 프로브 제품군도 기대 피크도를$poly(n) 2^{-n}$ 이상으로 달성할 수 없음을 증명한다.
• 유한 깊이: 유한 깊이에서, 도달 가능한 피크도는 이 심층 한계를 $n$에 따라 증가하는 인자로 초과하며, 이는 최적화 도구가 2차 진폭 통계에는 보이지 않는 유한 깊이 구조를 활용함을 나타낸다.

의의 및 주장
본 논문은 단순히 더 나은 최적화 도구를 찾는 것이 아니라, 지형을 규명함으로써 AZ가 제안한 이분법을 해결한다고 주장한다.

• 장애물: 피크 회로를 생성하는 주요 장벽은 바렌 플래토나 오버랩 갭(클러스터링)이 아니라, 연결된 지형 위에서의 "줄어드는 도달 범위(shrinking reach)"이다. 도달 가능한 피크도는 큐비트 수가 증가함에 따라 고정된 지수보다 더 빠르게 감소한다.
• 양자 우위에 대한 시사점: $n=50$에서의 실험적 실현 가능성에 대한 AZ의 추정치는 근거가 없다. 급격히 가팔라지는 감소율은 더 나은 최적화 도구를 찾더라도 피크 회로를 생성하는 것이 이전에 생각했던 것보다 훨씬 더 어려울 것임을 시사한다.
• 주장의 겸손함: 저자는 "클래스 내의 어떤 최적화 도구도 줄어드는 도달 범위를 이길 수 없다"는 가설을 철회했음을 명시적으로 밝히지만, 측정된 장애물(그 줄어드는 비율 자체)은 지금까지 테스트된 모든 최적화 도구에 대해 유효하다. 본 논문은 $n=50$까지 효율적으로 스케일링되는 방법을 찾았다고 주장하는 것이 아니라, 단순한 외삽을 배제하고 생성 병목 현상을 정의하는 구체적인 기하학적 특징(가팔라지는 감소, 심화되는 주름)을 제공하는 정밀한 부정적 규명을 제공한다.

요약하자면, 본 논문은 피크 회전의 생성이 고정된 지수보다 더 빠르게 줄어드는 도달 범위를 가진 지형에 의해 방해받으며, 이는 클러스터링이 아닌 연결된 선반 위의 심화되는 주름에 의해 발생하는 현상임을 확립한다.