Research
Papers and Surveys
(Mostly-)Quantum
Papers
S. Aaronson and S. Ben-David. Sculpting Quantum Speedups, in Proceedings of CCC'2016. ECCC TR15-203, arXiv:1512.04016.
Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. We show that a total function f can be restricted to a promise P such that Q(f|_{P})=O(polylogN) and R(f|_{P})=N^{Ω(1)}, if and only if f has a large number of inputs with large certificate complexity. The proof uses some interesting techniques: for one direction, we introduce new relationships between randomized and quantum query complexity in various settings, and for the other direction, we use a recent result from communication complexity due to Klartag and Regev. We also characterize sculpting for other query complexity measures, such as R(f) vs. R_{0}(f) and R_{0}(f) vs. D(f).
Along the way, we prove some new relationships for quantum query complexity: for example, a nearly quadratic relationship between Q(f) and D(f) whenever the promise of f is small. This contrasts with the recent super-quadratic query complexity separations, showing that the maximum gap between classical and quantum query complexities is indeed quadratic in various settings - just not for total functions!
Lastly, we investigate sculpting in the Turing machine model. We show that if there is any BPP-bi-immune language in BQP, then every language outside BPP can be restricted to a promise which places it in PromiseBQP but not in PromiseBPP. Under a weaker assumption, that some problem in BQP is hard on average for P/poly, we show that every paddable language outside BPP is sculptable in this way.
S. Aaronson, A. Ambainis, J. Iraids, M. Kokainis, and J. Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality, in Proceedings of CCC'2016. arXiv:1511.08682.
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by ε<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by ε' <1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy, and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Ω(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(√n). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from Aaronson and Ambainis, showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^{n}→[-1,1] with O(n^{1-1/2k}) queries.
S. Aaronson, S. Ben-David, and R. Kothari. Separations in Query Complexity Using Cheat Sheets, to appear in Proceedings of ACM STOC'2016. ECCC TR15-175, arXiv:1511.01937.
We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al., to be shown in a unified manner.
S. Aaronson and D. J. Brod. BosonSampling with Lost Photons, 2015. arXiv:1510.05245.
BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here we investigate the complexity of BosonSampling under photon losses---more specifically, the case where an unknown subset of the photons are randomly lost at the sources. We show that, if k out of n photons are lost, then we cannot sample classically from a distribution that is 1/n^{Θ(k)}-close (in total variation distance) to the ideal distribution, unless a BPP^{NP} machine can estimate the permanents of Gaussian matrices in n^{O(k)} time. In particular, if k is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.
Z. Liu, C. Perry, Y. Zhu, D. Koh, and S. Aaronson. Doubly Infinite Separation of Quantum Information and Communication, 2015. arXiv:1507.03546.
We prove the existence of (one-way) communication tasks with a vanishing vs. diverging type of asymptotic gap, which we call "doubly infinite", between quantum information and communication complexities. We do so by showing the following: As the size of the task n increases, the quantum communication complexity of a certain regime of the exclusion game, recently introduced by Perry, Jain, and Oppenheim, scales at least logarithmically in n, while the information cost of a winning quantum strategy may tend to zero. The logarithmic lower bound on the quantum communication complexity is shown to hold even if we allow a small probability of error, although the n-qubit quantum message of the zero-error strategy can then be compressed polynomially. We leave open the problems of whether the quantum communication complexity of the specified regime scales polynomially in n, and whether the gap between quantum and classical communication complexities can be superexponential beyond this regime.
S. Aaronson and A. Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing [PDF], in Proceedings of ACM STOC'2015, pp. 307-316. Conference version [PDF]. arXiv:1411.5729, ECCC TR14-155.
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs ~(√N)/log(N) queries (improving an ~N^{1/4} lower bound of Aaronson). Conversely, we show that this 1 versus ~√N separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N^{1-1/2t})-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus ~N^{1-1/2t} separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation."
S. Aaronson, A. Bouland, J. Fitzsimons, and M. Lee. The Space "Just Above" BQP, 2014. arXiv:1412.6507, ECCC TR14-181.
We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the wavefunction. This (non-physical) model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in O(N^{1/3}) time, but no faster than Ω(N^{1/4}), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so.
Our work is inspired by previous work of Aaronson on the power of sampling the histories of hidden variables. However Aaronson's work contains an error in its proof of the lower bound for search, and hence it is unclear whether or not his model allows for search in logarithmic time. Our work can be viewed as a conceptual simplification of Aaronson's approach, with a provable polynomial lower bound for search.
R. Gross and S. Aaronson. Bounding the Seed Length of Miller and Shi's Unbounded Randomness Expansion Protocol, 2014. arXiv:1410.8019.
Recent randomness expansion protocols have been proposed which are able to generate an unbounded amount of randomness from a finite amount of truly random initial seed. One such protocol, given by Miller and Shi, uses a pair of non-signaling untrusted quantum mechanical devices. These play XOR games with inputs given by the user in order to generate an output. Here we present an analysis of the required seed size, giving explicit upper bounds for the number of initial random bits needed to jump-start the protocol. The bits output from such a protocol are ε-close to uniform even against quantum adversaries. Our analysis yields that for a statistical distance of ε=10^{-1} and ε=10^{-6} from uniformity, the number of required bits is smaller than 225,000 and 715,000, respectively; in general it grows as O(log(1/ε)).
A. Nayebi, S. Aaronson, A. Belovs, and L. Trevisan. Quantum Lower Bound for Inverting a Permutation with Advice, to appear in Quantum Information and Computation 15(11-12):901-913, 2015. ECCC TR14-109, arXiv:1408.3193.
Given a random permutation f:[N]→[N] as a black box and y∈[N], we want to output f^{-1}(y). Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but not on the input y. Classically, there is a data structure of size ~O(S) and an algorithm that with the help of the data structure, given f(x), can invert f in time ~O(T), for every choice of parameters S, T such that ST ≥ N. We prove a quantum lower bound of T^{2}S ≥ ~Ω(εN) for quantum algorithms that invert a random permutation f on an ε fraction of inputs, where T is the number of queries to f and S is the amount of advice. This answers an open question of De et al.
We also give an Ω(√(N/m)) quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit x_{j}, given the ability to query an N-bit string x at any index except the j^{th}, and also given m bits of advice that depend on x but not on j.
J. Barry, D. Barry, and S. Aaronson. Quantum POMDPs Physical Review A 90:032311, 2014. arXiv:1406.2858.
We present quantum observable Markov decision processes (QOMDPs), the quantum analogues of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent’s state is represented as a quantum state and the agent can choose a superoperator to apply. This is similar to the POMDP belief state, which is a probability distribution over world states and evolves via a stochastic matrix. We show that the existence of a policy of at least a certain value has the same complexity for QOMDPs and POMDPs in the polynomial and infinite horizon cases. However, we also prove that the existence of a policy that can reach a goal state is decidable for goal POMDPs
and undecidable for goal QOMDPs.
A. Bouland and S. Aaronson. Any Beamsplitter Generates Universal Quantum Linear Optics [PDF], Physical Review A 89:062316, 2014. arXiv:1310.6718, ECCC TR13-147.
In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m × m unitary transformations (or orthogonal transformations, in the real case) on m ≥ 3 modes. (We prove the same result for any 2-mode real optical gate, and for any 2-mode optical gate combined with a generic phaseshifter.) Experimentally, this means that one does not need tunable beamsplitters or phaseshifters for universality: any nontrivial beamsplitter is universal. Theoretically, it means that one cannot produce "intermediate" models of quantum-optical computation (analogous to the Clifford group for qubits) by restricting the allowed beamsplitters and phaseshifters: there is a dichotomy; one either gets a trivial set or else a universal set. No similar classification theorem for gates acting on qubits is currently known. We leave open the problem of classifying optical gates that act on 3 or more modes.
S. Aaronson and A. Arkhipov. BosonSampling Is Far From Uniform [PS] [PDF], Quantum Information and Computation, vol. 14, no. 15&16, pp. 1383--1423, 2014. arXiv:1309.7460, ECCC TR13-135.
BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random outcome, at least "without detailed a priori knowledge"; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of "a priori knowledge" so strange that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments. However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s mistaken arguments. We prove that, with high probability over a Haar-random matrix A, the BosonSampling distribution induced by A is far from the uniform distribution in total variation distance. More surprisingly, and directly counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three "bonus" results about BosonSampling. First, we report an observation of Fernando Brandao: that one can efficiently sample a distribution that has large entropy and that's indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that FermionSampling is solvable in classical polynomial time, and we reuse techniques from our BosonSampling analysis to characterize random FermionSampling distributions.
S. Aaronson, A. Bouland, L. Chua, and G. Lowther. Psi-Epistemic Theories: The Role of Symmetry [PS] [PDF], Physical Review A 88:032111, 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). This no-go
theorem
holds if the ontic space is either the set of quantum states or the set
of unitaries. 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. Photonic Boson Sampling in a Tunable Circuit, Science 339(6121):794-798, February 2013. 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_{0}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. See also BosonSampling Mathematica notebook by Justin Dove.
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 [PDF], SIAM Journal on Computing 43(3):1131-1183, 2014. Conference version [PS] [PDF] in Proceedings of ACM STOC 2010, pages 131-140. 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_{1},...,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^{0}.
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.
(See also A Note on Oracle Separations for BQP by Lijie Chen, which fixes some mistaken proofs in this paper)
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:
- The problem can be solved with O(log |G|) communication, provided
the subgroup H is normal;
- 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;
- 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_{1},
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_{1}.
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^{n}/(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^{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.
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}^{n},
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^{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.
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_{0}(f) = O(Q_{2}(f)^{2}
Q_{0}(f) log n) for total f, where R_{0}, Q_{2},
and Q_{0} 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_{2}(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
E. Demaine, F. Ma, A. Schvartzman, E. Waingarten, and S. Aaronson. The Fewest Clues Problem [PDF], in Proceedings of FUN'2016.
When analyzing the computational complexity of well-known puzzles, most papers consider the algorithmic challenge of solving a given instance of (a generalized form of) the puzzle. We take a different approach by analyzing the computational complexity of designing a "good" puzzle. We assume a puzzle maker designs part of an instance, but before publishing it, wants to ensure that the puzzle has a unique solution. Given a puzzle, we introduce the FCP (fewest clues problem) version of the problem: Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable? We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari. Solving these puzzles is NP-complete, and we show their FCP versions are Σ_{2}^{P}-complete. Along the way, we show that the FCP versions of 3SAT, 1-in-3SAT, Triangle Partition, Planar 3SAT, and Latin Square are all Σ_{2}^{P}-complete. We show that even problems in P have difficult FCP versions, sometimes even Σ_{2}^{P}-complete, though "closed under cluing" problems are in the (presumably) smaller class NP; for example, FCP 2SAT is NP-complete.
A. Yedidia and S. Aaronson. A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory [PDF], submitted, 2016.
Since the definition of the Busy Beaver function by Radó in 1962, an interesting open question has been the smallest value of n for which BB(n) is independent of ZFC set theory. Is this n approximately 10, or closer to 1,000,000, or is it even larger? In this paper, we show that it is at most 7,910 by presenting an explicit description of a 7,910-state Turing machine Z with 1 tape and a 2-symbol alphabet that cannot be proved to run forever in ZFC (even though it presumably does), assuming ZFC is consistent. The machine is based on work of Harvey Friedman on independent statements involving order-invariant graphs. In doing so, we give the first known upper bound on the highest provable Busy Beaver number in ZFC. To create Z, we develop and use a higher-level language, Laconic, which is much more convenient than direct state manipulation. We also use Laconic to design two Turing machines, G and R, which halt if and only if there are counterexamples to Goldbach's Conjecture and the Riemann Hypothesis, respectively.
S. Aaronson, D. Grier, and L. Schaefer. The Classification of Reversible Bit Operations [PDF], submitted, 2016. ECCC TR15-066, arXiv:1504.05155.
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits.
Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable (though with effort, one can derive from abstract considerations an algorithm that takes triply-exponential time). The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^{n}poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace."
Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Prior to this work, it was not even known that every class was finitely generated. Ruling out the possibility of additional classes, not in the list, requires some arguments about polynomials, lattices, and Diophantine equations.
S. Aaronson and H. Nguyen. Near Invariance of the Hypercube [PS] [PDF], to appear in Israel Journal of Mathematics, 2014. arXiv:1409.7447.
We give an almost-complete description of orthogonal matrices M of order n that "rotate a non-negligible fraction of the Boolean hypercube C_{n}={-1,1}^{n} onto itself," in the sense that Pr_{x∈C_n}[Mx ∈ C_{n}] ≥ n^{-C}, for some positive constant C, where x is sampled uniformly over C_{n}. In particular, we show that such matrices M must be very close to products of permutation and reflection matrices. This result is a step toward characterizing those orthogonal and unitary matrices with large permanents, a question with applications to linear-optical quantum computing.
S. Aaronson, S. M. Carroll, and L. Ouellette. Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton [PDF], 2014.
In contrast to entropy, which increases monotonically, the "complexity" or "interestingness" of closed systems seems intuitively to increase at first and then decrease as equilibrium is approached. For example, our universe lacked complex structures at the Big Bang and will also lack them after black holes evaporate and particles are dispersed. This paper makes an initial attempt to quantify this pattern. As a model system, we use a simple, two-dimensional cellular automaton that simulates the mixing of two liquids ("coffee" and "cream"). A plausible complexity measure is then the Kolmogorov complexity of a coarse-grained approximation of the automaton's state, which we dub the "apparent complexity." We study this complexity measure, and show analytically that it never becomes large when the liquid particles are non-interacting. By contrast, when the particles do interact, we give numerical evidence that the complexity reaches a maximum comparable to the "coffee cup's" horizontal dimension. We raise the problem of proving this behavior analytically.
S. Aaronson, R. Impagliazzo, and D. Moshkovitz. AM with Multiple Merlins [PDF], in Proceedings of Conference on Computational Complexity (CCC), 2014. ECCC TR14-012, arXiv:1401.6848.
We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right.
We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n^{1/2+o(1)} bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n^{(log n)^(1-o(1))} time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games.
In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k)=AM for all k=poly(n). The key to this result is a subsampling theorem for free games, which follows from powerful results by Alon et al. and Barak et al. on subsampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random subgame.
S. Aaronson, A. Ambainis, K. Balodis, and M. Bavarian. Weak Parity [PDF], in Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP), 2014. ECCC TR13-164, arXiv:1312.0036.
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+ε fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries and n/2 quantum queries are needed to compute parity on all inputs. But surprisingly, we give a randomized algorithm for Weak Parity that makes only O(n/log^{0.246}(1/ε)) queries, as well as a quantum algorithm that makes only O(n/√log(1/ε)) queries. We also prove a lower bound of Ω(n/log(1/ε)) in both cases, as well as lower bounds of Ω(log(n)) in the randomized case and Ω(√log(n)) in the quantum case for any ε>0. We show that improving our lower bounds is intimately related to two longstanding open problems about Boolean functions: the Sensitivity Conjecture, and the relationships between query complexity and polynomial degree.
S. Aaronson and T. Hance. Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent [PS] [PDF], Quantum Information and Computation, 14(7-8):541-559, 2014. ECCC TR12-170.
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^{2}/ε^{2}) time, and approximates Per(A) to within ±ε||A||^{n}
additive error. A major advantage of Gurvits's algorithm is that it
works for arbitrary matrices, not just for nonnegative matrices. 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.
F. Mota, S. Aaronson, L. Antunes, and A. Souto. Sophistication as Randomness Deficiency [PDF], Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science Volume 8031, pp. 172-181, 2013.
The sophistication of a string measures how much structural information it contains. We introduce naive sophistication, a variant of sophistication based on randomness deficiency. Naive sophistication measures the minimum number of bits needed to specify a set in which the string is a typical element. Thanks to Vereshchagin and Vitányi, we know that sophistication and naive sophistication are equivalent up to low order terms. We use this to relate sophistication to lossy compression, and to derive an alternative formulation for busy beaver computational depth.
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}/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). Journal version to appear in Theory of Computing Systems, 2014. arXiv:1009.5104, ECCC TR10-128.
In a sampling problem, we are given an input x∈{0,1}^{n}, and asked to sample approximately from a probability distribution D_{x} over poly(n)-bit strings. In a search problem, we are given an input x∈{0,1}^{n}, 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 Π_{2}^{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^{0} 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/ε^{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 ε after exchanging order 1/ε^{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/ε^{6} 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^{n}) 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. Quantum Machine Learning Algorithms: Read the Fine Print [PDF], Nature Physics 11:291-293, 2015.
New quantum algorithms promise exponential speedup for machine learning, clustering, and finding patterns in big data. But in order to achieve real speedup, we need to delve into the details.
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, 2016.
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], pp. 261-328 in Computability: Turing, Gödel, Church, and Beyond, edited by B. J. Copeland, C. Posy, and O. Shagrir, MIT Press, 2013. 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]