Two new results about quantum exact learning

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 $\widetilde{\Theta}(kn)$ uniformly random $c...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf
Formato:	article
Lenguaje:	EN
Publicado:	Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften 2021
Materias:	Physics QC1-999
Acceso en línea:	https://doaj.org/article/8200064c8301448c9fed6779fd3e55be
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:8200064c8301448c9fed6779fd3e55be
record_format	dspace
spelling	oai:doaj.org-article:8200064c8301448c9fed6779fd3e55be2021-11-24T14:44:09ZTwo new results about quantum exact learning2521-327X10.22331/q-2021-11-24-587https://doaj.org/article/8200064c8301448c9fed6779fd3e55be2021-11-01T00:00:00Zhttps://quantum-journal.org/papers/q-2021-11-24-587/pdf/https://doaj.org/toc/2521-327XWe 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 $\widetilde{\Theta}(kn)$ uniformly random $classical$ examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our $\widetilde{O}(k^{1.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 $\mathcal{C}$ can be exactly learned using $Q$ quantum membership queries, then it can also be learned using $O\left(\frac{Q^2}{\log Q}\log\|\mathcal{C}\|\right)$ $classical$ membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a $\log Q$-factor.Srinivasan ArunachalamSourav ChakrabortyTroy LeeManaswi ParaasharRonald de WolfVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenarticlePhysicsQC1-999ENQuantum, Vol 5, p 587 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999
spellingShingle	Physics QC1-999 Srinivasan Arunachalam Sourav Chakraborty Troy Lee Manaswi Paraashar Ronald de Wolf Two new results about quantum exact learning
description	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 $\widetilde{\Theta}(kn)$ uniformly random $classical$ examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our $\widetilde{O}(k^{1.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 $\mathcal{C}$ can be exactly learned using $Q$ quantum membership queries, then it can also be learned using $O\left(\frac{Q^2}{\log Q}\log\|\mathcal{C}\|\right)$ $classical$ membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a $\log Q$-factor.
format	article
author	Srinivasan Arunachalam Sourav Chakraborty Troy Lee Manaswi Paraashar Ronald de Wolf
author_facet	Srinivasan Arunachalam Sourav Chakraborty Troy Lee Manaswi Paraashar Ronald de Wolf
author_sort	Srinivasan Arunachalam
title	Two new results about quantum exact learning
title_short	Two new results about quantum exact learning
title_full	Two new results about quantum exact learning
title_fullStr	Two new results about quantum exact learning
title_full_unstemmed	Two new results about quantum exact learning
title_sort	two new results about quantum exact learning
publisher	Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
publishDate	2021
url	https://doaj.org/article/8200064c8301448c9fed6779fd3e55be
work_keys_str_mv	AT srinivasanarunachalam twonewresultsaboutquantumexactlearning AT souravchakraborty twonewresultsaboutquantumexactlearning AT troylee twonewresultsaboutquantumexactlearning AT manaswiparaashar twonewresultsaboutquantumexactlearning AT ronalddewolf twonewresultsaboutquantumexactlearning
_version_	1718415000075239424

Two new results about quantum exact learning

Ejemplares similares