Quantum Semi-Supervised Learning with Quantum Supremacy
arXiv:2110.02343
Abstract
Quantum machine learning promises to efficiently solve important problems. There are two persistent challenges in classical machine learning: the lack of labeled data, and the limit of computational power. We propose a novel framework that resolves both issues: quantum semi-supervised learning. Moreover, we provide a protocol in systematically designing quantum machine learning algorithms with quantum supremacy, which can be extended beyond quantum semi-supervised learning. In the meantime, we show that naive quantum matrix product estimation algorithm outperforms the best known classical matrix multiplication algorithm. We showcase two concrete quantum semi-supervised learning algorithms: a quantum self-training algorithm named the propagating nearest-neighbor classifier, and the quantum semi-supervised K-means clustering algorithm. By doing time complexity analysis, we conclude that they indeed possess quantum supremacy.
arXiv commentAcknowledgement modified to reflect truth
References in corpus (9)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Quantum machine learning in feature Hilbert spaces
- Quantum algorithms for supervised and unsupervised machine learning
- Architectures for a quantum random access memory
- Quantum Data Compression and Quantum Cross Entropy
- Quantum Cross Entropy and Maximum Likelihood Principle
- Complexity, Entropy, and Markov Chains