Efficient classical computation of the neural tangent kernel of quantum neural networks

본 논문은 매개변수 평균화를 네 개의 이산 클리포드 값으로 축소함으로써 광범위한 양자 신경망 클래스에 대한 뉴럴 탄젠트 커널을 추정하는 효율적인 고전 알고리즘을 제시하여, 이러한 광대역 훈련된 네트워크가 양자 우위를 달성할 수 없음을 입증합니다.

핵심

이 논문은 간단한 언어와 창의적인 비유를 사용하여 설명합니다.

큰 그림: "양자 수정구" 문제

**양자 신경망 (QNN)**이라는 초정교한 기계가 있다고 상상해 보세요. 이는 양자 입자로 만들어진 거대하고 마법 같은 수정구와 같습니다. 이 기계에 데이터를 입력하면 미래 (또는 문제 해결) 를 예측하려 합니다. 이를 작동시키려면 기계 내부에 있는 수천 개의 작은 다이얼 (매개변수) 을 조정해야 합니다.

문제는 무엇일까요? 이러한 다이얼을 조정하려면 보통 실제 양자 컴퓨터에서 기계를 실행해야 하는데, 이는 매우 비싸고 구축하기 어렵습니다. 과학자들은 궁금해했습니다. 우리가 일반 컴퓨터 (예: 노트북) 만 사용하여 이 기계가 어떻게 학습할지 예측할 수 있을까요?

이 논문은 다음과 같이 답합니다: 예, 특정 유형의 양자 기계에 대해서는 가능합니다.

주요 등장인물

1. 양자 기계 (네트워크): 이를 레시피라고 생각하세요. 두 가지 유형의 재료가 있습니다.

   • 고정 재료 (클리퍼드 게이트): 이는 변하지 않는 표준적이고 미리 계량된 향신료와 같습니다. 이들은 "안전"하며 이해하기 쉽습니다.
   • 가변 재료 (매개변수 게이트): 이는 당신이 조절하는 다이얼입니다. 이들은 "해밀토니안" (규칙집이라는 멋진 단어) 에 의해 제어됩니다. 이 논문에서 규칙집은 "파울리 군" (특정 양자 규칙 집합) 을 기반으로 합니다.

2. 신경 탄성 커널 (NTK): 이는 논문의 비밀 무기입니다. NTK 를 기계의 학습 속도 지도로 상상해 보세요. 이 지도는 다이얼을 조절함에 따라 기계의 예측이 어떻게 변할지 정확히 알려줍니다. 이 지도가 있다면, 기계의 행동을 알기 위해 실제로 기계를 학습시킬 필요 없이 답을 계산하기만 하면 됩니다.

마법 같은 트릭: "4 점" 단축키

보통 이 "학습 지도" (NTK) 를 그리려면 다이얼을 모든 가능한 각도 (0 도에서 360 도까지) 로 설정하여 기계를 테스트해야 합니다. 이는 무한한 가능성입니다. 이를 일반 컴퓨터에서 수행하려면 영원히 걸릴 것입니다.

저자들의 혁신:
그들은 마법 같은 단축키를 발견했습니다. 그들은 이 특정 유형의 양자 기계에 대해서는 모든 각도를 테스트할 필요가 없다는 것을 증명했습니다. 오직 네 가지 특정 설정만 테스트하면 됩니다.

• 0 도
• 90 도
• 180 도
• 270 도

왜 이것이 작동할까요?
양자 기계를 복잡한 춤으로 생각하세요. 다이얼이 이 네 가지 특정 각도에 있을 때, "춤 동작" (게이트) 은 매우 단순하고 질서 정연해집니다. 양자 물리학에서 이러한 단순한 동작은 클리퍼드 군이라는 특별한 클럽에 속합니다.

가장 좋은 점은 무엇일까요? 일반 컴퓨터는 클리퍼드 군을 시뮬레이션하는 데 능숙합니다. 이는 혼란스러운 재즈 즉흥 연주 (어려움) 를 시뮬레이션하는 것과 완벽하게 동기화된 행진 밴드 (쉬움) 를 시뮬레이션하는 것의 차이와 같습니다. 다이얼을 이 네 가지 각도로 제한함으로써, 혼란스러운 양자 문제는 일반 노트북이 즉시 해결할 수 있는 단순한 행진 밴드 문제로 변합니다.

결과: 그들이 증명한 것

저자들은 이 단축키를 사용하는 알고리즘 (단계별 레시피) 을 개발했습니다.

