기술 요약: 단일 양자 회로를 이용한 다중 클래스 양자 k-최근접 이웃 분류

1. 문제 정의

본 논문은 가상의 프리미티브(primitive)에 의존하지 않고 다중 클래스 $k$-최근접 이웃(kNN) 분류기를 양자 하드웨어에 구현하는 과제를 다룹니다. 기존의 양자 kNN(qkNN) 제안들은 다음과 같은 요소들에 의존하는 경우가 많습니다:

• 양자 랜덤 액세스 메모리(QRAM) 또는 데이터 로딩을 위한 오라클 접근 방식: 이는 현재 규모 있게 물리적으로 구현되지 않은 기술입니다.
• 제한적인 거리 메트릭(예: 해밍 또는 극좌표 메트릭): 이는 이산화를 요구하거나 크기 정보를 손실합니다.
• 이진 분류의 한계 또는 클래스 레이블을 결정하기 위해 클래식 사후 처리가 필요한 아키텍처.
• 쌍별 평가(Pairwise evaluation): 모든 훈련 포인트에 대해 별도의 회로를 실행해야 하므로 자원 오버헤드가 높습니다.

저자들은 QRAM이나 오라클 가정을 피하면서, 모든 클래스의 모든 구성원을 동시에 쿼리와 비교하고, 가장 광범위하게 적용 가능한 유클리드 거리를 사용하며, 측정 통계로부터 클래스 레이블을 직접 출력하는 단일 회로 아키텍처를 설계하는 것을 목표로 합니다.

2. 방법론

2.1 전처리: 역 역투영 (Inverse Stereographic Projection, ISP)

클래식 유클리드 데이터($\mathbb{R}^d$)를 양자 상태 공간(단위 초구 $S^d \subset \mathbb{R}^{d+1}$)으로 매핑하기 위해 저자들은 역 투영(ISP)을 채택합니다.

• 매핑: 벡터 $z$는 $\Phi(z) = \frac{1}{1+\|z\|^2}(2z_1, \dots, 2z_d, 1-\|z\|^2)$로 매핑됩니다.
• 노름 보존(Norm Preservation): 표준 정규화($z \to z/\|z\|$)와 달리, ISP는 입력 벡터의 크기를 마지막 좌표에 보존하여 정보 손실을 방지합니다.
• 거리 변환: 논문은 구면 상의 현의 거리(chordal distance)에 대한 폐쇄형 식을 도출합니다. 이 매핑이 비선형임에도 불구하고, 최근접 이웃 순위가 유계된 왜곡 계수 $\sqrt{\alpha}$ (여기서 $\alpha = 1+R^2$ 이고 $R$은 데이터 진폭 상한) 내에서 보존됨을 증명합니다.
• 스케일 선택: 저자들은 데이터 스케일링을 $R=1$ (입력이 $\|z\| \in [0,1]$ 범위에 있도록 스케일링)로 선택합니다. 이는 순위 충실도(왜곡 최소화)와 SWAP 테스트의 통계적 해상도(측정에 충분한 각도 분리 확보) 사이의 균형을 맞춥니다.

2.2 양자 인코딩

• 밀집 각도 인코딩(Dense Angle Encoding): 투영된 좌표들은 밀집 각도 인코딩을 통해 큐비트에 인코딩됩니다. 좌표 쌍 $(a_k, b_k)$는 단일 큐비트 상태 $|q_k\rangle = \cos(\theta_k/2)|0\rangle + e^{i\phi_k}\sin(\theta_k/2)|1\rangle$로 매핑됩니다.
• 큐비트 효율성: 각 데이터 포인트는 $n_q = \lceil(d+1)/2\rceil$개의 큐비트를 점유하며, 이는 표준적인 좌표당 큐비트 인코딩보다 약 절반의 너비만 필요로 합니다.

2.3 회로 아키텍처: 단일 회로 다중 클래스 비교

핵심 혁신은 "클래스 중첩 인코딩"과 제어된-SWAP(CSWAP) 게이트의 버터플라이 네트워크입니다.

• 클래스 중첩 상태: 각 클래스 $k$에 대해, 훈련 구성원들은 중첩 상태로 전용 레지스터에 로드됩니다: $|C_k\rangle = \frac{1}{\sqrt{2^m}}\sum_{j=0}^{2^m-1} |\phi^{(k)}_j\rangle|j\rangle$, 여기서 $|j\rangle$는 구성원 인덱스입니다.
• 버터플라이 네트워크: $\lceil \log_2 l \rceil$ 단계의 CSWAP 스테이지(여기서 $l$은 클래스 수)를 가진 네트워크가 클래스 레지스터를 라우팅합니다. 단일 실행 중에 쿼리는 모든 $l \times 2^m$개의 훈련 포인트와 동시에 비교됩니다.
• SWAP 테스트: 라우팅된 클래스 레지스터와 쿼리 레지스터 사이의 최종 SWAP 테스트는 충실도(fidelity, 유사도)를 추정합니다.
• 측정 및 판독: 회로는 보조 큐비트(ancillary qubits)와 구성원 인덱스 큐비트를 측정합니다. 특정 결과 $(j, k)$와 함께 최종 보조 큐비트가 상태 $|1\rangle$인 상태를 측정할 확률은 쿼리와 클래스 $k$의 $j$번째 구성원 사이의 충실도에 반비례합니다.
• 분류: 가장 낮은 확률(가장 높은 충실도)을 가진 $K$개의 결과를 선택합니다. 예측된 레이블은 이 $K$개 결과의 클래스 인덱스들에 대한 다수결 투표에 의해 결정됩니다. 클래스를 식별하기 위해 인덱스의 클래식 사후 처리가 필요하지 않습니다; 클래스는 측정 통계에 인코딩되어 있습니다.

