기술 요약: 양자 커널 밴딧 최적화에서의 표현력과 학습 가능성의 균형

1. 문제 정의

본 연구는 미지의 평균 보상 함수 $f^*$가 양자 커널 $\kappa_Q$에 의해 유도된 재생 커널 힐베르트 공간(RKHS) 내에 존재하는 가우시안 프로세스(GP) 밴딧 최적화의 과제를 다룹니다. 이 설정은 양자 제어, 상태 준비, 변분 양자 알고리즘(VQA)의 최적화와 같은 NISQ(Noisy Intermediate-Scale Quantum) 시대의 작업들을 배경으로 합니다.

이 프레임워크에서 학습자는 순차적으로 행동 $x_t$를 선택하고 노이즈가 포함된 보상 $y_t = f^*(x_t) + \eta_t$를 관찰합니다. 목표는 누적 후회(cumulative regret) $R_T$를 최소화하는 것입니다. 양자 커널은 이론적으로 고전적 커널(예: RBF)보다 뛰어날 수 있는 도메인 특화된 귀납적 편향(inductive bias)을 제공하지만, 저자들은 양자 밴딧 설정에서 실질적인 적용을 가로막는 두 가지 근본적인 장벽을 식별했습니다:

1. 지수적 정보 획득(Exponential Information Gain): $n$-큐비트 시스템에 대해, 최대 정보 획득 $\gamma_T$는 $O(4^n \log T)$로 스케일링됩니다. 이러한 지수적 스케일링은 지나치게 높은 누적 후회를 초래하며 모델의 학습 가능성을 저해합니다.
2. 커널 집중(Kernel Concentration): $n$이 증가함에 따라, 서로 다른 데이터 쌍에 대한 커널 값들이 고정된 값 주변으로 지수적으로 집중되어, 정확한 추정을 위해 지수적인 횟수의 양자 측정이 필요하게 됩니다.

본 논문은 고차원의 전체 양자 커널을 나이브하게 사용하는 것이 낮은 샘플 효율성과 계산적 불가능성을 초래하므로, 모델의 표현력과 학습 가능성 사이의 절충(trade-off)이 필요하다고 주장합니다.

2. 방법론

이러한 과제를 해결하기 위해, 저자들은 저차원 대리 모델(surrogate models)을 활용하는 근사 GP 밴딧 알고리즘 프레임워크를 제안합니다. 이 모델들은 축소된 양자 부분 공간(subspaces) 또는 고전적 근사법을 사용하여 전체 양자 RKHS를 근사하며, 이를 통해 **커널 미스스펙리피케이션(misspecification, 모델 오설정)**을 대가로 정보 획득을 줄입니다.

핵심 방법론은 세 가지 구체적인 근사 기법을 포함합니다:

A. 선형 투영 양자 커널 (Linear Projected Quantum Kernels, LPQKs)

이 접근 방식은 전역 $n$-큐비트 양자 상태를 크기가 $b < n$인 축소된 부분 시스템으로 투영합니다.

• 메커니즘: 전역 충실도(fidelity) 커널을 $|s| \leq b$인 부분 시스템 $s$에 대한 로컬 충실도 커널들의 합으로 근사합니다. 결과적으로 생성된 커널 $\kappa_{S_b}$는 전체 $4^n$ 차원보다 현저히 작은 $2^{|s|} \times 2^{|s|}$ 차원의 힐베르트 공간에서 작동합니다.
• 알고리즘: 미스스펙리파이드 밴딧을 위해 설계된 EC-GP-UCB(Enlarged Confidence GP-UCB) 알고리즘을 사용합니다. 이 알고리즘의 후회 경계(regret bound)는 축소된 정보 획득 $\gamma_T$ (최대 $b$까지의 파울리 가중치 성분의 수와 함께 스케일링됨)와 미스스펙리피케이션 오차 $\epsilon_b$ 사이의 균형을 명시적으로 조절합니다.

B. 랜덤 푸리에 특징 (Random Fourier Features, RFF)

이는 이동 불변(shift-invariant) 양자 커널의 푸리에 표현을 활용하는 완전한 고전적 근사 방법입니다.

