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.
Acknowledgement modified to reflect truth
References in corpus (6)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum algorithm for solving linear systems of equations
- 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