Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > WILLIAM KRETSCHMER:
All reports by Author William Kretschmer:

TR21-164 | 19th November 2021
Scott Aaronson, DeVon Ingram, William Kretschmer

The Acrobatics of BQP

Revisions: 1

We show that, in the black-box setting, the behavior of quantum polynomial-time (${BQP}$) can be remarkably decoupled from that of classical complexity classes like ${NP}$. Specifically:

-There exists an oracle relative to which ${NP}^{{BQP}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits ... more >>>


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


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