• (Mostly-)Quantum Papers
• (Mostly-)Classical Papers
• Surveys and Book Reviews

(Mostly-)Quantum Papers

S. Aaronson and A. Drucker. A Full Characterization of Quantum Advice [PS] [PDF], to appear in Proceedings of ACM STOC, 2010. Conference version [PS] [PDF]. ECCC TR10-057, arXiv:1004.0377.

We prove the following surprising result: given any quantum state ρ 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 ρ on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, which supersedes the previous result of Aaronson that BQP/qpoly is contained in PP/poly. Indeed, we can exactly characterize quantum advice, as equivalent in power to untrusted quantum advice combined with trusted classical advice.

Proving our main result requires combining a large number of previous tools -- including a result of Alon et al. on learning of real-valued concept classes, a result of Aaronson on the learnability of quantum states, and a result of Aharonov and Regev on "QMA₊ super-verifiers" -- and also creating some new ones. The main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. In its simplest version, this lemma says the following. Given any set S of Boolean functions on n variables, any function f∈S can be expressed as the pointwise majority of m=O(n) functions f₁,...,f_m∈S, such that each f_i is the unique function in S compatible with O(log|S|) input/output constraints.

A. Lutomirski, S. Aaronson, E. Farhi, D. Gosset, A. Hassidim, J. Kelner, and P. Shor. Breaking and making quantum money: toward a new quantum cryptographic protocol, Proceedings of Innovations in Computer Science (ICS), 2010. arXiv:0912.3825.

Public-key quantum money is a cryptographic protocol in which a bank can create quantum states which anyone can verify but no one except possibly the bank can clone or forge. There are no secure public-key quantum money schemes in the literature; as we show in this paper, the only previously published scheme is insecure. We introduce a category of quantum money protocols which we call collision-free. For these protocols, even the bank cannot prepare multiple identical-looking pieces of quantum money. We present a blueprint for how such a protocol might work as well as a concrete example which we believe may be insecure.

S. Aaronson and A. Ambainis. The Need for Structure in Quantum Speedups [PS] [PDF], submitted, 2009. arXiv:0911.0996, ECCC TR09-110.

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 is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9^th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002.

Second, inspired by recent work of O'Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P≠BQP relative to a random oracle.

S. Aaronson. BQP and the Polynomial Hierarchy [PS] [PDF], to appear in Proceedings of ACM STOC 2010. arXiv:0910.4698, ECCC TR09-104.

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 exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not AC⁰.

Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.

S. Aaronson. Quantum Copy-Protection and Quantum Money [PS] [PDF], conference version in Proceedings of IEEE Complexity 2009, pp. 229-242. Full version still in preparation.

Forty years ago, Wiesner proposed using quantum states to create money that is physically impossible to counterfeit, something that cannot be done in the classical world. However, Wiesner's scheme required a central bank to verify the money, and the question of whether there can be unclonable quantum money that anyone can verify has remained open since. One can also ask a related question, which seems to be new: can quantum states be used as copy-protected programs, which let the user evaluate some function f, but not create more programs for f?

This paper tackles both questions using the arsenal of modern computational complexity. Our main result is that there exist quantum oracles relative to which publicly-verifiable quantum money is possible, and any family of functions that cannot be efficiently learned from its input-output behavior can be quantumly copy-protected. This provides the first formal evidence that these tasks are achievable. The technical core of our result is a "Complexity-Theoretic No-Cloning Theorem," which generalizes both the standard No-Cloning Theorem and the optimality of Grover search, and might be of independent interest. Our security argument also requires explicit constructions of quantum t-designs.

Moving beyond the oracle world, we also present an explicit candidate scheme for publicly-verifiable quantum money, based on random stabilizer states; as well as two explicit schemes for copy-protecting the family of point functions. We do not know how to base the security of these schemes on any existing cryptographic assumption. (Note that without an oracle, we can only hope for security under some computational assumption.)

S. Aaronson, F. Le Gall, A. Russell, and S. Tani. The One-Way Communication Complexity of Group Membership [PS] [PDF], submitted, 2009. arXiv:0902.3175.

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, a subgroup H of a finite group G; Bob receives an element x∈G. Alice is permitted to send a single message to Bob, after which he must decide if his input x is an element of H. We prove the following upper bounds on the classical communication complexity of this problem in the bounded-error setting:
1. The problem can be solved with O(log |G|) communication, provided the subgroup H is normal;
2. The problem can be solved with O(d_max log |G|) communication, where d_max is the maximum of the dimensions of the irreducible complex representations of G;
3. For any prime p not dividing |G|, the problem can be solved with O(d_max log p) communication, where d_max is the maximum of the dimensions of the irreducible F_p-representations of G.

