Quadratic speed-ups in quantum kernelized binary classification

Abstract

Classification is at the core of data-driven prediction and decision-making, representing a fundamental task in supervised machine learning. Recently, several quantum machine learning algorithms that use quantum kernels as a measure of similarities between data have emerged to perform binary classification on datasets encoded as quantum states. The potential advantages of quantum kernels arise from the ability of quantum computers to construct kernels that are more effective than their classical counterparts in capturing patterns in data or computing kernels more efficiently. However, existing quantum kernel-based classification algorithms do not harness the capability of having data samples in quantum superposition for additional enhancements. In this work, we demonstrate how such capability can be leveraged in quantum kernelized binary classifiers (QKCs) through Quantum Amplitude Estimation (QAE) for quadratic speed-up. Additionally, we propose new quantum circuits for the QKCs in which the number of qubits is reduced by one, and the circuit depth is reduced linearly with respect to the number of sample data. We verify the quadratic speed-up over previous methods through numerical simulations on the Iris dataset.

arXiv comment20 pages, 11 figures

References in corpus (31)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Supervised learning with quantum enhanced feature spaces
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• Kernel methods in machine learning
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• An introduction to quantum machine learning
• Quantum fingerprinting
• Circuit-centric quantum classifiers
• A Theory of Fault-Tolerant Quantum Computation
• Power of data in quantum machine learning
• Challenges and Opportunities in Quantum Machine Learning
• A rigorous and robust quantum speed-up in supervised machine learning
• Robust data encodings for quantum classifiers
• Quantum speedup of Monte Carlo methods
• Implementing a distance-based classifier with a quantum interference circuit
• Amplitude estimation without phase estimation
• Iterative Quantum Amplitude Estimation
• Approximate Quantum Fourier Transform and Decoherence
• A divide-and-conquer algorithm for quantum state preparation
• Quantum circuits with uniformly controlled one-qubit gates
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• The theory of the quantum kernel-based binary classifier
• Linear-depth quantum circuits for multiqubit controlled gates
• Configurable sublinear circuits for quantum state preparation
• Compact quantum kernel-based binary classifier
• A Multi-Class SWAP-Test Classifier