Does Quantum Machine Learning Work?


Quantum Machine Learning has been discussed since HHL algorithm was introduced by Harrow in 2012 as an algorithm for solving linear system of equations, or, maybe much more earlier, since quantum neural network.

In machine learning, most of the operations involve in problem solving linear system of equations. In classical situation, we use parallel computing to accelerate this process. In quantum computing, HHL algorithm (HHL = Harrow+Hassidim+Lloyd) was the answer to this kind of problem. HHL algorithm solve this problem in \(O(\kappa^2\log{N})\), and was later improved to \(O(\kappa\log^3\kappa\log{N})\). Since we are able to solve linear system of equation problems on a quantum computer, algorithms based on HHL algorithm were developed, for example quantum support vector machine. Support vector machine (SVM) is a classical machine learning model in supervised machine learning that classifies vectors in a feature space into one of two sets, given training data from the sets. In 2014, researcher developed its quantum version, a quantum algorithm which can be performed on a quantum computer. This algorithm was later performed on a NMR quantum computing device in 2015 .

Given a linear system of equations \(\vec{A}\vec{x} = \vec{b}\), we represent \(\vec{b}\) as a quantum state \(|b\rangle = \sum_{i=1}^N b_i |i\rangle\). Next, we calculate the inversion of the matrix A through some quantum process if \(A\) is a Hermitian. Then the solution of this linear system is \(|x\rangle = A^{-1}|b\rangle\). When \(A\) is not a Hermitian, we can define