期刊
QUANTUM INFORMATION PROCESSING
卷 21, 期 7, 页码 -出版社
SPRINGER
DOI: 10.1007/s11128-022-03607-5
关键词
Quantum computing; Machine learning; PAC learning; Concentrated functions
资金
- Defense Advanced Research Projects Agency [FA8750-16-2-0004]
This paper presents a series of new results on learning concentrated Boolean functions in the quantum computing model. The use of quantum approaches improves the query complexity, but still faces challenges in the case of exact learning without error.
In this paper, we present a series of new results about learning of concentrated Boolean functions in the quantum computing model. Given a Boolean function f on n variables, its concentration refers to the dominant terms in its Fourier-Walsh spectrum. We show that a quantum probabilistically approximately correct learning model to learn a Boolean function characterized by its concentration yields improvements over the best-known classical method. All of our results are presented within the framework of query complexity, and therefore, our advantage represents asymptotic improvements in the number of queries using a quantum approach over its classical counterpart. Next, we prove a lower bound in the number of quantum queries needed to learn the function in the distribution-independent settings. Further, we examine the case of exact learning which is the learning variant without error. Here, we show that the query complexity grows as 2(beta n) for some 0 < beta < 1 and therefore remains intractable even when quantum approaches are considered. This proof is based on the quantum information theoretic approach developed by researchers for the restricted case of k-sparse functions.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据