Quantum Spectral Clustering Framework via Compact Circuit Structures

기술 요약: 컴팩트한 회로 구조를 통한 양자 스펙트럴 클러스터링 프레임워크

문제 정의
스펙트럴 그래프 이론에 기반을 둔 스펙트럴 머신 러닝 방법론은 클러스터링과 매니폴드 학습을 위한 강력한 도구이다. 그러나 이들의 실제 적용은 높은 계산 비용으로 인해 제약을 받는다. $M$개의 샘플에 대해 커널(인접) 행렬을 구축하는 데는 일반적으로 $O(M^2)$의 시간이 소요되며, 관련 고유값 문제를 정확하게 푸는 데는 $O(M^3)$의 비용이 든다. Nyström, Random Fourier Features, Lanczos와 같은 고전적 근사 방법들이 존재하지만, 이들은 여전히 부분 또는 전체 커널 행리에 대한 명시적인 접근을 필요로 하는 경우가 많다. 양자 머신 러닝의 맥락에서, 커널 엔트리가 직접 읽히는 대신 양자 서브루틴(예: SWAP test)을 통해 추정되는 경우, 엔트리별 접근 방식은 $O(\epsilon^{-2}M^4)$로 스케일링되어 매우 비효율적이 된다. 저자들은 커널 행렬을 구축하거나 개별 엔트리를 추정하지 않고도 효율적으로 스펙트럴 클러스터링을 수행할 수 있는 공백을 확인하였다.

방법론
본 논문은 커널 행렬 구축을 완전히 우회하는 변분적 스펙트럴 클러스터링 프레임워크를 제안한다. 대신, 집합적 이차 형식(aggregate quadratic forms)을 사용하여 컴팩트한 양자 회로를 통해 필요한 양들을 직접 추정한다.

1. 목적 함수: 저자들은 대칭 그래프 라플라시안($L_{sym}$)으로부터 유도된 정규화된 레일리 몫(Rayleigh-quotient) 목적 함수를 공식화한다. 목표는 다음을 최대화하는 것이다:
   $$J(\alpha) = \frac{\alpha^\dagger A \alpha - \xi \alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha}{\alpha^\dagger D \alpha}$$
   여기서 $A$는 인접 행렬, $D$는 차수(degree) 행렬, $\mathbf{1}$은 모든 성분이 1인 벡터이며, $\xi > 0$은 페널티 파라미터이다. 분자에는 자명한 고유벡터(상수 벡터)를 억제하여 비자명한 클러스터링 솔루션을 보장하기 위해 설계된 페널티 항이 포함되어 있다.

2. 양자 회로 설계: 이 프레임워크는 행렬을 구축하지 않고 목적 함수의 항들을 평가하기 위해 세 가지 특정 양자 추정기를 활용한다:

   • $q_a(\alpha)$: 인접 이차 형식($\alpha^\dagger A \alpha$)을 추정한다.
   • $q_d(\alpha)$: 차수 가중 이차 형식($\alpha^\dagger D \alpha$)을 추정한다.
   • $q_p(\alpha)$: 투영 페널티 항($\alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha$)을 추정한다.

   이 추정기들은 데이터 인덱싱 중첩 상태를 준비하는 데이터 임베딩 유니터리 $U_{\phi, D}$와 인덱스 레지스터 상의 학습 가능한 가중 상태 $|\alpha_\theta\rangle$에 의존한다. 회로는 상태 간의 충실도(fidelity, 유사도)를 계산하기 위해 SWAP-test 스타일의 서브루틴을 사용한다.

3. 추론 (테스트): 관찰되지 않은 데이터 포인트 $\hat{x}$에 대해, 테스트 상태와 학습된 가중 상태 사이의 오버랩 위상(phase)을 기반으로 점수 함수가 정의된다. 위상 $\hat{\phi}(\hat{x}, \hat{\alpha})$는 간섭 회로(보조 큐비트를 $\sigma_x$ 및 $\sigma_y$ 기저에서 측정)를 통해 추출되며, 임계값 설정 또는 원형 클러스터링을 통해 클러스터 레이블을 할당하는 데 사용된다.

4. 학습 워크플로우: 가중 상태 $|\alpha_\theta\rangle$의 파라미터는 양자 추정기에 의해 유도되는 클래식 최적화 도구(경사 하강법)를 사용하여 최적화된다. 그래디언트는 파라미터 시프트 규칙(parameter-shift rule)을 사용하여 계산된다.

주요 기여

