Title: Gaussian Kernel in Quantum Paradigm,
Abstract: 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)|.