All reports by Author William Kretschmer:

__
TR23-015
| 20th February 2023
__

Scott Aaronson, Harry Buhrman, William Kretschmer#### A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

Revisions: 1

__
TR21-164
| 19th November 2021
__

Scott Aaronson, DeVon Ingram, William Kretschmer#### The Acrobatics of BQP

Revisions: 3

__
TR19-062
| 18th April 2019
__

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler#### Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Revisions: 2

__
TR19-015
| 7th February 2019
__

William Kretschmer#### QMA Lower Bounds for Approximate Counting

Scott Aaronson, Harry Buhrman, William Kretschmer

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>

Scott Aaronson, DeVon Ingram, William Kretschmer

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

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

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

William Kretschmer

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