3. 주요 기여

1. 클래스 중첩 인코딩: 각 클래스의 구성원을 중첩 상태로 로드하는 방법으로, 이를 통해 단일 회로 실행으로 모든 클래스의 모든 훈련 데이터와 비교할 수 있습니다. 클래스 정체성은 측정 통계로부터 직접 읽힙니다.
2. 분석적 기초: 회로의 사후 선택된 측정 확률에 대한 폐쇄형 식을 제공합니다. 저자들은 이 회로가 무한 샷(infinite-shot) 한계에서 의도한 결정 규칙을 정확하게 구현함을 증명합니다.
3. 기하학적 분석: ISP가 유클리드 최근접 이웃 순위를 유지하며 날카로운 왜곡 경계($R=1$에서 $\sqrt{2}$)를 가진다는 엄격한 분석을 수행합니다. 이는 투영이 분류 정확도를 저하시지 않음을 입증합니다.
4. 자원 효율적 아키텍처: QRAM이나 오라클을 필요로 하지 않는 설계입니다. 회로 너비는 클래스 수에 선형적이고, 클래스당 구성원 수에는 로그형입니다. 깊이는 클래스 수에 선형적입니다.
5. 포괄적 벤치마킹: 공통의 가우시안 벤치마크를 사용하여 여러 양자 kNN 결정 규칙을 공정하게 비교함으로써, 하드웨어 노이즈 및 샷 노이즈로부터 인코딩 및 거리 메트릭의 영향을 분리해 냈습니다.

4. 결과

• 정확도 보존: 네 개의 클래스를 가진 가우시안 벤치마크($d=3$, 클러스터 확산도 변화)에 대한 시뮬레이션 결과, ISP 기반의 충실도 순위는 모든 분리 수준에서 클래식 유클리드 kNN 정확도와 1 퍼센트 포인트 이내의 차이를 보였습니다.
• 회로 정확성: 29-큐비트 회로가 이론적 결정 규칙과 동일한 예측을 생성함을 확인했습니다(320/320 테스트 포인트 일치).
• 유한 샷 성능: 현실적인 샷 예산($2.62 \times 10^5$)에서, 회로는 클래식 베이스라인과 80개 테스트 샘플 중 5개 이내의 차이(약 6.25%)로 추적되었으며, 이러한 불일치는 경계 사례에서의 샷 노이즈에 기인합니다.
• 이전 연구와의 비교:
  • 진폭 인코딩(Amplitude Encoding): 진폭 충실도에 의존하는 방법들(예: Basheer 등)은 노름 정보가 있는 데이터에서 5~12 퍼센트 포인트 낮은 성능을 보였는데, 이는 표준 진폭 인코딩이 크기 정보를 버리기 때문입니다.
  • QRAM 가정: 물리적 메모리 요구량을 계산할 때, 저자들의 방법(벤치마크에 29 큐비트 필요)은 32개 이상의 포인트를 가진 훈련 세트에 대해 QRAM 기반 방법보다 적은 자원을 필요로 합니다. QRAM 방법은 "큐비트" 추정치에 포함되지 않는 $\Theta(N)$개의 메모리 셀을 암묵적으로 요구하기 때문입니다.
  • 이진 vs 다중 클래스: 제안된 방법은 성공적으로 다중 클래스 문제를 처리하지만, 일부 이전의 간섭 기반 방법들은 본질적으로 이진 분류에 국한됩니다.

5. 의의 및 주장

본 논문은 점근적 속도 향상보다는 구조적 발전을 주장합니다. 그 의의는 다음과 같습니다:

• 가설적 프리미티브 제거: QRAM이나 오라클 없이 작동하는 다중 클래스 kNN 분류기를 보여주며, 구현 가능한 게이트(Hadamard 및 CSWAP)만을 사용합니다.
• 단일 회로 효율성: $N$번의 개별 쌍별 비교를 하나의 더 넓은 회로로 대체하여, 한 번의 측정으로 모든 이웃 클래스를 노출합니다.
• 정확도 동등성: ISP 기반의 기하학적 변환과 양자 인코딩이 성능을 본질적으로 저하시지 않음을 입증함으로써 클래식 유클리드 kNN과 대등한 정확도를 달성했습니다.
• 비용의 투명성: 저자들은 병목 현상이 여전히 상태 준비(데이터 로딩)에 있으며, 이는 QRAM이 없는 경우 $\Omega(N)$임을 명시적으로 밝힙니다. 그들은 이 아키텍처가 모듈식이라고 주장합니다. 즉, 지배적인 비용을 줄이기 위해 변분 로더(variational loader)와 같은 미래의 상태 준비 개선 사항을 비교 네트워크를 변경하지 않고도 통합할 수 있습니다.

저자들은 이 아키텍처가 모든 양자 분류기에 공통적인 효율적인 상태 준비의 과제를 남겨두고 있음에도 불구하고, 클래식 정확도에 부합하는 QRAM-free 다중 클래스 분류를 위한 실용적인 프레임워크를 제공함으로써 분야를 발전시킨다고 결론짓습니다.