The Need for Structure in Quantum Speedups (2009)
Aaronson, Scott, Ambainis, Andris
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...
BQP and the Polynomial Hierarchy (2009)
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...
The One-Way Communication Complexity of Group Membership (2009)
Aaronson, Scott, Gall, François Le, Russell, Alexander, Tani, Seiichiro
This paper studies the one-way communication complexity of the subgroup membership problem, a classical problem closely related to basic questions in quantum computing. Here Alice receives, as input,...
Algorithms for Boolean function query properties (2009)
Abstract. We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N 2.322 log N) algorithm for block sensitivity, an...
ABSTRACT Algebrization: A New Barrier in Complexity Theory ∗ (2009)
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...
The Power of Unentanglement (2009)
Aaronson, Scott, Beigi, Salman, Drucker, Andrew, Fefferman, Bill, Shor, Peter
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...
Abstract Any proof of P 6 = 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 nothave...
Closed Timelike Curves Make Quantum and Classical Computing Equivalent (2008)
Aaronson, Scott, Watrous, John
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...
On Perfect Completeness for QMA (2008)
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...
The Power of Unentanglement (2008)
Aaronson, Scott, Beigi, Salman, Drucker, Andrew, Fefferman, Bill, Shor, Peter
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...
Are quantum states exponentially long vectors? quant-ph/0507242 (2008)
In this extended abstract, which is based on a talk that I gave there, I demonstrate that gratitude by explaining why Goldreich’s views about quantum computing are wrong. Why should anyone care?...
The Computational Complexity Column by (2007)
I have moved back to the University of Chicago and so has the web page for this column. See above for new URL and contact informaion. This issue Scott Aaronson writes quite an interesting (and...
Algorithms for Boolean function query properties (2007)
Abstract. We investigate e#cient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query...
Representing probabilistic data via ontological models (2007)
Harrigan, Nicholas, Rudolph, Terry, Aaronson, Scott
Ontological models are attempts to quantitatively describe the results of a probabilistic theory, such as Quantum Mechanics, in a framework exhibiting an explicit realism-based underpinning. Unlike...
Algebrization: A new barrier in complexity theory (2007)
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...
Algebrization: A new barrier in complexity theory (2007)
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...
Most of my research deals with two questions: first, what are the ultimate limits on what can feasibly be computed in the physical world? Second, how can studying those limits shed light on basic...
The Learnability of Quantum States (2006)
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...
Quantum Versus Classical Proofs and Advice (2006)
Aaronson, Scott, Kuperberg, Greg
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum...
Quantum versus classical proofs and advice (2006)
Scott Aaronson, Greg Kuperberg, S. Aaronson, G. Kuperberg
Abstract: This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA. We prove three results about this question. First, we give a...
The learnability of quantum states (2006)
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...
Quantum versus classical proofs and advice (2006)
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 three results about this question. First, we give a “quantum...
QMA/qpoly ⊆ PSPACE/poly: De-Merlinizing quantum protocols, to appear (2006)
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...
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols (2005)
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...
Are Quantum States Exponentially Long Vectors? (2005)
I'm grateful to Oded Goldreich for inviting me to the 2005 Oberwolfach Meeting on Complexity Theory. In this extended abstract, which is based on a talk that I gave there, I demonstrate that...
Oracles Are Subtle But Not Malicious (2005)
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...
NP-complete Problems and Physical Reality (2005)
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,...
Scott Aaronson, Andris Ambainis
Can Grover’s algorithm speed up search of a physical region—for example a 2-D grid of size √ n × √ n? The problem is that √ n time seems to be needed for each query, just to move amplitude...
The complexity of agreement (2005)
agents with common priors can never “agree to disagree”: if their opinions about any topic are common knowledge, then those opinions must be equal. But two key questions went unaddressed: first,...
The complexity of agreement (2005)
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...
Quantum computing, postselection, and probabilistic (2005)
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...
NP-complete problems and physical reality (2005)
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 Computing, Postselection, and Probabilistic Polynomial-Time (2004)
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...
Limits on Efficient Computation in the Physical World (2004)
More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from...
Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories (2004)
This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In...
Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices (2004)
This paper initiates the study of hidden variables from the discrete, abstract perspective of quantum computing. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps...
The Complexity of Agreement (2004)
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...
Improved Simulation of Stabilizer Circuits (2004)
Aaronson, Scott, Gottesman, Daniel
The Gottesman-Knill theorem says that a stabilizer circuit -- that is, a quantum circuit consisting solely of CNOT, Hadamard, and phase gates -- can be simulated efficiently on a classical computer....
Limitations of Quantum Advice and One-Way Communication (2004)
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...
Is Quantum Mechanics An Island In Theoryspace? (2004)
This recreational paper investigates what happens if we change quantum mechanics in several ways. The main results are as follows. First, if we replace the 2-norm by some other p-norm, then there are...
Is Quantum Mechanics An Island in Theoryspace? (2004)
This paper investigates what happens if we change quantum mechanics in several ways. The main results are as follows. First, if we replace the 2-norm by some other p-norm, then there are no...
Limitations of Quantum Advice and One-Way Communication (2004)
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...
Limitations of Quantum Advice and One-Way Communication (2004)
Abstract: 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...
Multilinear Formulas and Skepticism of Quantum Computing (2004)
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...
Is Quantum Mechanics an Island in Theoryspace? (2004)
This recreational paper investigates what happens if we change quantum mechanics in several ways.
Lower Bounds for Local Search by Quantum Arguments (2004)
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 , we show a...
Multilinear Formulas and Skepticism of Quantum Computing (2004)
Scott Aaronson, Several Researchers, Including Leonid Levin, Gerard 't Hooft, Stephen Wolfram
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...
Multilinear Formulas and Skepticism of Quantum Computing (2004)
Scott Aaronson, Several Researchers, Including Leonid Levin, Gerard 't Hooft
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...
Multilinear Formulas and Skepticism of Quantum Computing (2004)
Scott Aaronson, Several Researchers, Including Leonid Levin, Gerard ’t Hooft, Stephen Wolfram
Multilinear Formulas and Skepticism of Quantum Computing (2003)
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...
Lower Bounds for Local Search by Quantum Arguments (2003)
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...
Quantum Search of Spatial Regions (2003)
Aaronson, Scott, Ambainis, Andris
Can Grover's algorithm speed up search of a physical region - for example a 2-D grid of size sqrt(n) by sqrt(n)? The problem is that sqrt(n) time seems to be needed for each query, just to move...
A Summer Internship at Bell Labs (2003)
Imagine - Volume 5, Number 5, May/June 1998
Quantum search of spatial regions (2003)
Scott Aaronson, C Scott Aaronson, Andris Ambainis, Andris Ambainis, S. Aaronson, A. Ambainis
Abstract: Can Grover’s algorithm speed up search of a physical region—for example a 2-D grid of size √ n × √ n? The problem is that √ n time seems to be needed for each query, just to move...
Is P versus NP formally independent (2003)
I have moved back to the University of Chicago and so has the web page for this column. See above for new URL and contact informaion. This issue Scott Aaronson writes quite an interesting (and...
Quantum certificate complexity (2003)
Given a Boolean function f, we study two natural gener-alizations of the certificate complexity C (f): the randomized certificate complexity RC (f) and the quantum certificate complexity QC(f). Using...
Quantum lower bound for recursive Fourier sampling (2003)
We revisit the oft-neglected 'recursive Fourier sampling ' (RFS) prob-lem, introduced by Bernstein and Vazirani to prove an oracle separation between B]] and BQ]. We show that the known...
Quantum certificate complexity (2003)
Given a total Boolean function f, we study two natural generalizations of the certificate complexity C (f)--the randomized certificate complexity-Re (f) and the quantum certificate complexity QC(f)....
Is P versus NP formally independent (2003)
I have moved back to the University of Chicago and so has the web page for this column. See above for new URL and contact informaion. This issue Scott Aaronson writes quite an interesting (and...
Quantum certificate complexity (2003)
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 ’...
Is P versus NP formally independent (2003)
This is a survey about the title question, written for people who (like the author) see logic as forbidding, esoteric, and remote from their usual concerns. Beginning with a crash course on...
Quantum lower bound for recursive Fourier sampling (2003)
One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algorithm is not far...
Quantum search of spatial regions (2003)
Scott Aaronson, C Scott Aaronson, Andris Ambainis, Andris Ambainis, S. Aaronson, A. Ambainis
Abstract: Can Grover’s algorithm speed up search of a physical region—for example a 2-D grid of size √ n × √ n? The problem is that √ n time seems to be needed for each query, just to move...
Quantum certificate complexity (2003)
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...
Quantum Certificate Complexity (2002)
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...
Quantum Lower Bound for Recursive Fourier Sampling (2002)
One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algorithm is not far...
Book Review: 'A New Kind of Science' (2002)
This is a critical review of the book 'A New Kind of Science' by Stephen Wolfram. We do not attempt a chapter-by-chapter evaluation, but instead focus on two areas: computational complexity and...
Quantum Computing and Dynamical Quantum Models (2002)
A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model yields a...
Quantum lower bound for the collision problem (2002)
The collision problem is to decide whether a function X:
Quantum Lower Bound for the Collision Problem (2001)
The collision problem is to decide whether a function X:{1,..,n}->{1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Theta(n^{1/5}) on the number of...
Algorithms for Boolean Function Query Properties (2001)
We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585...
Query Complexity: Worst-Case Quantum Versus Average-Case Classical (2000)
In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a...