• 메커니즘: 보크너 정리(Bochner's theorem)를 사용하여, 양자 커널을 차원이 $D$인 유한 차원 특징 맵 $\phi_{RFF}$로 근사합니다. 문제는 미스스펙리파이드 선형 밴딧 문제로 재구성됩니다.
• 알고리즘: SquareCB 알고리즘을 사용하며, 이는 특징 차원 $D$와 미스스펙리피케이션 오차 $\epsilon_D$에 의존하는 후회 경계를 달성합니다. 저자들은 후회 경계를 최소화하기 위해 $D \approx \sqrt{T}$를 선택하는 이론적 지침을 도출합니다.

C. P-Greedy 커널 근사

이 방법은 데이터 의존적 부분 집합 선택을 통해 저차원 부분 공간을 구축합니다.

• 메커니즘: 알고리즘은 현재의 부분 공간이 RKHS를 가장 악하게 근사하는 지점을 식별하기 위해 "파워 함수(power function)"를 최대화하는 점들을 반복적으로 선택합니다. 이는 커널의 저계수(low-rank) 근사를 위한 뉴턴 기저(Newton basis)를 생성합니다.
• 알고리즘: RFF와 유사하게, 이 방법은 문제를 타겟 커널의 스펙트럼 감쇠(Kolmogorov width)에 의해 결정되는 미스스펙리피케이션 오차를 가진 선형 밴딧 설정으로 축소합니다.

3. 주요 기여

이론적 기여

• 양자 특화 학습 가능성 장벽: 본 논문은 $n$-큐비트 수에 따른 최대 정보 획득의 지수적 스mathcaling을 충실도 양자 커널을 사용하는 GP 밴딧의 근본적인 통계적 장벽으로 규명했습니다.
• 미스스펙리파이드 양자 밴딧에 대한 후회 경계: 저자들은 근사 오차(미스스펙리피케이션)와 정보 획득 사이의 트레이드오프를 특징짓는 후회 경계를 도출했습니다. 고차원 커널이 과도하게 높은 경우, 적절히 선택된 근사 커널이 전체 모델보다 엄격하게 낮은 후회를 달성함을 입증했습니다.
• 구조적 분석: 분석은 회로 구조(예: 파울리 가중치 투영, 생성자 고유값 간격)를 정보 획득/미스스펙리피케이션 트레이드오프와 직접 연결합니다. 예를 들어, LPQK는 파울리 가중치 투영에 해당하며, 오차 경계는 타겟 관측량의 고가중 파울리 성분의 감쇠에 의존합니다.

알고리즘 및 실용적 기여

• 계산 효율성: 제안된 방법들은 GP 추론에 필요한 시간 복잡도를 $O(T^3)$에서 $O(TD^2 + D^3)$ 또는 $O(TD^2 + TD|A|)$로 줄입니다 (여기서 $D \ll T$는 근사 차원). 이는 양자 네이티브 애플리케이션을 위한 확장 가능한 최적화를 가능하게 합니다.
• 차원 선택 가이드라인: 이론적 경계는 모델 복잡도(예: LPQK에서 제거할 큐비트 수 또는 RFF에서 사용할 랜덤 특징의 수)를 선택하기 위한 원칙적인 지침을 제공합니다.

4. 실험 결과

저자들은 합성 및 실제 양자 작업을 통해 접근 방식을 검증했습니다:

1. 합성 양자 함수: 3-큐비트(및 6-큐비트로 확장) 양자 커널을 사용한 실험에서, 모델 복잡도에 따른 전형적인 "U자형" 후회 곡선을 보여주었습니다.

   • 낮은 복잡도는 언더피팅(높은 미스스펙리피케이션 오차)을 초래합니다.
   • 높은 복잡도는 오버피팅(높은 정보 획득 페널티)을 초래합니다.
   • 제안된 근사 커널(LPQK, RFF, P-greedy)은 차원이 이론적 예측에 따라 조정되었을 때, 전체 양자 커널보다 샘플 효율성 측면에서 일관되게 우수한 성능을 보였습니다.

2. 양자 위상 분류 (Quantum Phase Classification): 일반화된 클러스터 해밀토니안에서 페로마그네틱 상(ferromagnetic phase)에 해당하는 파라미터를 식별하는 작업에서, 근사 커널은 전체 커널보다 현저히 우수한 성능을 보였으며, 이는 저차원 커널이 전체 커널의 정보 획득 페널티 없이도 상을 구별하기에 충분함을 시사합니다.

3. 변분 양자 고유치 솔버 (VQE): XYZ 하이젠베르크 해밀토니안의 바닥 상태를 찾는 베이지안 최적화 작업에서, 더 단순한 근사 모델들이 전체 커널보다 더 빠르게 최소 에너지로 수렴했습니다. 전체 커널은 해당 작업에 대해 지나치게 복잡한 것으로 간주되었습니다.

5. 의의 및 주장

본 논문의 주요 의의는 양자 커널의 이론적 잠재력과 NISQ 시대의 실질적 한계 사이의 간극을 메우는 데 있습니다. 표현력(전체 양자 RKHS에 의해 포착됨)과 학습 가능성(정보 획득 및 계산 비용에 의해 제한됨) 사이의 트레이드오프를 공식화함으로써, 저자들은 확장 가능한 GP 최적화를 위한 프레임워크를 제공합니다.

본 연구의 주장은 다음과 같습니다:

• 전체 양자 커널은 정보 획득의 "차원의 저주"로 인해 밴딧 작업에 있어 종종 최적이 아닐 수 있습니다.
• 적절히 튜닝된 근사 양자 커널은 실질적으로 감소된 계산 오버헤드와 샘플 복잡성을 가지면서도 최적에 가까운 성능을 달성할 수 있습니다.
• 근사 오차에 대한 이론적 통찰은 실제 환경에서 모델 차원을 선택하는 데 도움을 주며, 이는 누적 후회 측면에서 "그라운드 트루스(ground truth)"인 전체 커널 접근법을 능가하는 성능을 낼 수 있습니다.

저자들은 자신의 후회 경계가 보수적일 수 있으며, 분석이 이상적인 노이즈 모델(i.i.d. 가우시안)을 가정하고 있는 반면 실제 NISQ 장치는 구조화된 노이즈를 보인다는 점을 언급하며 신중한 태도를 유지하고 있습니다. 또한, RFF 접근 방식은 모든 양자 회로에 적용 가능할 수 있는 트랙터블한 푸리에 전개의 존재를 전제로 합니다.