All reports by Author Scott Aaronson:

__
TR19-062
| 18th April 2019
__

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

Revisions: 1

__
TR19-061
| 16th April 2019
__

Scott Aaronson, Daniel Grier, Luke Schaeffer#### A Quantum Query Complexity Trichotomy for Regular Languages

__
TR19-060
| 18th April 2019
__

Scott Aaronson, Guy Rothblum#### Gentle Measurement of Quantum States and Differential Privacy

__
TR18-137
| 7th August 2018
__

Scott Aaronson#### Quantum Lower Bound for Approximate Counting Via Laurent Polynomials

__
TR18-099
| 19th May 2018
__

Scott Aaronson#### PDQP/qpoly = ALL

__
TR17-164
| 3rd November 2017
__

Scott Aaronson#### Shadow Tomography of Quantum States

__
TR17-004
| 8th January 2017
__

Scott Aaronson#### P=?NP

__
TR16-200
| 18th December 2016
__

Scott Aaronson, Lijie Chen#### Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Revisions: 1

__
TR16-146
| 18th September 2016
__

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini#### Computability Theory of Closed Timelike Curves

__
TR16-109
| 18th July 2016
__

Scott Aaronson#### The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

__
TR16-016
| 30th January 2016
__

Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson#### Doubly infinite separation of quantum information and communication

__
TR15-203
| 13th December 2015
__

Scott Aaronson, Shalev Ben-David#### Sculpting Quantum Speedups

__
TR15-175
| 5th November 2015
__

Scott Aaronson, Shalev Ben-David, Robin Kothari#### Separations in query complexity using cheat sheets

__
TR15-066
| 20th April 2015
__

Scott Aaronson, Daniel Grier, Luke Schaeffer#### The Classification of Reversible Bit Operations

__
TR14-181
| 19th December 2014
__

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee#### The space "just above" BQP

__
TR14-155
| 21st November 2014
__

Scott Aaronson, Andris Ambainis#### Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

__
TR14-109
| 14th August 2014
__

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan#### Quantum lower bound for inverting a permutation with advice

Revisions: 1

__
TR14-012
| 27th January 2014
__

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz#### AM with Multiple Merlins

Revisions: 1

__
TR13-164
| 28th November 2013
__

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian#### Weak Parity

__
TR13-147
| 25th October 2013
__

Adam Bouland, Scott Aaronson#### Any Beamsplitter Generates Universal Quantum Linear Optics

Revisions: 3

__
TR13-135
| 27th September 2013
__

Scott Aaronson#### BosonSampling Is Far From Uniform

Revisions: 2

__
TR12-170
| 30th November 2012
__

Scott Aaronson, Travis Hance#### Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

__
TR12-024
| 25th March 2012
__

Scott Aaronson, Paul Christiano#### Quantum Money from Hidden Subspaces

__
TR11-108
| 8th August 2011
__

Scott Aaronson#### Why Philosophers Should Care About Computational Complexity

Revisions: 2

__
TR11-043
| 25th March 2011
__

Scott Aaronson#### A Linear-Optical Proof that the Permanent is #P-Hard

__
TR11-008
| 27th January 2011
__

Scott Aaronson, Andrew Drucker#### Advice Coins for Classical and Quantum Computation

__
TR11-001
| 2nd January 2011
__

Scott Aaronson#### Impossibility of Succinct Quantum Proofs for Collision-Freeness

__
TR10-174
| 12th November 2010
__

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek#### A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

__
TR10-170
| 11th November 2010
__

Scott Aaronson, Alex Arkhipov#### The Computational Complexity of Linear Optics

__
TR10-128
| 15th August 2010
__

Scott Aaronson#### The Equivalence of Sampling and Searching

Revisions: 1

__
TR10-109
| 11th July 2010
__

Scott Aaronson#### A Counterexample to the Generalized Linial-Nisan Conjecture

