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

arXiv: https://arxiv.org/abs/2207.05865 · HTML: https://mlsanity.com/paper/2207.05865/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 31 references that are in the map.
- First posted on arXiv 12 Jul 2022.

## Builds on (most cited first, 7 of 7)

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Quantum machine learning of large datasets using randomized measurements](https://mlsanity.com/paper/2108.01039/) (2021)
- [Experimental kernel-based quantum machine learning in finite feature space](https://mlsanity.com/paper/1906.04137/) (2019)
- [Practical application improvement to Quantum SVM: theory to practice](https://mlsanity.com/paper/2012.07725/) (2020)

## Built on by (most cited first, 28 of 28)

- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [QKSAN: A Quantum Kernel Self-Attention Network](https://mlsanity.com/paper/2308.13422/) (2023)
- [A Unified Framework for Trace-induced Quantum Kernels](https://mlsanity.com/paper/2311.13552/) (2023)
- [Quantum Kernel-Based Long Short-term Memory](https://mlsanity.com/paper/2411.13225/) (2024)
- [Automatic and effective discovery of quantum kernels](https://mlsanity.com/paper/2209.11144/) (2022)
- [Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits](https://mlsanity.com/paper/2310.07528/) (2023)
- [A kernel-based quantum random forest for improved classification](https://mlsanity.com/paper/2210.02355/) (2022)
- [Neural auto-designer for enhanced quantum kernels](https://mlsanity.com/paper/2401.11098/) (2024)
- [Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2307.01171/) (2023)
- [Coreset selection can accelerate quantum machine learning models with provable generalization](https://mlsanity.com/paper/2309.10441/) (2023)
- [Lean classical-quantum hybrid neural network model for image classification](https://mlsanity.com/paper/2412.02059/) (2024)
- [Post-variational quantum neural networks](https://mlsanity.com/paper/2307.10560/) (2023)
- [Performance Guarantees for Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2511.19289/) (2025)
- [Modeling Quantum Machine Learning for Genomic Data Analysis](https://mlsanity.com/paper/2501.08193/) (2025)
- [BenchRL-QAS: Benchmarking reinforcement learning algorithms for quantum architecture search](https://mlsanity.com/paper/2507.12189/) (2025)
- [QDCNN: Quantum Deep Learning for Enhancing Safety and Reliability in Autonomous Transportation Systems](https://mlsanity.com/paper/2503.01916/) (2025)
- [Probabilistic Quantum SVM Training on Ising Machine](https://mlsanity.com/paper/2503.16363/) (2025)
- [Superior resilience to poisoning and amenability to unlearning in quantum machine learning](https://mlsanity.com/paper/2508.02422/) (2025)
- [PALQO: Physics-informed Model for Accelerating Large-scale Quantum Optimization](https://mlsanity.com/paper/2509.20733/) (2025)
- [Quantum feature-map learning with reduced resource overhead](https://mlsanity.com/paper/2510.03389/) (2025)
- [Intrinsic preservation of plasticity in continual quantum learning](https://mlsanity.com/paper/2511.17228/) (2025)
- [Quantum Support Vector Regression for Robust Anomaly Detection](https://mlsanity.com/paper/2505.01012/) (2025)
- [Enhancing the Dynamic Range of Quantum Sensing via Quantum Circuit Learning](https://mlsanity.com/paper/2505.04958/) (2025)
- [On the Design of Expressive and Trainable Pulse-based Quantum Machine Learning Models](https://mlsanity.com/paper/2508.05559/) (2025)
- [Quantum feature encoding optimization](https://mlsanity.com/paper/2512.02422/) (2025)
- [Parameterized Quantum Circuits as Feature Maps: Representation Quality and Readout Effects in Multispectral Land-Cover Classification](https://mlsanity.com/paper/2604.26675/) (2026)
- [Adversarial Effects on Expressibility and Trainability in Distributed Variational Quantum Algorithms](https://mlsanity.com/paper/2605.03629/) (2026)

## Abstract (arXiv)

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.