Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author William Kretschmer:

TR19-062 | 18th April 2019
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

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

TR19-015 | 7th February 2019
William Kretschmer

QMA Lower Bounds for Approximate Counting

We prove a query complexity lower bound for $QMA$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to ... more >>>

ISSN 1433-8092 | Imprint