Comment on "Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency": Polynomial Evaluation of the Triplet-Block Readout

기술 요약: 확장 가능한 양자 기계 학습: 학습 가능성, 표현력 및 효율성 – 트리플릿 블록 판독의 다항식 평가

문제 정의
본 연구는 문헌 [1]에 기술된 양자 기계 학습 아키텍처 내의 "지도 학습형 2체 판독(supervised two-body readout)"을 계산하는 데 드는 고전적 계산 비용에 관한 특정 주장을 다룬다. 문헌 [1]은 "트리플릿 블록" 상태로 초기화된 $n$개의 페르미온 모드 시스템을 분석한다. 여기서 입력 상태는 $|\Psi_{\text{in}}\rangle = |\Psi_6\rangle^{\otimes m} \otimes |0\rangle^{\otimes (n-6m)}$로 정의되며, $|\Psi_6\rangle = (|111000\rangle + |000111\rangle)/\sqrt{2}$이다. 이 시스템은 수동적 페르미온 선형 광학(FLO) 연산을 거치며, 판독은 2체 수 밀도 상관계수(two-body number correlators)의 벡터인 $q_{ij} = \langle n_i n_j \rangle$로 구성된다.

문헌 [1]은 입력 상태가 "폼 랭크(form-rank)" 3을 가지기 때문에(랭크-2 상태에서 사용 가능한 혼합-파피언(mixed-Pfaffian) 압축을 사용할 수 없음), 유일하게 실행 가능한 고전적 시뮬레이션 경로는 가우시안 상태 확장(Gaussian-state expansion)뿐이라고 주장했다. 이 확장은 $\chi = 2^{k/3}$개의 항을 포함하며, 이에 따라 $O(\chi^2 \text{poly}(n)) = O(2^{2k/3} \text{poly}(n))$의 고전적 평가 비용을 초래한다. 결과적으로 문헌 [1]은 이 판독 벡터를 계산하는 것이 고전적으로 불가능(exponential in $k$)하며, 따라서 이와 관련된 지도 학습 특징(supervised learning features)은 고전적으로 접근 불가능하다고 결론지었다.

방법론
저자는 전체 가우시안 확장의 필요성에 이의를 제기하며, 관측량과 입력 상태의 특정 구조에 집중한다. 방법론은 다음과 같이 진행된다:

1. FLO 하에서의 고정된 체(Fixed-Body) 폐쇄성: 수동적 FLO 유니터리 $U_W$는 $r$-입자 섹터에서 페르온 상태의 $r$-입자 축소 밀도 행렬(RDM), $\Gamma^{(r)}$의 선형 변환을 통해 작용함을 입증한다. 구체적으로, 입력 상태가 $\rho$일 때, 출력 상태 $\rho_{\text{out}} = U_W \rho U_W^\dagger$는 다음을 만족한다:
   $$\Gamma^{(r)}_{\rho_{\text{out}}} = R_r(W) \Gamma^{(r)}_{\rho} R_r(W)^\dagger$$
   여기서 $R_r(W) = \bigwedge^r W$는 단일 입자 유니터리 $W$의 $r$-번째 외적(exterior power)이다. $R_r(W)$의 행렬 요소는 $W$의 $r \times r$ 부분 행렬들의 행렬식(determinants)이다.

2. 대각 입력 구조: 저자는 특정 트리플릿-블록 입력에 대해 2-입자 축소 밀도 행렬($r=2$)이 명시적으로 대각 행렬임을 입증한다. 이는 트리플릿 상태의 두 가지 분기($|111000\rangle$과 $|000111\rangle$)가 3개의 점유된 모드에 의해 서로 다르기 때문이다. 따라서 임의의 2체 연산자(최대 2개의 모드만 변화시킬 수 있음)는 이 두 분기 사이의 결맞음(coherence)을 갖지 않는다. $\Gamma^{(2)}_{\text{in}}$의 대각 성분들은 인덱스에 따라 $1/2, 1/4,$ 또는 $0$인 명시적으로 계산 가능한 상수들이다.

3. 결정론적 전파: 저자는 대각적인 입력 $\Gamma^{(2)}_{\text{in}}$의 특성과 선형 전파 규칙을 결합하여, 출력 상관계수에 대한 폐쇄형 식(closed-form expression)을 도출한다. 임의의 쌍 $(i, j)$에 대한 기대값은 $W$의 해당 부분 행렬들의 행렬식의 절댓값 제곱에 의해 가중치가 부여된 입력 RDM의 대각 성분들의 합으로 계산된다.

주요 기여 및 결과

• 다항 시간 알고리즘: 본 논문은 전체 2체 상관계수 벡터 $q(x, \theta)$를 $O(n^4)$ 시간 내에 계산하는 결정론적 고전 알고리즘을 제시한다. 이 복잡도는 블록의 수 $m$(따라서 $k$)이나 전체 상태의 폼 랭크와 무관하다.
• 고정된 $r$-관측량으로의 일반화: 본 연구는 결과를 임의의 입자 보존 $r$-체 기대값으로 일반화한다. 입력 $r$-입자 RDM을 고전적으로 구할 수 있다면, 출력 기대값은 $O(n^{2r})$ 시간(구체적으로 $O(r^3 \binom{n}{r}^2)$) 내에 계산 가능하다. 입력 RDM이 대각 행렬인 경우 비용은 $O(n^{2r})$이다.
• 지수적 비용의 반박: 저자는 문헌 [1]에서 인용된 $O(2^{2k/3})$ 경계가 근본적인 복잡도 이론적 하한이 아니라, 최적화되지 않은 시뮬레이션 방법(전체 가우시안 확장)을 사용한 결과임을 입증한다. 트리플릿-블록 판독의 특정 구조 덕분에 효율적인 고전적 시뮬레이션이 가능하다.

의의 및 주장
본 논문은 트리플릿-블록 입력을 위한 지도 학습형 2체 판독이 지수적 고전 시간을 요구한다는 문헌 [1]의 주장이 유효하지 않음을 단언한다. 구체적으로:

• 특징 벡터의 "고전적 접근 불가능성"이 제거되었다. 즉, 벡터와 그 기울기(gradients)를 효율적으로 계산할 수 있다.
• "기대값의 어려움(expectation-value hardness)"이 이러한 특정 모델에 대한 고전적 시뮬레이션의 장벽을 의미한다는 결론이 뒤집혔다.
• 본 결과는 기울기 분산(gradient variance), 배런 플래토(barren plateaus), 파라미터 시프트 규칙(parameter-shift rules) 또는 샘플링 어려움과 같은 문헌 [1]의 다른 결론에는 영향을 미치지 않는다. 샘플링 어려움은 여전히 존재하는데, 이는 전체 출력 확률가 시스템 크기에 따라 증가하는 체(body) 차수의 상관관계에 의존하며, 이는 고정된 $r$-체 RDM에 의해 포착되지 않기 때문이다.

참고 사항
저자는 문헌 [1]의 버전 2(2026년 8월 20일 게시)가 이후 트리플릿 인코딩과 그와 관련된 기대값 어려움 주장을 삭제했으며, 이는 일반적인 형태의 고정된 체 시뮬레이션 가능성을 인정한 것이라고 언급했다. 본 논문은 이러한 수정에 대한 기술적 정당성을 제공한다.