Two new results about quantum exact learning

Arunachalam, S; Chakraborty, S; Lee, T; Paraashar, M; de Wolf, R

Two new results about quantum exact learning

Arunachalam, S Chakraborty, S Lee, T

Paraashar, M de Wolf, R

Permalink

Publisher:: Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
Publication Type:: Journal Article
Citation:: Quantum, 2021, 5, pp. 587
Issue Date:: 2021-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (675.02 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Arunachalam, S
dc.contributor.author	Chakraborty, S
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.contributor.author	Paraashar, M
dc.contributor.author	de Wolf, R
dc.date.accessioned	2022-01-28T04:14:32Z
dc.date.available	2022-01-28T04:14:32Z
dc.date.issued	2021-01-01
dc.identifier.citation	Quantum, 2021, 5, pp. 587
dc.identifier.issn	2521-327X
dc.identifier.issn	2521-327X
dc.identifier.uri	http://hdl.handle.net/10453/153739
dc.description.abstract	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(k1.5(log k)2) uniform quantum examples for that function. This improves over the bound of Θ(e kn) uniformly random classical examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our Oe(k1.5) upper bound by proving an improvement of Chang's lemma for k-Fourier-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 (logQ2Q log \|C\| ) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log Q-factor.
dc.language	en
dc.publisher	Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
dc.relation	http://purl.org/au-research/grants/arc/DP200100950
dc.relation.ispartof	Quantum
dc.relation.isbasedon	10.22331/Q-2021-11-24-587
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Two new results about quantum exact learning
dc.type	Journal Article
utslib.citation.volume	5
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access	*
dc.date.updated	2022-01-28T04:14:31Z
pubs.publication-status	Published
pubs.volume	5

Abstract:

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(k1.5(log k)2) uniform quantum examples for that function. This improves over the bound of Θ(e kn) uniformly random classical examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our Oe(k1.5) upper bound by proving an improvement of Chang's lemma for k-Fourier-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 (logQ2Q log |C| ) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log Q-factor.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/153739