1. 정확함: 비록 네 가지 각도만 테스트하지만, 평균 결과는 수학적으로 모든 가능한 각도를 테스트한 것과 동일합니다. 마치 "이 수프를 이 네 가지 특정 순간에 맛보면, 전체 냄비의 짠맛을 정확히 알 수 있다"고 말하는 것과 같습니다.
2. 빠름: 필요한 컴퓨터 시간은 문제 크기에 따라 합리적으로 증가합니다. 무한대로 폭발하지 않습니다.
3. "넓은" 네트워크 한계: 이 논문은 "넓은" 네트워크 (많은 병렬 경로를 가진 기계) 에 초점을 맞춥니다. 최근 수학에 따르면, 이러한 네트워크가 매우 넓어지면 가우시안 프로세스 (통계 모델의 일종) 와 같은 행동을 합니다.
   • 저자들이 효율적으로 "학습 지도" (NTK) 를 계산할 수 있기 때문에, 학습된 기계의 최종 예측도 효율적으로 계산할 수 있습니다.

결론: 여기에는 "양자 우위"가 없음

이 논문은 양자 기계 학습 분야에서 다소 냉소적이지만 중요한 결론으로 끝납니다.

이 논문의 설명에 부합하는 양자 신경망을 구축한다면 (입력에 클리퍼드 게이트를 사용하고 다이얼에 파울리 회전을 사용하는 경우), 이를 시뮬레이션하기 위해 양자 컴퓨터가 필요하지 않습니다. 일반 컴퓨터가 똑같이 잘 그리고 똑같이 빠르게 그 일을 해낼 수 있습니다.

비유:
누군가가 제트기보다 더 빠르게 날 수 있는 "마법 비행 자동차"를 가지고 있다고 주장한다고 상상해 보세요. 하지만 물리학자가 그 자동차의 "마법" 부분이 바퀴가 정확히 100, 200, 300, 또는 400 RPM 으로 회전할 때만 작동한다는 것을 보여줍니다. 이를 깨닫게 되면, 컴퓨터로 그 정확한 속도를 완벽하게 시뮬레이션하는 일반 자동차를 만들 수 있습니다. 그 "마법" 자동차는 실제로 일반 자동차보다 빠르지 않습니다. 단지 우리가 이미 만드는 방법을 알고 있는 것의 화려한 버전일 뿐입니다.

간단히 말해: 이 특정 클래스의 양자 네트워크에 대해서는 "양자 우위" (양자 컴퓨터가 일반 컴퓨터가 할 수 없는 일을 할 수 있다는 아이디어) 가 사라집니다. 우리는 현재 컴퓨터에서 이를 효율적으로 시뮬레이션할 수 있습니다.

기술 요약

기술적 요약: 양자 신경망의 신경 접선 커널 효율적 고전 계산

문제 제기
본 논문은 무한 폭 (infinite width) 영역에서 양자 신경망 (QNN) 의 학습 역학을 특성화하는 계산 복잡성을 다룹니다. 최근 이론적 연구는 지도 학습 작업에서 훈련된 넓은 QNN 이 신경 접선 커널 (NTK) 에 의해 지배되는 가우시안 과정으로 수렴함이 입증되었으나, 일반적인 양자 회로에 대한 이 커널을 계산하려면 양자 시스템을 시뮬레이션해야 하므로 대규모 시스템의 경우 고전적으로 처리 불가능합니다. 저자들은 입력 인코딩에 클리포드 게이트를 사용하고 매개변수 진화에 파울리 군 (Pauli-group) 해밀토니안을 사용하는 특정하고 광범위한 QNN 클래스가 고전적 자원을 사용하여 NTK 를 효율적으로 추정할 수 있는지 조사합니다. 만약 이러한 추정이 가능하다면, 이러한 특정 넓은 QNN 은 고전 컴퓨터 대비 양자 우위를 달성할 수 없음을 의미합니다.

방법론
제안된 접근법은 QNN 아키텍처의 구조적 속성과 매개변수 공간의 특정 이산화 (discretization) 에 의존합니다:

1. 아키텍처 정의: 본 연구는 입력 $x$에 의존할 수 있는 임의의 클리포드 군 유니타리 연산자와 파울리 군에 속하는 해밀토니안 하의 시간 진동으로 생성된 매개변수 게이트가 교차하여 구성된 유니타리 연산자 $U_{x,\theta}$로 정의된 QNN 을 고려합니다. 모델 함수는 파울리 관측가능량 $O$의 기댓값입니다.
2. 매개변수 이산화 통찰: 핵심 방법론적 기여는 초기화 매개변수 $\theta \in [0, 2\pi)^L$의 균일 분포에 대한 경험적 NTK 의 기댓값으로 정의된 분석적 NTK 가 정확히 네 개의 값 $\{0, \pi/2, \pi, 3\pi/2\}$으로 구성된 이산 집합에 대한 기댓값으로 대체될 수 있다는 관찰입니다.
   • 이러한 특정 매개변수 값에서 매개변수 파울리 회전은 클리포드 연산이 됩니다.
   • 가정에 따라 비매개변수 게이트 또한 클리포드 연산이므로, 이러한 매개변수 선택에서 전체 회로 $U_{x,\theta}$는 클리포드 군에 속합니다.
   • 클리포드 게이트로만 구성된 회로는 고전 컴퓨터에서 효율적으로 시뮬레이션할 수 있습니다 (고트먼 - 클릴 정리).