S. Aaronson and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [PS] [PDF], Proceedings of the Royal Society A 465:631-647, 2009. arXiv:0808.2669.

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 (extremely large) power of the complexity class PSPACE, consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a "causal consistency" condition is imposed, meaning that Nature has to produce a (probabilistic or quantum) fixed-point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed-point of the circuit can be (implicitly) computed in polynomial space. This theorem might have independent applications in quantum information.

S. Aaronson. On Perfect Completeness for QMA [PS] [PDF], Quantum Information & Computation, vol. 9, p. 81-89, 2009. arXiv:0806.0450.

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA₁, 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≠QMA₁. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP⊆ZQEXP.

N. Harrigan, T. Rudolph, and S. Aaronson. Representing Probabilistic Data via Ontological Models, submitted, 2008. arXiv:0709.1149.

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 either the well known quasi-probability representations, or the "r-p" vector formalism, these models are contextual and by definition only involve positive probability distributions (and indicator functions). In this article we study how the ontological model formalism can be used to describe arbitrary statistics of a system subjected to a finite set of preparations and measurements. We present three models which can describe any such empirical data and then discuss how to turn an indeterministic model into a deterministic one. This raises the issue of how such models manifest contextuality, and we provide an explicit example to demonstrate this. In the second half of the paper we consider the issue of finding ontological models with as few ontic states as possible.

S. Aaronson, S. Beigi, A. Drucker, B. Fefferman and P. Shor. The Power of Unentanglement [PS] [PDF], Theory of Computing, 5(1):1-42, 2009. Conference version [PS] [PDF] in Proceedings of IEEE Complexity 2008, pp. 223-236. arXiv:0804.0802.

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? Does QMA(k)=QMA(2) for k≥2? Can QMA(k) protocols be amplified to exponentially small error?

In this paper, we make progress on all of the above questions.

• We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given Õ(√n) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs.
• We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all k≥2.
• We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.

S. Aaronson. The Learnability of Quantum States [PS] [PDF], Proceedings of the Royal Society A463(2088), 2007. quant-ph/0608142.

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 implications for experimental physics, our learning theorem has two applications to quantum computing: first, a new simulation of quantum one-way protocols, and second, the use of trusted classical advice to verify untrusted quantum advice.

S. Aaronson and G. Kuperberg. Quantum Versus Classical Proofs and Advice [PS] [PDF], Theory of Computing 3(7):129-157, 2007. Conference version [PS] [PDF] in Proceedings of IEEE Complexity 2007, pp. 115-128. quant-ph/0604056.

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 oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs Ω(sqrt(2ⁿ/(m+1))) queries to find an n-qubit "marked state" |ψ>, even if given an m-bit classical description of |ψ> together with a quantum black box that recognizes |ψ>. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.

S. Aaronson. QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols [PS] [PDF], in Proceedings of IEEE Complexity 2006. quant-ph/0510230.

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 can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly is contained in PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly is contained in PP/poly and that QMA/rpoly = QMA/poly.

S. Aaronson. Quantum Computing, Postselection, and Probabilistic Polynomial-Time [PS] [PDF], Proceedings of the Royal Society A, 461(2063):3473-3482, 2005. quant-ph/0412187.

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 of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold, and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.

S. Aaronson. Quantum Computing and Hidden Variables [PS] [PDF], Physical Review A 71:032325, March 2005. quant-ph/0408035 and quant-ph/0408119.

This paper initiates the study of hidden variables from a quantum computing perspective. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another, into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list five axioms that we might want such a theory to satisfy, and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we propose a new hidden-variable theory based on network flows. In a second part of the paper, we show 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 particular, under any hidden-variable theory satisfying a reasonable axiom, we could solve the Graph Isomorphism problem in polynomial time, and could search an N-item database using O(N^1/3) queries, as opposed to O(N^1/2) queries with Grover's search algorithm. On the other hand, the N^1/3 bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.

