ECCC-Report TR18-137https://eccc.weizmann.ac.il/report/2018/137Comments and Revisions published for TR18-137en-usTue, 07 Aug 2018 18:13:21 +0300
Paper TR18-137
| Quantum Lower Bound for Approximate Counting Via Laurent Polynomials |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2018/137We consider the following problem: estimate the size of a nonempty set $S\subseteq\left[ N\right] $, given both quantum queries to a membership oracle for $S$, and a device that generates equal superpositions $\left\vert S\right\rangle $ over $S$ elements. We show that, if $\left\vert S\right\vert $ is neither too large nor too small, then approximate counting with these resources is still quantumly hard. More precisely, any quantum algorithm needs either $\Omega\left( \sqrt{N/\left\vert S\right\vert }\right) $ queries or else $\Omega\left( \min\left\{ \left\vert S\right\vert ^{1/4},\sqrt{N/\left\vert S\right\vert }\right\} \right)$ copies of $\left\vert S\right\rangle $. This means that, in the black-box setting, quantum sampling does not imply approximate counting. The proof uses a novel generalization of the polynomial method of Beals et al. to Laurent polynomials, which can have negative exponents.Tue, 07 Aug 2018 18:13:21 +0300https://eccc.weizmann.ac.il/report/2018/137