Scott Aaronson, Andris Ambainis

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

Scott Aaronson, Paul Christiano

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that ... more >>>

Arturs Backurs, Mohammad Bavarian

For a multilinear polynomial $p(x_1,...x_n)$, over the reals, the $L1$-influence is defined to be $\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where $x^i$ is $x$ with $i$-th bit swapped. If $p$ maps $\{-1,1\}^n$ to $[-1,1]$, we prove that the $L1$-influence of $p$ is upper bounded by a function of its degree (and independent of ... more >>>

Scott Aaronson

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