S. Aaronson and D. Gottesman. Improved Simulation of Stabilizer Circuits [PS] [PDF] [Webpage], Physical Review A 70:052328, 2004. quant-ph/0406196.

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. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor-2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely-available program called CHP (CNOT-Hadamard-Phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class ParityL, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any n-qubit stabilizer circuit into a "canonical form" that requires at most O(n²/log n) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of non-stabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.

S. Aaronson. Limitations of Quantum Advice and One-Way Communication [PS] [PDF], Theory of Computing 1:1-28, 2005. Conference version in Proceedings of IEEE Complexity 2004 pp. 320-332 (won the Ron Book Best Student Paper Award). quant-ph/0402095.

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 PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state" that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions.
Second, we construct an oracle relative to which NP is not contained in BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting.
Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.

S. Aaronson. Is Quantum Mechanics An Island In Theoryspace? [PS] [PDF], Proceedings of the Växjö Conference "Quantum Theory: Reconsideration of Foundations" (A. Khrennikov, ed.), 2004. quant-ph/0401062.

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 nontrivial norm-preserving linear maps. Second, if we relax the demand that norm be preserved, we end up with a theory that allows rapid solution of hard computational problems known as PP-complete problems (as well as superluminal signalling). And third, if we restrict amplitudes to be real, we run into a difficulty much simpler than the usual one based on parameter-counting of mixed states.
Note: The computational results in this paper are superseded by "Quantum Computing, Postselection, and Probabilistic Polynomial-Time."

S. Aaronson. Multilinear Formulas and Skepticism of Quantum Computing [PS] [PDF], to appear in SIAM Journal of Computing. Also in STOC 2004, pp. 118-127. Conference version: [PS] [PDF]. quant-ph/0311039.

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 states that can account for all experiments performed to date, but not for Shor's factoring algorithm. We propose as a candidate the set of states expressible by a polynomial number of additions and tensor products. Using a recent lower bound on multilinear formula size due to Raz, we then show that states arising in quantum error-correction require n^{Ω(log n)} additions and tensor products even to approximate, which incidentally yields the first superpolynomial gap between general and multilinear formula size of functions. More broadly, we introduce a complexity classification of pure quantum states, and prove many basic facts about this classification. Our goal is to refine vague ideas about a breakdown of quantum mechanics into specific hypotheses that might be experimentally testable in the near future.

S. Aaronson. Lower Bounds for Local Search by Quantum Arguments [PS] [PDF], Proceedings of ACM STOC 2004, pp. 465-474 (won the Danny Lewin Best Student Paper Award). Also in STOC'04 Special Issue of SIAM Journal on Computing. quant-ph/0307149.

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}ⁿ, we show a lower bound of Ω(2^n/4/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis' quantum adversary method, also yields a lower bound of Ω(2^n/2/n²) on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension greater than 2.

S. Aaronson and A. Ambainis. Quantum Search of Spatial Regions [PS] [PDF], Theory of Computing 1:47-79, 2005. Conference version [PS] [PDF] in Proceedings of IEEE FOCS 2003, pp. 200-209. quant-ph/0303041.

Can Grover's quantum search 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 amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time O(sqrt(n)) for d at least 3, or O(sqrt(n)log^5/2(n)) for d=2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm that works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of `locality' for unitary matrices acting on graphs. As an application of our results, we give an O(sqrt(n))-qubit communication protocol for the disjointness problem, which improves an upper bound of Høyer and de Wolf and matches a lower bound of Razborov.

S. Aaronson. Quantum Certificate Complexity [PS] [PDF], IEEE Conference on Computational Complexity (CCC) 2003, pp. 171-178 (won the Ron Book Best Student Paper Award). Journal version [PS] [PDF] to appear in JCSS Special Issue for Complexity 2003. ECCC TR03-005, quant-ph/0210020.

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 R₀(f) = O(Q₂(f)² Q₀(f) log n) for total f, where R₀, Q₂, and Q₀ are zero-error randomized, bounded-error quantum, and zero-error quantum query complexities respectively. Finally we give asymptotic gaps between the measures, including a total f for which C(f) is superquadratic in QC(f), and a symmetric partial f for which QC(f) = O(1) yet Q₂(f) = Ω(n/log n).

S. Aaronson. Quantum Lower Bound for Recursive Fourier Sampling [PS] [PDF], Quantum Information and Computation 3(2):165-174, 2003. quant-ph/0209060.

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 from optimal. The moral is that the need to "uncompute" garbage can impose a fundamental limit on efficient quantum computation. The proof introduces a new parameter of Boolean functions called the "nonparity coefficient," which might be of independent interest.
Note: I've revised this paper since it appeared in QIC, both to correct an error and to emphasize the need to uncompute. The version here is taken from Chapter 9 of my PhD thesis.

S. Aaronson. Quantum Lower Bound for the Collision Problem [PS] [PDF], Proceedings of ACM STOC 2002, pp. 635-642 (won the C. V. Ramamoorthy Award). Journal version (joint with Y. Shi) in Journal of the ACM 51(4):595-605, 2004. quant-ph/0111102.

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 Ω(n^1/5) on the number of queries needed by a quantum computer to solve this problem with bounded error probability. The best known upper bound is O(n^1/3), but obtaining any lower bound better than Ω(1) was an open problem since 1997. Our proof uses the polynomial method augmented by some new ideas. We also give a lower bound of Ω(n^1/7) for the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Finally we give implications of these results for quantum complexity theory.

(Mostly-)Classical Papers

S. Aaronson. The Equivalence of Sampling and Searching [PS] [PDF], 2010. ECCC TR10-128.

In a sampling problem, we are given an input x∈{0,1}ⁿ, 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∈{0,1}ⁿ, and asked to find a member of a nonempty set A_x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity and algorithmic information theory to show that sampling and search problems are essentially equivalent. More precisely, for any sampling problem S, there exists a search problem R_S such that, if C is any "reasonable" complexity class, then R_S is in the search version of C if and only if S is in the sampling version.

As one application, we show that SampP=SampBQP if and only if FBPP=FBQP: in other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve. A second application is that, assuming a plausible conjecture, there exists a search problem R that can be solved using a simple linear-optics experiment, but that cannot be solved efficiently by a classical computer unless the polynomial hierarchy collapses. That application will be described in a forthcoming paper with Alex Arkhipov on the computational complexity of linear optics.

S. Aaronson. A Counterexample to the Generalized Linial-Nisan Conjecture [PS] [PDF], 2010. ECCC TR10-109.

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 circuits. The original Linial-Nisan Conjecture was recently proved by Braverman; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher.

As a byproduct, our counterexample also implies that Π₂^p⊄P^NP relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the highest levels of PH previously proved separate were NP and coNP.

Finally, our counterexample implies that the famous results of Linial, Mansour, and Nisan, on the structure of AC⁰ functions, cannot be improved in several interesting respects.

S. Aaronson and D. van Melkebeek. A note on circuit lower bounds from derandomization, 2010. ECCC TR10-105.

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.

S. Aaronson and A. Wigderson. Algebrization: A New Barrier in Complexity Theory [PS] [PDF], ACM Transactions on Computing Theory 1(1), 2009. Conference version [PS] [PDF] in Proceedings of ACM STOC'2008, pp. 731-740.

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 is a third barrier to progress on the central questions in complexity theory.

In this paper we present such a barrier, which we call algebraic relativization or algebrization. The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to a low-degree extension of A over a finite field or ring.

We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. First, we show that all known non-relativizing results based on arithmetization -- both inclusions such as IP=PSPACE and MIP=NEXP, and separations such as MA_EXP⊄P/poly -- do indeed algebrize. Second, we show that almost all of the major open problems -- including P versus NP, P versus RP, and NEXP versus P/poly -- will require non-algebrizing techniques. In some cases algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP.

Our second set of results follows from lower bounds in a new model of algebraic query complexity, which we introduce in this paper and which is interesting in its own right. Some of our lower bounds use direct combinatorial and algebraic arguments, while others stem from a surprising connection between our model and communication complexity. Using this connection, we are also able to give an MA-protocol for the Inner Product function with O(√n log n) communication (essentially matching a lower bound of Klauck), as well as a communication complexity conjecture whose truth would imply NL≠NP.

S. Aaronson. Oracles Are Subtle But Not Malicious [PS] [PDF], in Proceedings of IEEE Complexity 2006. cs.CC/0504048.

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 give an oracle relative to which PP has linear-sized circuits, by proving a new lower bound for perceptrons and low-degree threshold polynomials. This oracle settles a longstanding open question, and generalizes earlier results due to Beigel and to Buhrman, Fortnow, and Thierauf. More importantly, it implies the first nonrelativizing separation of "traditional" complexity classes, as opposed to interactive proof classes such as MIP and MA_EXP. For Vinodchandran showed, by a nonrelativizing argument, that PP does not have circuits of size n^k for any fixed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size n^k with quantum advice. To our knowledge, this is the first nontrivial lower bound on quantum circuit size.
Second, we study a beautiful algorithm of Bshouty et al. for learning Boolean circuits in ZPP^NP. We show that the NP queries in this algorithm cannot be parallelized by any relativizing technique, by giving an oracle relative to which ZPP^||NP and even BPP^||NP have linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P=NP. Thus, classes such as ZPP^||NP inhabit a "twilight zone," where we need to distinguish between relativizing and black-box techniques. Our results on this subject have implications for computational learning theory as well as for the circuit minimization problem.

S. Aaronson. The Complexity of Agreement [PS] [PDF]. Conference version [PS] [PDF] in Proceedings of ACM STOC 2005, pp. 634-643. cs.CC/0406061.

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 went unaddressed: first, can the agents reach agreement after a conversation of reasonable length? Second, can the computations needed for that conversation be performed efficiently? This paper answers both questions in the affirmative, thereby strengthening Aumann's original conclusion.
We first show that, for two agents with a common prior to agree within ε about the expectation of a [0,1] variable with high probability over their prior, it suffices for them to exchange order 1/ε² bits. This bound is completely independent of the number of bits n of relevant knowledge that the agents have. We then extend the bound to three or more agents; and we give an example where the economists' "standard protocol" (which consists of repeatedly announcing one's current expectation) nearly saturates the bound, while a new "attenuated protocol" does better. Finally, we give a protocol that would cause two Bayesians to agree within ε after exchanging order 1/ε² messages, and that can be simulated by agents with limited computational resources. By this we mean that, after examining the agents' knowledge and a transcript of their conversation, no one would be able to distinguish the agents from perfect Bayesians. The time used by the simulation procedure is exponential in 1/ε⁶ but not in n.

