Journal
QUANTUM INFORMATION PROCESSING
Volume 21, Issue 7, Pages -Publisher
SPRINGER
DOI: 10.1007/s11128-022-03607-5
Keywords
Quantum computing; Machine learning; PAC learning; Concentrated functions
Funding
- Defense Advanced Research Projects Agency [FA8750-16-2-0004]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available