[논문 리뷰] Quantum Cluster Algorithm for Data classification

Intro

• 양자 알고리즘은 지수-스케일의 스피드업을 노릴 수 있는 퍼텐셜이 있음
• 그 활용 중 하나로 양자 머신러닝 알고리즘이 제시됨
• 최근에는 양자 머신러닝 알고리즘을 통해 6, 9 이미지를 QSVM으로 구분해내는 알고리즘을 개발하고 직접 시연하는데 성공함.
• 하지만 이런 알고리즘은 대부분 gradient에 크게 의존하는 구현
• 여기서는 Quantum nearest neighbor algorithm을 사용해서 gradient 없이 데이터를 분류해내는 방법에 대해서 설명함
• 'sublabel'을 활용해서 데이터의 분류를 도와줄 것이다. sublabel은 일종의 마이너 레이블로, 'subclass' 를 나타내는 요소로써 활용될 것이다.
• 알고리즘은 크게 2가지 작업으로 나뉠 수 있다.
  1) 어떻게 적절한 sublabel을 찾아낼 것인가?
  2) 찾아낸 sublabel로 어떻게 classification 양자 회로를 만들 것인가?

Algorithm Design

• 여기서는 sublabel을 Lloyd's algorithm을 활용해서 부여할 것이다.

  • Seth Lloyd가 아니다. K-means 자체는 이미 몇번을 반복해야 하는지에 대해서 NP-hard임이 증명되어 있지만, 그 반복수를 조금 줄이는 방법이 있다. 그것이 Lloyd's algorithm이다.

• 각 클러스터에 대해서 mean point가 하나씩 있다고 가정하자. 이때 각 데이터에 대한 트레이닝 벡터를 이 mean point에 하나씩 대응 시킨다.

• 하지만 로이드 알고리즘에서 나온 결과는 직접 우리 알고리즘에 적용하지는 못한다. Sublabel 중복이나 다음 iteration에서 새로 분포를 만들 수 있을 정도로 sublabel이 충분하지 않을 수도 있기 때문.

• 이 문제를 해결하기 위해서 여기서는 2개의 추가 알고리즘을 제시한다.
  1) 너무 많은 sublabel을 부여하는 것을 막아주는 알고리즘
  2) 각 sublabel 간 겹치는 부분이 없도록 해주는 알고리즘

• 다음과 같은 랜덤한 양자 상태가 있다고 하자.

  $|\psi \rangle = e^{i \alpha} [ cos(\theta / 2) |0 \rangle + sin(\theta /2)e^{-i\phi /2} |1\rangle ]$

  데이터가 $\bold{x_i} = (x_{1,i}, x_{2,i})$ 라고 표현될 때, $\theta, \phi$는 각각 다음과 같이 인코딩 된다.

  $\theta_i = {2\pi (x_{1,i} - min\{x_1\}) \over max\{x_1\} - min\{x_1\}}$
  $\phi_i = {2\pi (x_{2,i} - min\{x_2\}) \over max\{x_2\} - min\{x_2\}}$

  이때 여기서 $max\{x_1\}$는 모든 데이터들에 대해서 첫 번째 애트리뷰트만을 고려했을 때 그 중 최대값을 말한다.

  즉, 양자상태 $|\psi_i\rangle$가 갖고 있는 정보들은 $i$ 번째 데이터 포인트가 갖고 있는 2개의 애트리뷰트가 $\theta, \phi$에 각각 위 식대로 한번 가공해서 들어간 정보들이다.

• 이제 이렇게 구해진 $|\psi\rangle$ 여러 개에 대해서 거리를 구할 것이다. 당연하지만 inner product가 사용될 것이다.

• 데이터 인코딩에는 다음과 같은 회로가 사용될 것이다.

  $|\psi_i (\theta_1, \phi_1) \rangle= R_z(\phi_{1}/2)R_y(\theta_1)R_z(-\phi_1/2) |0\rangle$

  유니터리 행렬의 곱셈은 교환법칙이 성립하지 않는다. 따라서 '돌렸다가 다시 되돌리는 것' 같은 위 회로도 사실은 다시 되돌리는 것이 아니다.

• 이렇게 만든 $|\psi (\theta_1, \phi_1) \rangle$, $|\psi (\theta_2, \phi_2) \rangle$ 에 대해서 서로 inner product를 구하는 것이 전체 알고리즘의 중요한 서브 루틴 중 하나이다.

3 Algorithms

• S1: