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

(Mostly-)Quantum Papers

S. Aaronson, A. Bouland, L. Chua, and G. Lowther. Psi-Epistemic Theories: The Role of Symmetry [PS] [PDF], 2013. arXiv:1303.2834.

Formalizing an old desire of Einstein, "ψ-epistemic theories" try to reproduce the predictions of quantum mechanics, while viewing quantum states as ordinary probability distributions over underlying objects called "ontic states." Regardless of one's philosophical views about such theories, the question arises of whether one can cleanly rule them out, by proving no-go theorems analogous to the Bell Inequality. In the 1960s, Kochen and Specker (who first studied these theories) constructed an elegant ψ-epistemic theory for Hilbert space dimension d=2, but also showed that any deterministic ψ-epistemic theory must be "measurement contextual" in dimensions 3 and higher. Last year, the topic attracted renewed attention, when Pusey, Barrett, and Rudolph (PBR) showed that any ψ-epistemic theory must "behave badly under tensor product." In this paper, we prove that even without the Kochen-Specker or PBR assumptions, there are no ψ-epistemic theories in dimensions d≥3 that satisfy two reasonable conditions: (1) symmetry under unitary transformations, and (2) "maximum nontriviality" (meaning that the probability distributions corresponding to any two non-orthogonal states overlap). The proof of this result, in the general case, uses some measure theory and differential geometry. On the other hand, we also show the surprising result that without the symmetry restriction, one can construct maximally-nontrivial ψ-epistemic theories in every finite dimension d.

M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. Ralph, and A. G. White. Experimental BosonSampling, to appear in Science. arXiv:1212.2234.

Quantum computers are unnecessary for exponentially-efficient computation or simulation if the Extended Church-Turing thesis---a foundational tenet of computer science---is correct. The thesis would be directly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. Such a task is BosonSampling: obtaining a distribution of n bosons scattered by some linear-optical unitary process. Here we test the central premise of BosonSampling, experimentally verifying that the amplitudes of 3-photon scattering processes are given by the permanents of submatrices generated from a unitary describing a 6-mode integrated optical circuit. We find the protocol to be robust, working even with the unavoidable effects of photon loss, non-ideal sources, and imperfect detection. Strong evidence against the Extended Church-Turing thesis will come from scaling to large numbers of photons, which is a much simpler task than building a universal quantum computer.

S. Aaronson and P. Christiano. Quantum Money from Hidden Subspaces [PS] [PDF], Theory of Computing 9(9):349-401, 2013. Conference version [PS] [PDF] in Proceedings of ACM STOC 2012, pages 41-60. arXiv:1203.4740, ECCC TR12-024.

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 printed it, and (2) cryptographically secure, under a "classical" hardness assumption that has nothing to do with quantum money.

Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the "black-box" version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published).

Even in Wiesner's original setting---quantum money that can only be verified by the bank---we are able to use our techniques to patch a major security hole in Wiesner's scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank.

Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis---matching the original intuition for quantum money, based on the existence of complementary observables.

Our security proofs use a new variant of Ambainis's quantum adversary method, and several other tools that might be of independent interest.

S. Aaronson. A Linear-Optical Proof that the Permanent is #P-Hard [PS] [PDF], Proceedings of the Royal Society A, 467:3393-3405, 2011. ECCC TR11-043, arXiv:1109.1674.

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n-by-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 arguably more intuitive proof of this theorem.

S. Aaronson. Impossibility of Succinct Quantum Proofs for Collision-Freeness [PS] [PDF], Quantum Information and Computation, 12:21-28, 2012. ECCC TR11-001, arXiv:1101.0403.

We show that any quantum algorithm to decide whether a function f:[n]→[n] is a permutation or far from a permutation must make Ω(n^1/3/w) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation. This implies that there exists an oracle A such that SZK^A⊄QMA^A, answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, SZK is not in the counting class A₀PP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.

S. Aaronson and A. Drucker. Advice Coins for Classical and Quantum Computation [PS] [PDF], in Proceedings of ICALP 2011, pages 61-72. ECCC TR11-008, arXiv:1101.5355.

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 can be sensitive to arbitrarily small changes in a coin's bias. This contrasts with classical probabilistic finite automata, whose sensitivity to changes in a coin's bias is bounded by a classic 1970 result of Hellman and Cover.

Despite this finding, we are able to bound the power of advice coins for space-bounded classical and quantum computation. We define the classes BPPSPACE/coin and BQPSPACE/coin, of languages decidable by classical and quantum polynomial-space machines with advice coins. Our main theorem is that both classes coincide with PSPACE/poly. Proving this result turns out to require substantial machinery. We use an algorithm due to Neff for finding roots of polynomials in NC; a result from algebraic geometry that lower-bounds the separation of a polynomial's roots; and a result on fixed-points of superoperators due to Aaronson and Watrous, originally proved in the context of quantum computing with closed timelike curves.

S. Aaronson and A. Arkhipov. The Computational Complexity of Linear Optics [PDF], Theory of Computing 4:143-252, 2013. Conference version [PS] [PDF] in Proceedings of ACM STOC 2011, pages 333-342. ECCC TR10-170, arXiv:1011.3245.

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 the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.

Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation.

Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the Permanent-of-Gaussians Conjecture, which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the Permanent Anti-Concentration Conjecture, which says that |Per(A)|≥√(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application.

This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

S. Aaronson and A. Drucker. A Full Characterization of Quantum Advice [PS] [PDF], in Proceedings of ACM STOC 2010, pages 131-140. 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], in Proceedings of ICS 2011, pages 338-352. 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], in Proceedings of ACM STOC 2010, pages 141-150. 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, pages 229-242.

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], Chicago Journal of Theoretical Computer Science Article 6, 2011. 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, pp. 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, 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, pages 261-273. 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], 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] 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).

Note: If you're interested in the part of this paper dealing with asymptotic separations among C, RC, and bs, then please see some improvements and corrections in a later paper by Avishay Tal.

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 and T. Hance. Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent [PS] [PDF], 2012.

In 2005, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n²/ε²) time, and approximates Per(A) to within ±ε||A||ⁿ additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. Indeed, the existence of Gurvits's algorithm is why, in their recent work on the hardness of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than estimation problems.

In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment---even an outcome involving multiple photons "bunched" in the same mode---at least as well as that probability can be estimated by the experiment itself. (This does not, of course, let us solve the AA sampling problem.) It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest.

Second, we use ε-biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of ε-biased sets to the complex numbers, construct "complex ε-biased sets," then use those sets to derandomize even our generalization of Gurvits's algorithm to the multirow/multicolumn case (again for nonnegative A). Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.

S. Aaronson, B. Aydinlioglu, H. Buhrman, J. Hitchcock, and D. van Melkebeek. A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games, 2010. ECCC TR10-174.

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 C accepts at least a given number b of inputs, and the case where C accepts less than δb inputs for some positive constant δ. If P^NP contains a solution for this promise problem then E^NP requires circuits of size Ω(2ⁿ/n) almost everywhere.

S. Aaronson. The Equivalence of Sampling and Searching [PS] [PDF], in Proceedings of International Computer Science Symposium in Russia (CSR), pp. 1-14, 2011 (won the Best Paper Award). arXiv:1009.5104, 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 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. What makes this nontrivial is that the same R_S works for every C.

As an application, we prove the surprising result 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.

S. Aaronson and D. van Melkebeek. On Circuit Lower Bounds from Derandomization, Theory of Computing 7(1):177-184, 2011. 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. 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 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, pages 340-354. 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], 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], in 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. The Ghost in the Quantum Turing Machine [PDF] [PS], to appear in The Once and Future Turing, edited by S. Barry Cooper and Andrew Hodges, 2013.

In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will. I focus relatively narrowly on a notion that I call "Knightian freedom": a certain kind of in-principle physical unpredictability that goes beyond probabilistic unpredictability. Other, more metaphysical aspects of free will I regard as possibly outside the scope of science.

I examine a viewpoint, suggested independently by Carl Hoefer, Cristi Stoica, and even Turing himself, that tries to find scope for "freedom" in the universe's boundary conditions rather than in the dynamical laws. Taking this viewpoint seriously leads to many interesting conceptual problems. I investigate how far one can go toward solving those problems, and along the way, encounter (among other things) the No-Cloning Theorem, the measurement problem, decoherence, chaos, the arrow of time, the holographic principle, Newcomb's paradox, Boltzmann brains, algorithmic information theory, and the Common Prior Assumption. I also compare the viewpoint explored here to the more radical speculations of Roger Penrose.

The result of all this is an unusual perspective on time, quantum mechanics, and causation, of which I myself remain skeptical, but which has several appealing features. Among other things, it suggests interesting empirical questions in neuroscience, physics, and cosmology; and takes a millennia-old philosophical debate into some underexplored territory.

S. Aaronson. Get Real [PDF] [HTML], Nature Physics News & Views, 8:443–444, 2012.

Do quantum states offer a faithful representation of reality or merely encode the partial knowledge of the experimenter? A new theorem illustrates how the latter can lead to a contradiction with quantum mechanics.

S. Aaronson. Why Philosophers Should Care About Computational Complexity [PS] [PDF], to appear in Computability: Gödel, Turing, Church, and Beyond, edited by B. J. Copeland, C. Posy, and O. Shagrir, MIT Press, 2012. ECCC TR11-108, arXiv:1108.1791.

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 resources (such as time, space, and randomness) needed to solve computational problems---leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume's problem of induction, Goodman's grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.

S. Aaronson. QIP = PSPACE Breakthrough (Technical Perspective) [HTML] [PDF], Communications of the ACM, 53(12):101, December 2010.

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]