4.7 Article

Quantum learning of concentrated Boolean functions

期刊

QUANTUM INFORMATION PROCESSING
卷 21, 期 7, 页码 -

出版社

SPRINGER
DOI: 10.1007/s11128-022-03607-5

关键词

Quantum computing; Machine learning; PAC learning; Concentrated functions

资金

  1. 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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据