Search

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 in AC0. 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.

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 \in 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} \cdot \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} \cdot \log p)$ communication, where $d_{\max}$ is the maximum of the dimensions of the irreducible $\F_p$-representations of $G$.

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., Comment: 15 pages

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which they are different. 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 in ZQEXP., Comment: 9 pages. To appear in Quantum Information & Computation

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. First, we give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n)) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs. Second, 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. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one., Comment: Several errors fixed; based amplification result on "Weak Additivity Conjecture" rather than now-falsified Additivity Conjecture; added some new observations due to F. Brandao. To appear in Theory of Computing

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., Comment: Replaces previous paper of the same name with substantial new content. New author added and almost all previous open problems answered

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 communication protocols, and second, the use of trusted classical advice to verify untrusted quantum advice., Comment: 30 pages; added discussion of adaptive measurements, moved proofs to appendix, and corrected various minor errors

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 $\Omega(\sqrt{2^n/(m+1)})$ queries to find an $n$-qubit "marked state" $\lvert\psi\rangle$, even if given an $m$-bit classical description of $\lvert\psi\rangle$ together with a quantum black box that recognizes $\lvert\psi\rangle$. 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., Comment: 20 pages, now includes a definition of an explicit group that is in the journal version

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., Comment: 13 pages. Final version to appear in Complexity 2006; fills in some gaps in the proofs

I'm grateful to Oded Goldreich for inviting me to the 2005 Oberwolfach Meeting on Complexity Theory. In this extended abstract, which is based on a talk that I gave there, I demonstrate that gratitude by explaining why Goldreich's views about quantum computing are wrong., Comment: 5 pages. No new results, just informal spouting about old ones

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., Comment: 20 pages, 1 figure

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., Comment: 23 pages, minor corrections

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., Comment: 8 pages, 1 figure. Supersedes the computational results in quant-ph/0401062

More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which., Comment: UC Berkeley PhD thesis, 258 pages. Some minor errors fixed

This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom called "indifference to the identity," we could solve the Graph Isomorphism and Approximate Shortest Vector problems in polynomial time, as well as an oracle problem that is known to require quantum exponential time. We could also 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., Comment: 14 pages. Together with Part I (quant-ph/0408035), subsumes the earlier paper quant-ph/0205059. Can be read independently of Part I

This paper initiates the study of hidden variables from the discrete, abstract perspective of quantum computing. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps 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 seven 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 construct a new hidden-variable theory that is both robust to small perturbations and indifferent to the identity operation, by exploiting an unexpected connection between unitary matrices and network flows. We also analyze previous hidden-variable theories of Dieks and Schrodinger in terms of our axioms. In a companion paper, we will show that actually sampling the history of a hidden variable under reasonable axioms is at least as hard as solving the Graph Isomorphism problem; and indeed is probably intractable even for quantum computers., Comment: 19 pages, 1 figure. Together with a companion paper to appear, subsumes the earlier paper "Quantum Computing and Dynamical Quantum Models" (quant-ph/0205059)

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 epsilon about the expectation of a [0,1] variable with high probability over their prior, it suffices for them to exchange order 1/epsilon^2 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 epsilon after exchanging order 1/epsilon^2 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/epsilon^6 but not in n., Comment: 27 pages, 4 figures

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^2/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., Comment: 15 pages. Final version with some minor updates and corrections. Software at http://www.scottaaronson.com/chp

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 $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where $\mathsf{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 $\mathsf{NP}\not \subset \mathsf{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. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC)., Comment: Published in Theory of Computing, Volume 1 (2005), Article 1; Received: June 29, 2004, Published: February 9, 2005

This recreational paper investigates what happens if we change quantum mechanics in several ways. The main results are as follows. First, if we replace the 2-norm by some other p-norm, then there are 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 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., Comment: 9 pages, minor corrections

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 set of quantum states that can account for all experiments performed to date, but not for Shor's factoring algorithm. We investigate 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^{Omega(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., Comment: Journal version, extensively revised and expanded. Points out connections among tree size, error correction, and persistence of entanglement

The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube {0,1}^n, we show a lower bound of Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis' quantum adversary method, also yields a lower bound of Omega(2^{n/2}/n^2) 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., Comment: 20 pages, 2 figures

Can Grover's algorithm speed up search of a physical region - for example a 2-D grid of size sqrt(n) by sqrt(n)? The problem is that sqrt(n) time seems to be needed for each query, just to move 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 n)^(3/2)) 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 Hoyer and de Wolf and matches a lower bound of Razborov., Comment: 27 pages. New revisions, for example to the disjointness protocol. To appear in Theory of Computing

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 R0(f) = O(Q2(f)^2 Q0(f) log n) for total f, where R0, Q2, and Q0 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 Q2(f) = Omega(n/log n)., Comment: 9 pages

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., Comment: 8 pages. Revised since appearing in QIC, both to correct an error in the definition of the nonparity coefficient and to emphasize the need to uncompute

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 violation., Comment: Revised version. 14 pages, to appear in Quantum Information & Computation, September 2002

A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model yields a distribution over classical histories of a quantum state. We study what can be computed by sampling from that distribution, i.e., by examining an observer's entire history. We show that, relative to an oracle, one can solve problems in polynomial time that are intractable even for quantum computers; and can search an N-element list in order N^{1/3} steps (though not fewer)., Comment: 6 pages, submitted to PRL

The collision problem is to decide whether a function X:{1,..,n}->{1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Theta(n^{1/5}) on the number of 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 Theta(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 Theta(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., Comment: 10 pages plus 4 page appendix, no figures. Submitted to STOC'2002

We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585 log N) algorithm for `tree decomposition,' and an O(N) algorithm for `quasisymmetry.' These algorithms are based on new insights into the structure of Boolean functions that may be of independent interest. We also give a subexponential-time algorithm for the space-bounded quantum query complexity of a Boolean function. To prove this algorithm correct, we develop a theory of limited-precision representation of unitary operators, building on work of Bernstein and Vazirani., Comment: 13 pages, no figures, earlier version submitted to SIAM J. Comp

In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting., Comment: Withdrawn. The results in the paper only work for a certain subclass of Boolean functions, in which block sensitivity has properties similar to those of ordinary sensitivity. They don't work in general