S. Aaronson. Algorithms for Boolean Function Query Properties [PS] [PDF], SIAM Journal on Computing 32(5):1140-1157, 2003.

We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties given an n-variable function's truth table (of size N=2ⁿ) as input. Our main results are the following:
• O(N^1.585 log N) algorithms for many common properties.
• An O(N^2.322 log N) algorithm for block sensitivity.
• An O(N) algorithm for testing 'quasisymmetry.'
• A notion of a 'tree decomposition' of a Boolean function, proof that the decomposition is unique, and an O(N^1.585 log N) algorithm for finding the decomposition.
• A subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic.
The algorithms discussed have been implemented in a linkable library.

S. Aaronson. Stylometric Clustering: A Comparison of Data-Driven and Syntactic Features [MS Word], manuscript, 2001.

We present evidence that statistics drawn from an automated parser can aid in stylometric analysis. The problem considered is that of clustering a collection of texts by author, without any baseline texts of known authorship. We use a feature based on relative frequencies of grammar rules as computed by an automated parser, the CMU Link Grammar parser. We compare this feature against standard "data-driven" features: letter, punctuation, and function word frequencies, and mean and variance of sentence length. On two corpora -- (1) the Federalist Papers and (2) selections from Twain, Hawthorne, and Melville -- our results indicate that syntactic and data-driven features combined yield accuracy as good as or better than data-driven features alone. We analyze the results using a cluster validity measure that may be of independent interest.