__
TR10-105
| 29th June 2010
__

Scott Aaronson, Dieter van Melkebeek#### A note on circuit lower bounds from derandomization

__
TR10-057
| 1st April 2010
__

Scott Aaronson, Andrew Drucker#### A Full Characterization of Quantum Advice

Revisions: 3

__
TR09-110
| 5th November 2009
__

Scott Aaronson, Andris Ambainis#### The Need for Structure in Quantum Speedups

Revisions: 1

__
TR09-104
| 26th October 2009
__

Scott Aaronson#### BQP and the Polynomial Hierarchy

__
TR08-092
| 26th August 2008
__

Scott Aaronson, John Watrous#### Closed Timelike Curves Make Quantum and Classical Computing Equivalent

__
TR08-067
| 4th June 2008
__

Scott Aaronson#### On Perfect Completeness for QMA

__
TR08-051
| 4th April 2008
__

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor#### The Power of Unentanglement

__
TR08-005
| 15th January 2008
__

Scott Aaronson, Avi Wigderson#### Algebrization: A New Barrier in Complexity Theory

__
TR06-106
| 18th August 2006
__

Scott Aaronson#### The Learnability of Quantum States

__
TR06-055
| 10th April 2006
__

Scott Aaronson, Greg Kuperberg#### Quantum Versus Classical Proofs and Advice

__
TR05-129
| 30th October 2005
__

Scott Aaronson#### QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

__
TR05-040
| 13th April 2005
__

Scott Aaronson#### Oracles Are Subtle But Not Malicious

__
TR05-026
| 15th February 2005
__

Scott Aaronson#### NP-complete Problems and Physical Reality

__
TR05-003
| 23rd December 2004
__

Scott Aaronson#### Quantum Computing, Postselection, and Probabilistic Polynomial-Time

__
TR04-061
| 30th June 2004
__

Scott Aaronson#### The Complexity of Agreement

__
TR04-026
| 17th February 2004
__

Scott Aaronson#### Limitations of Quantum Advice and One-Way Communication

__
TR03-079
| 8th November 2003
__

Scott Aaronson#### Multilinear Formulas and Skepticism of Quantum Computing

__
TR03-057
| 21st July 2003
__

Scott Aaronson#### Lower Bounds for Local Search by Quantum Arguments

__
TR03-005
| 28th December 2002
__

Scott Aaronson#### Quantum Certificate Complexity

__
TR02-072
| 12th November 2002
__

Scott Aaronson#### Quantum Lower Bound for Recursive Fourier Sampling

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

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity $\Theta(1)$, $\tilde{\Theta}(\sqrt n)$, or $\Theta(n)$. The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we ... more >>>

Scott Aaronson, Guy Rothblum

In differential privacy (DP), we want to query a database about $n$ users, in a way that "leaks at most $\varepsilon$ about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure $n$ quantum states, in a way that "damages the ... 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 >>>

Scott Aaronson

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... more >>>

Scott Aaronson

We introduce the problem of *shadow tomography*: given an unknown $D$-dimensional quantum mixed state $\rho$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$, estimate the probability that $E_{i}$ accepts $\rho$, to within additive error $\varepsilon$, for each of the $M$ measurements. How many copies of $\rho$ are needed to achieve this, ... more >>>

Scott Aaronson

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, ... more >>>

Scott Aaronson, Lijie Chen

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis ... more >>>

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>

Scott Aaronson

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, ... more >>>

Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson

We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call "doubly infinite," between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for which there exist instances ... more >>>

Scott Aaronson, Shalev Ben-David

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>>

Scott Aaronson, Shalev Ben-David, Robin Kothari

We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity ... more >>>

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>>

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>

Scott Aaronson, Andris Ambainis

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum ... more >>>

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>>

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

Adam Bouland, Scott Aaronson

In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m by m unitary transformations (or orthogonal transformations, in the real case) ... more >>>

