{"id":380510,"date":"2017-04-19T12:00:33","date_gmt":"2017-04-19T19:00:33","guid":{"rendered":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/?post_type=msr-research-item&#038;p=380510"},"modified":"2017-05-02T16:09:01","modified_gmt":"2017-05-02T23:09:01","slug":"quantum-query-complexity-entropy-estimation","status":"publish","type":"msr-video","link":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/video\/quantum-query-complexity-entropy-estimation\/","title":{"rendered":"Quantum query complexity of entropy estimation"},"content":{"rendered":"<p>Estimation of Shannon and Renyi entropies of unknown discrete distributions is a fundamental problem in classical statistical property testing that has been intensively studied by the communities of both theoretical computer science and information theory. Tight bounds of the number of samples to estimate these entropies have been established in the classical setting, while little is known if one introduces quantum computation into the picture. In this paper, we systematically study the potential quantum speed-up in estimating alpha-Renyi entropies for general alpha (Shannon entropy is 1-Renyi entropy).<\/p>\n<p>In particular, we demonstrate a quadratic quantum speed-up for Shannon entropy estimation and also a generic quantum speed-up for alpha-Renyi entropy estimation when 1\/2<alpha<2 and for integer alpha >=2. Our result for 1\/2<alpha<2 is inspired by Bravyi, Harrow, and Hassidim (BHH), however, with a few new ingredients in our algorithm design and analysis: the first one is to leverage a generic quantum speed-up of estimating the expectation of the output of any quantum procedure by Montanaro, which significantly improves our error dependence comparing to BHH; the second one is a careful analysis of output distributions of our quantum algorithms because of the special form of entropies. Our result for integer alpha>=2 is achieved by building a connection between the entropy estimation problem and the k-distinctness problem and then by utilizing the state-of-the-art quantum algorithm for k-distinctness by Belovs.<\/p>\n<p>Finally, we complement our quantum upper bounds with quantum lower bounds of alpha-Renyi entropy estimation for all alpha>0.<\/p>\n<p>Joint work with Tongyang Li.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Estimation of Shannon and Renyi entropies of unknown discrete distributions is a fundamental problem in classical statistical property testing that has been intensively studied by the communities of both theoretical computer science and information theory. Tight bounds of the number of samples to estimate these entropies have been established in the classical setting, while little [&hellip;]<\/p>\n","protected":false},"featured_media":380633,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[13552],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-380510","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-research-area-hardware-devices","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/Y9B8nGKJADY","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/380510","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/380510\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/media\/380633"}],"wp:attachment":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/media?parent=380510"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=380510"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=380510"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=380510"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=380510"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=380510"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=380510"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=380510"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=380510"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=380510"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}