Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SCOTT AARONSON:
All reports by Author Scott Aaronson:

TR23-020 | 3rd March 2023
Scott Aaronson, Shih-Han Hung

Certified Randomness from Quantum Supremacy

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>>


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

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


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

The Acrobatics of BQP

Revisions: 3

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


TR21-115 | 6th August 2021
Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

On quantum versus classical query complexity

Revisions: 2

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the ... more >>>


TR20-146 | 24th September 2020
Scott Aaronson, Yosi Atia, Leonard Susskind

On the Hardness of Detecting Macroscopic Superpositions

When is decoherence "effectively irreversible"? Here we examine this central question of quantum foundations using the tools of quantum computational complexity. We prove that, if one had a quantum circuit to determine if a system was in an equal superposition of two orthogonal states (for example, the $|$Alive$\rangle$ and $|$Dead$\rangle$ ... more >>>


TR20-115 | 1st August 2020
Scott Aaronson

The Busy Beaver Frontier

The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I offer a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: ... more >>>


TR20-066 | 28th April 2020
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Quantum Implications of Huang's Sensitivity Theorem

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, ... 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-061 | 16th April 2019
Scott Aaronson, Daniel Grier, Luke Schaeffer

A Quantum Query Complexity Trichotomy for Regular Languages

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


TR19-060 | 18th April 2019
Scott Aaronson, Guy Rothblum

Gentle Measurement of Quantum States and Differential Privacy

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


TR18-137 | 7th August 2018
Scott Aaronson

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials

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


TR18-099 | 19th May 2018
Scott Aaronson

PDQP/qpoly = ALL

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


TR17-164 | 3rd November 2017
Scott Aaronson

Shadow Tomography of Quantum States

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


TR17-004 | 8th January 2017
Scott Aaronson

P=?NP

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


TR16-200 | 18th December 2016
Scott Aaronson, Lijie Chen

Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Revisions: 1

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


TR16-146 | 18th September 2016
Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

Computability Theory of Closed Timelike Curves

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


TR16-109 | 18th July 2016
Scott Aaronson

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

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


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

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


TR15-203 | 13th December 2015
Scott Aaronson, Shalev Ben-David

Sculpting Quantum Speedups

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


TR15-175 | 5th November 2015
Scott Aaronson, Shalev Ben-David, Robin Kothari

Separations in query complexity using cheat sheets

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


TR15-066 | 20th April 2015
Scott Aaronson, Daniel Grier, Luke Schaeffer

The Classification of Reversible Bit Operations

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


TR14-181 | 19th December 2014
Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

The space "just above" BQP

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


TR14-155 | 21st November 2014
Scott Aaronson, Andris Ambainis

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

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


TR14-109 | 14th August 2014
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Quantum lower bound for inverting a permutation with advice

Revisions: 1

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


TR14-012 | 27th January 2014
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

AM with Multiple Merlins

Revisions: 1

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


TR13-164 | 28th November 2013
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

Weak Parity

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


TR13-147 | 25th October 2013
Adam Bouland, Scott Aaronson

Any Beamsplitter Generates Universal Quantum Linear Optics

Revisions: 3

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


TR13-135 | 27th September 2013
Scott Aaronson

BosonSampling Is Far From Uniform

Revisions: 2

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


TR12-170 | 30th November 2012
Scott Aaronson, Travis Hance

Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

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


TR12-024 | 25th March 2012
Scott Aaronson, Paul Christiano

Quantum Money from Hidden Subspaces

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


TR11-108 | 8th August 2011
Scott Aaronson

Why Philosophers Should Care About Computational Complexity

Revisions: 2

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


TR11-043 | 25th March 2011
Scott Aaronson

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

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


TR11-008 | 27th January 2011
Scott Aaronson, Andrew Drucker

Advice Coins for Classical and Quantum Computation

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


TR11-001 | 2nd January 2011
Scott Aaronson

Impossibility of Succinct Quantum Proofs for Collision-Freeness

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


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

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


TR10-170 | 11th November 2010
Scott Aaronson, Alex Arkhipov

The Computational Complexity of Linear Optics

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


TR10-128 | 15th August 2010
Scott Aaronson

The Equivalence of Sampling and Searching

Revisions: 1

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


TR10-109 | 11th July 2010
Scott Aaronson

A Counterexample to the Generalized Linial-Nisan Conjecture

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


TR10-105 | 29th June 2010
Scott Aaronson, Dieter van Melkebeek

A note on circuit lower bounds from derandomization

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

TR10-057 | 1st April 2010
Scott Aaronson, Andrew Drucker

A Full Characterization of Quantum Advice

Revisions: 3

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


TR09-110 | 5th November 2009
Scott Aaronson, Andris Ambainis

The Need for Structure in Quantum Speedups

Revisions: 1

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


TR09-104 | 26th October 2009
Scott Aaronson

BQP and the Polynomial Hierarchy

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


TR08-092 | 26th August 2008
Scott Aaronson, John Watrous

Closed Timelike Curves Make Quantum and Classical Computing Equivalent

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


TR08-067 | 4th June 2008
Scott Aaronson

On Perfect Completeness for QMA

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


TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The Power of Unentanglement

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


TR08-005 | 15th January 2008
Scott Aaronson, Avi Wigderson

Algebrization: A New Barrier in Complexity Theory

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


TR06-106 | 18th August 2006
Scott Aaronson

The Learnability of Quantum States

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


TR06-055 | 10th April 2006
Scott Aaronson, Greg Kuperberg

Quantum Versus Classical Proofs and Advice

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


TR05-129 | 30th October 2005
Scott Aaronson

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

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


TR05-040 | 13th April 2005
Scott Aaronson

Oracles Are Subtle But Not Malicious

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


TR05-026 | 15th February 2005
Scott Aaronson

NP-complete Problems and Physical Reality

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


TR05-003 | 23rd December 2004
Scott Aaronson

Quantum Computing, Postselection, and Probabilistic Polynomial-Time

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


TR04-061 | 30th June 2004
Scott Aaronson

The Complexity of Agreement

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


TR04-026 | 17th February 2004
Scott Aaronson

Limitations of Quantum Advice and One-Way Communication

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


TR03-079 | 8th November 2003
Scott Aaronson

Multilinear Formulas and Skepticism of Quantum Computing

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


TR03-057 | 21st July 2003
Scott Aaronson

Lower Bounds for Local Search by Quantum Arguments

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


TR03-005 | 28th December 2002
Scott Aaronson

Quantum Certificate Complexity

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


TR02-072 | 12th November 2002
Scott Aaronson

Quantum Lower Bound for Recursive Fourier Sampling

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




ISSN 1433-8092 | Imprint