Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines

Abstract

Rigorous results about the real computational advantages of quantum machine learning are few. Here, the authors prove that a PROMISEBQP-complete problem can be expressed by variational quantum classifiers and quantum support vector machines, meaning that a quantum advantage can be achieved for all ML classification problems that cannot be classically solved in polynomial time.