Quantum support vector machine for big data classification

1. 개요

SVM에서 Loss function을 최소화 시키는 문제를 풀기 위해서는 다음과 같은 라그랑주 함수를 최소화 시키는 $\vec{\alpha}$를 알아내야 한다.

이상의 문제를 양자 알고리즘을 활용해 $O(log(M))$ 수준의 성능 향상을 얻는 것을 목표로 한다.

2. 단편 지식 모음

• 커널 행렬 $K$가 중요한 역할을 한다. $K$는 다음과 같이 정의된다.
  $K_{jk}=k(\vec{x_j},\,\vec{x_k})=\vec{x_j}\,\cdot\,\vec{x_k}$
• 위에서 정의한 dual problem을 해결하는데는 가능한 모든 벡터에 대해서 dot product를 진행할 것이며, 총 $M(M-1)/2$ 번의 연산을 하게 된다.
• 최종적으로 얻어지는 결과는 다음과 같을 것이다. 오로지 1인가 -1인가만 관심이 있기 때문에 sign만 얻는다.
  $y(\vec{x})=sign\left(\sum^M_{j=1}\alpha_jk(\vec{x_j}\,\vec{x})+b\right)$
• 먼저 $K$를 Hamiltonian 형태로 쓰기 위해 다음을 구할 것이다.
  $\frac{K}{trK}$
  양자 오라클을 사용해서 다음과 같은 중첩상태를 만든다.
  $\frac{1}{\sqrt{N_{\mathcal{X}}}}\sum^M_{i=1}\left|\vec{x_i}\right|\left|i\right>\left|\vec{x_i}\right>$
  여기서 만약 training data register $\left|\vec{x_i}\right>$를 갖다 버린다면, 우리가 원하는 $\frac{K}{trK}$를 얻을 수 있을 것이다. 이를 수행하는 방법은 2번 레지스터에 대한 partial trace가 된다.
  $tr_{2}\{\left|\mathcal{X}\right>\left<\mathcal{X}\right|\}=\frac{1}{N_{\mathcal{X}}}\sum^M_{i,j=1}\left<\vec{x_j}|\vec{x_i}\right>|\vec{x_i}||\vec{x_j}|\left|i\right>\left<j\right|=\frac{K}{trK}$