ECCC-Report TR15-203https://eccc.weizmann.ac.il/report/2015/203Comments and Revisions published for TR15-203en-usSun, 13 Dec 2015 17:01:35 +0200
Paper TR15-203
| Sculpting Quantum Speedups |
Scott Aaronson,
Shalev Ben-David
https://eccc.weizmann.ac.il/report/2015/203Given 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.Sun, 13 Dec 2015 17:01:35 +0200https://eccc.weizmann.ac.il/report/2015/203