Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-137 | 7th August 2018 18:13

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials


Authors: Scott Aaronson
Publication: 7th August 2018 18:13
Downloads: 217


We 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.

ISSN 1433-8092 | Imprint