3. 추정 알고리즘: 저자들은 매개변수를 이산 집합 $\{0, \pi/2, \pi, 3\pi/2\}^L$에서 $N$회 샘플링하는 고전 확률적 알고리즘 (알고리즘 1) 을 제안합니다. 각 샘플에 대해 모델 함수의 기울기는 유한 차분으로 축소되는 매개변수 이동 규칙 (parameter-shift rule) 을 사용하여 계산됩니다. NTK 는 이러한 기울기들의 외적 (outer products) 의 평균으로 추정됩니다.
4. 학습 역학으로의 확장: 넓은 훈련된 QNN 과 가우시안 과정 사이의 동등성을 활용하여, 저자들은 추정된 NTK 를 사용하여 훈련된 모델 함수 $\mu_\infty(x)$의 극한을 계산합니다 (알고리즘 2). 이는 훈련 데이터에 대한 추정된 NTK 행렬을 역행렬로 변환하고 이를 훈련 레이블에 적용하는 과정을 포함합니다.

주요 기여 및 결과
본 논문은 제안된 알고리즘의 샘플 및 계산 복잡성에 대한 엄격한 경계를 제공합니다:

• 편향 없는 추정: 저자들은 분석적 NTK 에 대한 추정량이 편향되지 않음을 증명합니다. 즉, 이산 집합에 대한 기댓값은 연속 균일 분포에 정의된 실제 NTK 와 일치합니다.
• NTK 를 위한 샘플 복잡성: 정밀도 $\epsilon$과 실패 확률 $\delta$로 NTK 항목 $K(x, x')$를 추정하기 위해 알고리즘은 $N = O(L^2 m^2 \epsilon^{-2} \log(1/\delta))$개의 샘플이 필요합니다. 여기서 $L$은 매개변수의 수이고 $m$은 관측가능량의 파울리 항 개수입니다.
• $\mu_\infty$를 위한 샘플 복잡성: 훈련된 네트워크의 평균 출력 $\mu_\infty(x)$를 정밀도 $\epsilon$으로 추정하기 위해 필요한 샘플 수는 훈련 예제 수 ($d_{train}$), 매개변수 수 ($L$), 그리고 관측가능량 복잡도 ($m$) 에 대해 다항식적으로 증가합니다. 구체적으로, 샘플 복잡성은 $d_{train}$과 $L$에 대해 다항식입니다.
• 계산 복잡성: 각 샘플에 대한 클리포드 회로의 고전 시뮬레이션은 매개변수 이동당 $O(L m n^2)$ 연산이 필요합니다. NTK 를 추정하기 위한 총 고전 복잡도는 $O(N L^2 m n^2)$입니다. $\mu_\infty$를 추정하는 경우, 복잡도에는 행렬 역행렬 계산이 포함되며 $O(N L^2 d_{train} (m n^2 + d_{train}^2))$로 증가합니다.
• 균일 수렴: 저자들은 전체 특징 공간 $X$에 걸쳐 균일하게 제한된 오차를 달성하기 위해 필요한 샘플 수가 $X$의 크기에 대해 로그적으로만 증가함을 보였습니다.

의의 및 주장
본 논문은 입력이 클리포드 게이트를 통해 인코딩되고 매개변수가 균일하게 초기화된 로그 깊이 (logarithmic depth) 의 넓은 양자 신경망은 지도 학습 작업에서 양자 우위를 달성할 수 없다고 결론지었습니다. 이는 그들의 학습 역학과 기대 출력이 고전 컴퓨터에 의해 효율적으로 시뮬레이션될 수 있기 때문입니다.

저자들은 그들의 결과가 특정 변분 양자 회로가 고전적으로 시뮬레이션 가능함을 보여주는 점점 늘어나는 문헌과 일치한다고 명시적으로 밝힙니다. 그들은 유도된 시간 복잡도 경계 (특히 $\mu_\infty$에 대한 최악의 경우 분석에서 $d_{train}^6$에 따른 스케일링) 가 비관적일 수 있으며 최적의 스케일링을 결정하기 위해 수치 실험이 필요하다고 인정합니다. 그러나 이러한 광범위한 네트워크 클래스에 대한 효율적인 고전 알고리즘의 이론적 존재는 QML 의 "양자 우위"가 클리포드 기반 입력 인코딩에 의존하지 않거나 다른 초기화 분포를 요구하는 아키텍처를 필요로 할 수 있음을 시사합니다.

마지막으로, 저자들은 제안된 알고리즘이 실제 양자 하드웨어 없이도 특징 맵을 생성하는 생성 메커니즘으로 양자 회로 구조를 효과적으로 사용하여 고전 기계 학습 작업을 위한 표현력 있는 커널을 합성하는 방법으로 활용될 수 있다고 제안합니다.