Abstract
Given a problem which is intractable for both quantum and classical algorithms, can we find a subproblem 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(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 superquadratic 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 BPPbiimmune 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.
BibTeX  Entry
@InProceedings{aaronson_et_al:LIPIcs:2016:5853,
author = {Scott Aaronson and Shalev BenDavid},
title = {{Sculpting Quantum Speedups}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {26:126:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5853},
URN = {urn:nbn:de:0030drops58538},
doi = {10.4230/LIPIcs.CCC.2016.26},
annote = {Keywords: Quantum Computing, Query Complexity, Decision Tree Complexity, Structural Complexity}
}
Keywords: 

Quantum Computing, Query Complexity, Decision Tree Complexity, Structural Complexity 
Collection: 

31st Conference on Computational Complexity (CCC 2016) 
Issue Date: 

2016 
Date of publication: 

19.05.2016 