S. Aaronson. Optimal Demand-Oriented Topology for Hypertext Systems [PS] [PDF], Proceedings of ACM SIGIR 1997, pp. 168-177.

This paper proposes an algorithm to aid in the design of hypertext systems. A numerical index is presented for rating the organizational efficiency of hypertexts based on (1) user demand for pages, (2) the relevance of pages to one another, and (3) the probability that users can navigate along hypertext paths without getting lost. Maximizing this index under constraints on the number of links is proven NP-complete, and a genetic algorithm is used to search for the optimal link topology. An experiment with computer users provides evidence that a numerical measure of hypertext efficiency might have practical value.

Surveys and Book Reviews

S. Aaronson. Why Quantum Chemistry Is Hard [HTML] [PS] [PDF], Nature Physics News & Views, 5(10):707-708, 2009.

The burgeoning field of quantum information science is not only about building a working device. Already we can learn a lot by thinking about how computation works under the rule of quantum mechanics.

S. Aaronson. Are Quantum States Exponentially Long Vectors? [PS] [PDF], shorter version in Proceedings of the 2005 Oberwolfach Meeting on Complexity Theory. quant-ph/0507242.

I'm grateful to Oded Goldreich for inviting me to the Oberwolfach meeting. 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.

S. Aaronson. NP-complete Problems and Physical Reality [PS] [PDF], SIGACT News Complexity Theory Column, March 2005. quant-ph/0502072.

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 section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.

S. Aaronson. Is P Versus NP Formally Independent? [PS] [PDF], Bulletin of the EATCS 81, October 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 Zermelo-Fraenkel set theory, it discusses oracle independence; natural proofs; independence results of Razborov, Raz, DeMillo-Lipton, Sazanov, and others; and obstacles to proving P vs. NP independent of strong logical theories. It ends with some philosophical musings on when one should expect a mathematical question to have a definite answer.

S. Aaronson. Book Review: A New Kind of Science [PS] [PDF], Quantum Information and Computation 2(5):410-423, 2002. quant-ph/0206089.

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 fundamental physics. In complexity, we address some of the questions Wolfram raises using standard techniques in theoretical computer science. In physics, we examine Wolfram's proposal for a deterministic model underlying quantum mechanics, with 'long-range threads' to connect entangled particles. We show that this proposal cannot be made compatible with both special relativity and Bell inequality violations.

[Return to home page]