기술 요약: AQKA: 샷 예산 하의 능동 양자 커널 획득

1. 문제 제기

고전적 입력을 양자 특징 공간으로 매핑하여 충실도 $K(x_i, x_j) = |\langle \phi(x_j)|\phi(x_i)\rangle|^2$를 계산하는 양자 커널 방법은 잡음 중간 규모 양자 (NISQ) 하드웨어에서 가장 접근하기 쉬운 작업 부하 중 하나입니다. 그러나 실제 배포는 측정 비용에 의해 병목 현상을 겪습니다. $N \times N$ 커널 행렬을 추정하는 데는 원하는 정밀도를 달성하기 위한 각 항목당 샷 수 $S$를 곱한 $\Theta(N^2 S)$만큼의 회로 실행 (샷) 이 필요합니다. 현재 하드웨어에서는 회로 지연 시간이 수 밀리초에서 수 초까지 다양하므로, 이러한 확장성은 배포 가능한 문제 크기를 수백 수준으로 제한합니다.

기존 예산 절감 전략 (예: Nyström-QKE, ShoFaR, 커널-타겟 정렬) 은 측정할 어떤 항목을 하위 표본 추출하는 방식으로 이 문제를 해결합니다 (예: 랜드마크 열 또는 훈련 포인트 선택). 그러나 이러한 방법들은 일반적으로 선택된 하위 집합 내에서 샷 예산을 균일하게 할당합니다. 이는 각 특정 커널 항목이 하류 분류기 성능에 기여하는 정도가 이질적이라는 점을 고려하지 못합니다. 핵심적으로 해결되지 않은 질문은 다음과 같습니다: 고정된 샷 예산 $B$가 주어졌을 때, 하류 작업의 손실을 최소화하기 위해 샷을 쌍 (pair) 수준에서 어떻게 할당해야 하는가?

2. 방법론: AQKA

저자들은 총 샷 예산 제약 $\sum s_{ij} \leq B$ 하에서 기대 손실 $\mathbb{E}[L(\hat{K})]$을 최소화하는 문제로 샷 예산이 할당된 양자 커널 학습을 공식화했습니다.

이론적 유도

1 차 분석 (델타 방법) 과 Karush-Kuhn-Tucker (KKT) 조건을 결합하여, 저자들은 폐쇄형 최적 할당 규칙을 유도했습니다. $s_{ij}$개의 샷으로 추정된 커널 항목 $K_{ij}$의 분산은 $K_{ij}(1-K_{ij})/s_{ij}$입니다. 손실 추정기의 분산을 최소화하는 최적 할당 $s^*_{ij}$는 해당 항목에 대한 손실의 민감도에 비례합니다:
$$s^*_{ij} \propto |g_{ij}| \sqrt{K_{ij}(1-K_{ij})}$$
여기서 $g_{ij} = \partial L / \partial K_{ij}$는 커널 항목에 대한 손실의 기울기입니다.

