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

Abstract

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. Hence, this work implies that their feature map and quantum kernel, respectively, can be designed to have a quantum advantage for any classification problem that cannot be classically solved in polynomial time but contrariwise by a quantum computer.

6 pages, 2 figures

References in corpus (2)

• The theory of the quantum kernel-based binary classifier
• Quantum Gaussian process model of potential energy surface for a polyatomic molecule

Cited by in corpus (17)

• Barren Plateaus in Variational Quantum Computing
• QML-IDS: Quantum Machine Learning Intrusion Detection System
• Quantum Neural Estimation of Entropies
• Automatic and effective discovery of quantum kernels
• Quantum Extreme Learning of molecular potential energy surfaces and force fields
• Digital-analog quantum convolutional neural networks for image classification
• Measurement-based quantum machine learning
• Learning Fourier series with parametrized quantum circuits
• Lean classical-quantum hybrid neural network model for image classification
• High-Accuracy Temporal Prediction via Experimental Quantum Reservoir Computing in Correlated Spins
• Benchmarking of quantum fidelity kernels for Gaussian process regression
• Resource-efficient quantum algorithm for linear systems of equations
• Global optimization in variational quantum algorithms via dynamic tunneling method
• Superior resilience to poisoning and amenability to unlearning in quantum machine learning
• Quantum feature-map learning with reduced resource overhead
• LArTPC hit-based topology classification with quantum machine learning and symmetry
• Performance Guarantees for Quantum Neural Estimation of Entropies