Scott Aaronson

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random ... more >>>

Scott Aaronson, Travis Hance

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... 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 >>>

Scott Aaronson

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the ... more >>>

Scott Aaronson

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing---and in particular, a universality theorem due to Knill, Laflamme, and Milburn---one can give a different and ... more >>>

Scott Aaronson, Andrew Drucker

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

Scott Aaronson

We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right] $ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right) $ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>

Scott Aaronson, Alex Arkhipov

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a

model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ...
more >>>

Scott Aaronson

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability

distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input

$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set

$A_{x}$ with high probability. ...
more >>>

Scott Aaronson

In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that "almost k-wise independent" distributions are indistinguishable from the uniform distribution by constant-depth ... more >>>

Scott Aaronson, Dieter van Melkebeek

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.

more >>>Scott Aaronson, Andrew Drucker

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>>

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

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

Scott Aaronson, John Watrous

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The class QMA(k), introduced by Kobayashi et al., consists

of all languages that can be verified using k unentangled quantum

proofs. Many of the simplest questions about this class have remained

embarrassingly open: for example, can we give any evidence that k

quantum proofs are more powerful than one? Can ...
more >>>

Scott Aaronson, Avi Wigderson

Any proof of P!=NP will have to overcome two barriers: relativization

and natural proofs. Yet over the last decade, we have seen circuit

lower bounds (for example, that PP does not have linear-size circuits)

that overcome both barriers simultaneously. So the question arises of

whether there ...
more >>>

Scott Aaronson

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than

classical proofs, or in complexity terms, whether QMA=QCMA. We prove

two results about this question. First, we give a "quantum oracle

separation" between QMA and QCMA. More concretely, we show that any

quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ...
more >>>

Scott Aaronson

This paper introduces a new technique for removing existential quantifiers

over quantum states. Using this technique, we show that there is no way

to pack an exponential number of bits into a polynomial-size quantum

state, in such a way that the value of any one of those bits ...
more >>>

Scott Aaronson

Theoretical computer scientists have been debating the role of

oracles since the 1970's. This paper illustrates both that oracles

can give us nontrivial insights about the barrier problems in

circuit complexity, and that they need not prevent us from trying to

solve those problems.

First, we ... more >>>

Scott Aaronson

Can NP-complete problems be solved efficiently in the physical universe?

I survey proposals including soap bubbles, protein folding, quantum

computing, quantum advice, quantum adiabatic algorithms,

quantum-mechanical nonlinearities, hidden variables, relativistic time

dilation, analog computing, Malament-Hogarth spacetimes, quantum

gravity, closed timelike curves, and "anthropic computing." The ...
more >>>

Scott Aaronson

I study the class of problems efficiently solvable by a quantum computer, given the ability to "postselect" on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or Probabilistic Polynomial-Time. Using this result, I show that several simple changes to the axioms ... more >>>

Scott Aaronson

A celebrated 1976 theorem of Aumann asserts that honest, rational

Bayesian agents with common priors will never "agree to disagree": if

their opinions about any topic are common knowledge, then those

opinions must be equal. Economists have written numerous papers

examining the assumptions behind this theorem. But two key questions

more >>>

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones.

First, we show that BQP/qpoly is contained in ...
more >>>

Scott Aaronson

Several researchers, including Leonid Levin, Gerard 't Hooft, and

Stephen Wolfram, have argued that quantum mechanics will break down

before the factoring of large numbers becomes possible. If this is

true, then there should be a natural "Sure/Shor separator" -- that is,

a set of quantum ...
more >>>

Scott Aaronson

The problem of finding a local minimum of a black-box function is central

for understanding local search as well as quantum adiabatic algorithms.

For functions on the Boolean hypercube {0,1}^n, we show a lower bound of

Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to

solve this ...
more >>>

Scott Aaronson

Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation ... more >>>

Scott Aaronson

We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place BQP outside ... more >>>