Gaussian Kernel in Quantum Paradigm

The Gaussian kernel is a very popular kernel function used in many machine-learning algorithms, especially in support vector machines (SVM). For nonlinear training instances in machine learning, it often outperforms polynomial kernels in model accuracy. We use Gaussian kernel profoundly in formulating nonlinear classical SVM. In the recent research, P. Rebentrost et.al. discuss a very elegant quantum version of least square support vector machine using the quantum version of polynomial kernel, which is exponentially faster than the classical counterparts. In this paper, we have demonstrated a quantum version of the Gaussian kernel and analyzed its complexity in the context of quantum SVM. Our analysis shows that the computational complexity of the quantum Gaussian kernel is O(\epsilon^(-1)logN) with N-dimensional instances and \epsilon with a Taylor remainder error term |R_m (\epsilon^(-1) logN)|.