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.
翻译:量子机器学习有望有效解决重要问题。古典机器学习中存在两个持续的挑战:缺乏标签数据,以及计算能力的限制。我们提出了一个解决这两个问题的新框架:量子半监督学习。此外,我们提供了一个协议,系统地设计量子机器学习算法,这种算法可以超越量子半监督学习。与此同时,我们表明天真的量子矩阵产品估计算法优于最已知的经典矩阵乘法。我们展示了两种具体的量子半监督学习算法:一种量子自我培训算法,名为“传播近邻分类”和量子半监督K手段集算法。通过时间复杂性分析,我们得出结论,它们确实拥有量子优势。