• 컴팩트한 회로 구조: 저자들은 목적 함수의 구성 요소들을 직접 추정하는 일련의 양자 회로를 제시한다. 이 접근 방식은 커널 행렬을 구축하거나 개별 커널 엔트리를 추정하는 번거로움을 피하며, 이는 양자 환경에서 다른 양자 스펙트럴 방법들의 병목 현상이 된다.
• 엄밀한 샷 복잡도 분석: 이론적 분석을 통해 페널티 항($q_p$)의 샘플링 복잡도가 다룰 수 있는 수준임을 입증하였다. 페널티 항의 크기가 작아 더 많은 샷이 필요할 것이라는 직관과 달리, 저자들은 집중 부등식(concentration inequalities)을 사용하여 필요한 샷 수가 실패 확률에 대해 최대 준다항식(quasi-polynomially)으로 증가함을 증명하였다. 이는 페널티 추정기가 전체 샘플링 예산을 지배하지 않음을 검증한다.
• 통합된 학습-테스트 워크플로우: 본 프레임워크는 변분 최적화부터 위상 기반 점수 메커니즘을 이용한 미관측 데이터에 대한 추론까지 완전한 파이프라인을 제공한다.

결과
저자들은 표준 데이터셋에 대한 무잡음 양자 시뮬레이션을 통해 프레임워크를 검증하였다:

• 데이터셋: Iris 데이터셋(Setosa 대 Versicolor/Virginica의 이진 클러스터링) 및 MNIST 데이터셋(PCA를 통해 4차원으로 축소된 숫자 '0'과 '1'의 이진 클러스터링).
• 성능:
  • Iris: 상대적으로 얕은 회로(4개 레이어, 24개 파라미터)를 사용하여 모델은 98.7%의 평균 테스트 정확도를 달성했다. 레이어를 6개 이상으로 늘리면 정확도가 99.8% 이상에서 안정화되었다.
  • MNIST: 6개 레이어부터 신뢰할 수 있는 성능이 나타나기 시작했으며, 8개 이상의 레이어에서 평균 97.2%의 정확도로 안정화되었다.
• 유한 샷 동작(Finite-Shot Behavior): 시뮬레이션은 페널티 추정기가 예측대로 동작함을 확인시켜 주었다. 페널티 항의 표본 평균은 빠르게 0으로 수렴하였고, 그에 따라 분산도 수축하였다. 결정적으로, 페널티 항은 이론적 분석과 일치하게 다른 항들보다 현저히 큰 샘플링 예산을 요구하지 않고도(예: 256–1024 샷) 안정적으로 추정될 수 있었다.

의의 및 주장
본 논문은 얕고 하드웨어 효율적인 양자 회로와 호환되는 스펙트럴 클러스터링 프레임워크의 "개념 증명(proof of concept)"으로 이 연구를 포지셔닝한다. 주요 의의는 다음과 같다:

1. 커널 행렬 병목 현상 회피: 집합적 이차 형식을 연산함으로써, 양자 환경에서 엔트리별 커널 추정에 따르는 $O(M^2)$ 또는 $O(M^4)$ 비용을 피한다.
2. 스케일 불일치 완화: 엄밀한 분석을 통해, 수치적 불안정성이나 높은 샘플링 비용의 원인이 될 수 있는 페널티 항을 효율적으로 추정할 수 있음을 보여줌으로써 변분 목적 함수를 실용적으로 만든다.
3. 비지도 학습 맥락: 저자들은 양자 커널 방법이 지도 학습에서는 잘 연구되어 있지만, 비지도 학습인 스펙트럴 클러스터링에 대한 적용은 덜 탐구되었음을 언급한다. 본 연구는 스펙트럴 그래프 이론과 이 특정 영역에서의 변분 양자 알고리즘을 연결한다.

저자들은 일반적인 과업에 대해 양자 충실도 커널이 고전적 커널보다 양자 우위를 제공하는지에 대해서는 다루지 않으며, 이에 대해 겸허한 입장을 유지한다. 대신, 이 연구의 초점은 양자 커널이 선택된 유사도 척도라고 가정할 때, 이를 효율적으로 구현하는 데 있다. 또한 향후 연구에서 이러한 페널티 분석 접근법을 페널티 항이 포함된 다른 변분 알고리즘(예: QUBO 문제)으로 확장하고, 비지도 학습 환경에서의 양자 인코딩에 대한 이론적 특성을 추가로 조사할 수 있음을 시사한다.