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

Understand

Machine learning is considered to be one of the most promising applications of quantum computing.

• Therefore, the search for quantum advantage of the quantum analogues of machine learning models is a key research goal.
• Here, we show that variational quantum classifiers and support vector machines with quantum kernels can solve a classification problem based on the $k$-Forrelation problem, which is known to be PromiseBQP-complete.
• Because the PromiseBQP complexity class includes all Bounded-Error Quantum Polynomial-Time (BQP) decision problems, our results imply that there exists a feature map and a quantum kernel that make variational quantum classifiers and quantum kernel support vector machines efficient solvers for any BQP problem.