文章基本信息

标题：Two New Results About Quantum Exact Learning
本地全文：下载
作者：Srinivasan Arunachalam ; Sourav Chakraborty ; Troy Lee 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-15
DOI：10.4230/LIPIcs.ICALP.2019.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k^{1.5}(log k)^2) uniform quantum examples for that function. This improves over the bound of Theta~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang's lemma for sparse Boolean functions. Second, we show that if a concept class {C} can be exactly learned using Q quantum membership queries, then it can also be learned using O ({Q^2}/{log Q} * log C ) classical membership queries. This improves the previous-best simulation result (Servedio-Gortler, SICOMP'04) by a log Q-factor.
关键词：quantum computing; exact learning; analysis of Boolean functions; Fourier sparse Boolean functions