• 커널 릿지 회귀 (KRR) 의 경우: 기울기는 명시적으로 $g_{ij} = -2\lambda^2(\beta_i \alpha_j + \beta_j \alpha_i)$로 유도되며, 여기서 $\alpha = (K+\lambda I)^{-1}y$이고 $\beta = (K+\lambda I)^{-1}\alpha$입니다.
• 서포트 벡터 머신 (SVM) 의 경우: 포락선 정리 (Danskin's theorem) 를 사용하여 기울기는 $g_{ij} = -y_i y_j \eta^*_i \eta^*_j$로 유도되며, 여기서 $\eta^*$는 최적 이중 변수입니다.

알고리즘적 구현

저자들은 라운드 단위로 작동하는 배포 가능한 알고리즘인 **AQKA(능동 양자 커널 획득)**를 제안합니다:

1. 워밍업: 예산의 작은 비율 ($\eta_w B$) 을 균일하게 사용하여 초기 커널 추정치 $\hat{K}$를 시드합니다.
2. 민감도 추정: 알고리즘은 $\hat{K}$에서 KRR(또는 SVM) 문제를 풀어 기울기 기반 민감도 점수 $g_{ij}$를 계산합니다.
3. 타겟-필 할당: 다항 분포에서 샷을 샘플링하는 것 (확률적 스파이크로 인해 민감도가 낮은 쌍이 고갈될 수 있음) 대신, AQKA 는 결정론적인 "타겟-필" 접근 방식을 사용합니다. 이는 목표 샷 수 $s^*_{ij}$를 계산하고 각 쌍에 차이 $\max(0, s^*_{ij} - s_{ij})$를 추가합니다.
4. 탐색: 알고리즘이 2 차 효과나 추정 노이즈로 인해 중요해질 수 있는 쌍을 완전히 무시하는 것을 방지하기 위해 균일하게 작은 탐색 비율 ($\eta_e B$) 을 추가합니다.

3. 주요 기여

1. 완전한 영역 분해

이 논문은 다양한 할당 전략이 최적인 시기에 대한 원칙적인 특징을 제공합니다:

• AQKA는 희소 민감도 KRR 작업에서 예산 제한 영역($B \lesssim 16 n_{pairs}$) 에서 우세합니다.
• Nyström-QKE(저차원 재구성) 는 저차원 구조가 완전히 복원될 수 있는 식재된 희소 데이터에서 포화 예산 시점에 승리합니다.
• ShoFaR 스타일 방법은 극단적으로 낮은 예산 영역에서만 경쟁력이 있습니다.

2. 폐쇄형 쌍 수준 획득 이론

• KKT 최적 할당: 샷 노이즈 하에서 KRR 및 SVM 에 대한 폐쇄형 기울기 $g_{ij}$ 유도.
• 수정된 희소성 인식 경계: 저자들은 달성 가능한 분산 감소 비율 $\rho$에 대한 코시 - 슈바르츠 경계를 유도했습니다. $g$가 $S \times S$에서 지원된다고 가정하는 단순한 $\Theta(m^2/N^2)$ 스케일링을 더 정확한 $\Theta(m/N)$ 스케일링 ($\rho \leq 2m/N$ for KRR) 으로 수정했습니다. 이는 해 벡터 $\alpha$가 희소하더라도 민감도 벡터 $\beta = (K+\lambda I)^{-1}\alpha$는 일반적으로 밀집되어 있어, 지원 집합과 접촉하는 모든 쌍이 0 이 아닌 민감도를 가진다는 구조적 사실을 반영합니다.
• 후회 경계: 명시적 상수 플러그인 후회 경계가 제공되어, 워밍업 예산이 증가함에 따라 오차가 오라클 최적값으로 수렴함을 보여줍니다.

3. 배포 가능한 타겟-필 알고리즘

이 논문은 결정론적 타겟-필 방식이 특히 예산 제한 영역에서 자연스러운 다항 샘플링을 능가함을 입증했습니다. 다항 샘플링은 소수의 고득점 쌍에 집중적으로 집중하여 다른 쌍을 고갈시키고 행렬 역연산에서 노이즈를 증폭시키는 경향이 있는 반면, 타겟-필은 최소 커버리지 바닥을 유지합니다.

4. 양자 하드웨어에서의 첫 번째 멀티-시드 실시간 온라인 적응

저자들은 현재 156 큐비트 IBM Heron 급 장치에서 온라인 적응형 샷 할당의 첫 번째 공개된 실증 보고를 제시했습니다.

• IBM Aachen (N=20): 균일 할당 대비 +17.0 ± 4.8 퍼센트 포인트 (3.5$\sigma$ 유의성).
• IBM Berlin (N=30): 더 높은 예산에서 +14.0 ± 8.5 퍼센트 포인트.

4. 실험 결과

합성 및 시뮬레이션 설정

• 식재된 희소 KRR: 희소 해 벡터를 가진 합성 데이터에서, AQKA(추정된 민감도를 사용한 타겟-필) 는 $N$이 225 에서 1000 으로 확장됨에 따라 균일 할당 대비 +8 에서 +25 퍼센트 포인트를 달성합니다.
• 무잡음 양자 커널: 이 이득은 무잡음 4 큐비트 ZZFeatureMap 시뮬레이션으로 이전되어 균일 대비 +13 에서 +18 포인트를 보여줍니다.
• 하드웨어 리샘플링 제거 분석: IBM Pittsburgh(156 큐비트) 에서 측정된 커널을 사용하여 샷 노이즈로 리샘플링한 결과, AQKA 는 $B = n_{pairs}$에서 균일 대비 +26.3 ± 6.1 포인트, $B = 4n_{pairs}$에서 +31.9 ± 7.2 포인트를 달성했습니다.

실데이터 벤치마크

• 유방암 (밀집 $\alpha$): 해 벡터가 희소가 아닌 밀집된 실세계 데이터셋에서 AQKA 는 균일하게 우세하지 않습니다. 경쟁력 있지만 영역에 따른 성능을 보여주며, 이 방법의 이점이 높은 쌍 수준 민감도 이질성에 의존함을 강조합니다.
• SVM 대 KRR: 논문은 이론적 프레임워크가 SVM 으로 확장되지만, 노이즈가 있는 워밍업 하에서 지원 집합의 불안정성으로 인해 플러그인 버전이 더 취약하다고 지적합니다. 작은 N, 노이즈가 있는 워밍업 영역에서 SVM 용 AQKA 는 균일 할당보다 성능이 떨어질 수 있는 반면, KRR 버전은 견고하게 유지됩니다.

5. 중요성 및 주장

이 논문은 이론적 샷 예산 최적화와 NISQ 하드웨어의 실제 배포 간의 격차를 해소했다고 주장합니다. 주요 중요성은 다음과 같습니다:

1. 균일 할당을 넘어선 이동: 예산이 빡빡할 때 특히 근미래 양자 커널 학습을 위해 비균일, 민감도 인식 샷 할당이 중요함을 입증.
2. 하드웨어 검증: 실제 양자 하드웨어에서 적응형 샷 할당 전략에 대한 첫 번째 멀티-시드, 실시간 온라인 검증을 제공하여 이론적 이득이 장치 노이즈 및 보정 드리프트를 견딘다는 것을 증명.
3. 영역 인식: 단일 방법이 보편적으로 우월하지 않음을 확립; AQKA 는 현재 하드웨어의 운영상 관련 영역인 예산 제한, 희소 민감도 영역을 위해 특별히 설계됨.

저자들은 주장에 있어 겸손하며, 밀집 민감도 문제나 포화 예산의 경우 Nyström 과 같은 다른 방법이나 균일 할당이 더 선호될 수 있음을 인정합니다. 또한 SVM 플러그인 노이즈를 현재 한계로 식별하여 향후 작업 (예: 마진 안정화 획득) 이 필요하다고 지적합니다.