Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LAURENT POLYNOMIALS:
Reports tagged with laurent polynomials:
TR19-062 | 18th April 2019
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

#### Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Revisions: 2

This paper proves new limitations on the power of quantum computers to solve approximate counting---that is, multiplicatively estimating the size of a nonempty set $S\subseteq [N]$.

Given only a membership oracle for $S$, it is well known that approximate counting takes $\Theta(\sqrt{N/|S|})$ quantum queries. But what if a quantum algorithm ... more >>>

ISSN 1433-8092 | Imprint