Under the auspices of the Computational Complexity Foundation (CCF) REPORTS > DETAIL:

### Paper:

TR15-203 | 13th December 2015 08:04

#### Sculpting Quantum Speedups TR15-203
Authors: Scott Aaronson, Shalev Ben-David
Publication: 13th December 2015 17:01
Keywords:

Abstract:

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. We show that a total function $f$ can be restricted to a promise $P$ such that $Q(f|_P)=O(\mathrm{polylog}\,N)$ and $R(f|_P)=N^{\Omega(1)}$, if and only if $f$ has a large number of inputs with large certificate complexity. The proof uses some interesting techniques: for one direction, we introduce new relationships between randomized and quantum query complexity in various settings, and for the other direction, we use a recent result from communication complexity due to Klartag and Regev. We also characterize sculpting for other query complexity measures, such as $R(f)$ vs. $R_0(f)$ and $R_0(f)$ vs. $D(f)$.

Along the way, we prove some new relationships for quantum query complexity: for example, a nearly quadratic relationship between $Q(f)$ and $D(f)$ whenever the promise of $f$ is small. This contrasts with the recent super-quadratic query complexity separations, showing that the maximum gap between classical and quantum query complexities is indeed quadratic in various settings - just not for total functions!

Lastly, we investigate sculpting in the Turing machine model. We show that if there is any BPP-bi-immune language in BQP, then every language outside BPP can be restricted to a promise which places it in PromiseBQP but not in PromiseBPP. Under a weaker assumption, that some problem in BQP is hard on average for P/poly, we show that every paddable language outside BPP is sculptable in this way.

ISSN 1433-8092 | Imprint
{"ft_lang_label":"__label__en","ft_lang_prob":0.9197406,"math_prob":0.96231437,"size":1818,"snap":"2021-43-2021-49","text_gpt3_token_len":406,"char_repetition_ratio":0.12513782,"word_repetition_ratio":0.014492754,"special_character_ratio":0.210121,"punctuation_ratio":0.09063444,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9856622,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-18T02:00:37Z\",\"WARC-Record-ID\":\"<urn:uuid:c9723b17-7944-405b-829a-6d3c1e4e4f32>\",\"Content-Length\":\"21245\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ffe9cd22-fc88-426b-a3ac-e9f7bfba97a8>\",\"WARC-Concurrent-To\":\"<urn:uuid:7e627b53-a40f-48f3-9593-be85f3fa0891>\",\"WARC-IP-Address\":\"132.77.150.87\",\"WARC-Target-URI\":\"https://eccc.weizmann.ac.il/report/2015/203/\",\"WARC-Payload-Digest\":\"sha1:YTAB4SGTSCW2F36R2BPKQEAEKDPU37UF\",\"WARC-Block-Digest\":\"sha1:7WUBAKM73BUF2KOP3CAVYGPKI2GIEOXZ\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585186.33_warc_CC-MAIN-20211018000838-20211018030838-00327.warc.gz\"}"}