
Blind delegation protocols allow a client to delegate a computation to a
server so that the server learns nothing about the input to the computation
apart from its size. For the specific case of quantum computation we know that
blind delegation protocols can achieve informationtheoretic security. In this
paper we prove, provided certain complexitytheoretic conjectures are true,
that the power of informationtheoretically secure blind delegation protocols
for quantum computation (ITSBQC protocols) is in a number of ways constrained.
In the first part of our paper we provide some indication that ITSBQC
protocols for delegating $\sf BQP$ computations in which the client and the
server interact only classically are unlikely to exist. We first show that
having such a protocol with $O(n^d)$ bits of classical communication implies
that $\mathsf{BQP} \subset \mathsf{MA/O(n^d)}$. We conjecture that this
containment is unlikely by providing an oracle relative to which $\mathsf{BQP}
\not\subset \mathsf{MA/O(n^d)}$. We then show that if an ITSBQC protocol
exists with polynomial classical communication and which allows the client to
delegate quantum sampling problems, then there exist nonuniform circuits of
size $2^{n  \mathsf{\Omega}(n/log(n))}$, making polynomiallysized queries to
an $\sf NP^{NP}$ oracle, for computing the permanent of an $n \times n$ matrix.
The second part of our paper concerns ITSBQC protocols in which the client and
the server engage in one round of quantum communication and then exchange
polynomially many classical messages. First, we provide a complexitytheoretic
upper bound on the types of functions that could be delegated in such a
protocol, namely $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$. Then, we show that
having such a protocol for delegating $\mathsf{NP}$hard functions implies
$\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}$.

Suppose we have many copies of an unknown $n$qubit state $\rho$. We measure
some copies of $\rho$ using a known twooutcome measurement $E_{1}$, then other
copies using a measurement $E_{2}$, and so on. At each stage $t$, we generate a
current hypothesis $\sigma_{t}$ about the state $\rho$, using the outcomes of
the previous measurements. We show that it is possible to do this in a way that
guarantees that $\operatorname{Tr}(E_{i} \sigma_{t}) 
\operatorname{Tr}(E_{i}\rho) $, the error in our prediction for the next
measurement, is at least $\varepsilon$ at most $\operatorname{O}\!\left(n /
\varepsilon^2 \right) $ times. Even in the "nonrealizable" settingwhere
there could be arbitrary noise in the measurement outcomeswe show how to
output hypothesis states that do significantly worse than the best possible
states at most $\operatorname{O}\!\left(\sqrt {Tn}\right) $ times on the first
$T$ measurements. These results generalize a 2007 theorem by Aaronson on the
PAClearnability of quantum states, to the online and regretminimization
settings. We give three different ways to prove our resultsusing convex
optimization, quantum postselection, and sequential fatshattering
dimensionwhich have different advantages in terms of parameters and
portability.

In the near future, there will likely be specialpurpose quantum computers
with 4050 highquality qubits. This paper lays general theoretical foundations
for how to use such devices to demonstrate "quantum supremacy": that is, a
clear quantum speedup for some task, motivated by the goal of overturning the
Extended ChurchTuring Thesis as confidently as possible. First, we study the
hardness of sampling the output distribution of a random quantum circuit, along
the lines of a recent proposal by the the Quantum AI group at Google. We show
that there's a natural hardness assumption, which has nothing to do with
sampling, yet implies that no efficient classical algorithm can pass a
statistical test that the quantum sampling procedure's outputs do pass.
Compared to previous work, the central advantage is that we can now talk
directly about the observed outputs, rather than about the distribution being
sampled. Second, in an attempt to refute our hardness assumption, we give a new
algorithm, for simulating a general quantum circuit with n qubits and m gates
in polynomial space and m^O(n) time. We then discuss why this and other known
algorithms fail to refute our assumption. Third, resolving an open problem of
Aaronson and Arkhipov, we show that any strong quantum supremacy theoremof
the form "if approximate quantum sampling is classically easy, then PH
collapses"must be nonrelativizing. Fourth, refuting a conjecture by Aaronson
and Ambainis, we show that the Fourier Sampling problem achieves a constant
versus linear separation between quantum and randomized query complexities.
Fifth, we study quantum supremacy relative to oracles in P/poly. Previous work
implies that, if OWFs exist, then quantum supremacy is possible relative to
such oracles. We show that some assumption is needed: if SampBPP=SampBQP and NP
is in BPP, then quantum supremacy is impossible relative to such oracles.

Inspired by connections to two dimensional quantum theory, we define several
models of computation based on permuting distinguishable particles (which we
call balls), and characterize their computational complexity. In the quantum
setting, we find that the computational power of this model depends on the
initial input states. More precisely, with a standard basis input state, we
show how to approximate the amplitudes of this model within additive error
using the model DQC1 (the class of problems solvable with one clean qubit),
providing evidence that the model in this case is weaker than universal quantum
computing. However, for specific choices of input states, the model is shown to
be universal for BQP in an encoded sense. We use representation theory of the
symmetric group to partially classify the computational complexity of this
model for arbitrary input states. Interestingly, we find some input states
which yield a model intermediate between DQC1 and BQP. Furthermore, we consider
a restricted version of this model based on an integrable scattering problem in
1+1 dimensions. We show it is universal under postselection, if we allow
intermediate destructive measurements and specific input states. Therefore, the
existence of any classical procedure to sample from the output distribution of
this model within multiplicative error implies collapse of polynomial hierarchy
to its third level. Finally, we define a classical version of this model in
which one can probabilistically permute balls. We find this yields a complexity
class which is intermediate between L and BPP. Moreover, we find a
nondeterministic version of this model is NPcomplete.

We ask, and answer, the question of what's computable by Turing machines
equipped with time travel into the past: that is, closed timelike curves or
CTCs (with no bound on their size). We focus on a model for CTCs due to
Deutsch, which imposes a probabilistic consistency condition to avoid
grandfather paradoxes. Our main result is that computers with CTCs can solve
exactly the problems that are Turingreducible to the halting problem, and that
this is true whether we consider classical or quantum computers. Previous work,
by Aaronson and Watrous, studied CTC computers with a polynomial size
restriction, and showed that they solve exactly the problems in PSPACE, again
in both the classical and quantum cases.
Compared to the complexity setting, the main novelty of the computability
setting is that not all CTCs have fixedpoints, even probabilistically. Despite
this, we show that the CTCs that do have fixedpoints suffice to solve the
halting problem, by considering fixedpoint distributions involving infinite
geometric series. The tricky part is to show that even quantum computers with
CTCs can be simulated using a Halt oracle. For that, we need the Riesz
representation theorem from functional analysis, among other tools.
We also study an alternative model of CTCs, due to Lloyd et al., which uses
postselection to "simulate" a consistency condition, and which yields BPP_path
in the classical case or PP in the quantum case when subject to a polynomial
size restriction. With no size limit, we show that postselected CTCs yield only
the computable languages if we impose a certain finiteness condition, or all
languages nonadaptively reducible to the halting problem if we don't.

These are lecture notes from a weeklong course in quantum complexity theory
taught at the Bellairs Research Institute in Barbados, February 2125, 2016.
The focus is quantum circuit complexityi.e., the minimum number of gates
needed to prepare a given quantum state or apply a given unitary
transformationas a unifying theme tying together several topics of recent
interest in the field. Those topics include the power of quantum proofs and
advice states; how to construct quantum money schemes secure against
counterfeiting; and the role of complexity in the blackhole information
paradox and the AdS/CFT correspondence (through connections made by
HarlowHayden, Susskind, and others). The course was taught to a mixed audience
of theoretical computer scientists and quantum gravity / string theorists, and
starts out with a crash course on quantum information and computation in
general.

We show an equivalence between 1query quantum algorithms and representations
by degree2 polynomials. Namely, a partial Boolean function $f$ is computable
by a 1query quantum algorithm with error bounded by $\epsilon<1/2$ iff $f$ can
be approximated by a degree2 polynomial with error bounded by $\epsilon'<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
blockmultilinear polynomials recently introduced by Aaronson and Ambainis
(STOC'2015, arxiv:1411.5729).
We also show two results for polynomials of higher degree. First, there is a
total Boolean function which requires $\tilde{\Omega}(n)$ quantum queries but
can be represented by a blockmultilinear polynomial of degree
$\tilde{O}(\sqrt{n})$. Thus, in the general case (for an arbitrary number of
queries), blockmultilinear 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 blockmultilinear) are equivalent. As a
consequence, we solve an open problem of Aaronson and Ambainis, showing that
one can estimate the value of any bounded degree$k$ polynomial $p:\{0, 1\}^n
\rightarrow [1, 1]$ with $O(n^{1\frac{1}{2k}})$ queries.

Since the definition of the Busy Beaver function by Rado 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,910state Turing machine Z
with 1 tape and a 2symbol alphabet that cannot be proved to run forever in ZFC
(even though it presumably does), assuming ZFC is consistent. The machine is
based on the work of Harvey Friedman on independent statements involving
orderinvariant 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
higherlevel language, Laconic, which is much more convenient than direct state
manipulation. We also use Laconic to design two Turing machines, G and R, that
halt if and only if there are counterexamples to Goldbach's Conjecture and the
Riemann Hypothesis, respectively.

We prove the existence of (oneway) communication tasks with a subconstant
versus superconstant asymptotic gap, which we call "doubly infinite," between
their quantum information and communication complexities. We do so by studying
the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for
which there exist instances where the quantum information complexity tends to
zero as the size of the input $n$ increases. By showing that the quantum
communication complexity of these games scales at least logarithmically in $n$,
we obtain our result. We further show that the established lower bounds and
gaps still hold even if we allow a small probability of error. However in this
case, the $n$qubit quantum message of the zeroerror strategy can be
compressed polynomially.

Given a problem which is intractable for both quantum and classical
algorithms, can we find a subproblem 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(polylog(N)) and R(f_P)=N^{Omega(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 superquadratic 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 BPPbiimmune 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.

We show a power 2.5 separation between boundederror 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.

BosonSampling is an intermediate model of quantum computation where
linearoptical 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
errorcorrection 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 lossesmore 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^{\Theta(k)}$close (in total
variation distance) to the ideal distribution, unless a
$\text{BPP}^{\text{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.

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 reversiblecomputing 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 lineartime 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. The theorem also implies that any nbit 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 nondegenerate 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 nbit
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 ControlledNOT 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. Ruling out the possibility of
additional classes, not in the list, requires some arguments about polynomials,
lattices, and Diophantine equations.

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$,
we want to output $x = f^{1}(y)$. Supplementary to our input, we are given
classical advice in the form of a precomputed data structure; this advice can
depend on the permutation but \emph{not} on the input $y$. Classically, there
is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help
of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for
every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a
quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum
algorithms that invert a random permutation $f$ on an $\epsilon$ 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 a $\Omega(\sqrt{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$.

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 (nonphysical) 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 Nelement list in $\tilde O$(N^{1/3}) time, but no faster than
{\Omega}(N^{1/4}), and hence cannot solve NPhard 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.

We achieve essentially the largest possible separation between quantum and
classical query complexities. We do so using a propertytesting 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
~sqrt(N)/log(N) queries (improving an ~N^{1/4} lower bound of Aaronson).
Conversely, we show that this 1 versus ~sqrt(N) separation is optimal: indeed,
any tquery quantum algorithm whatsoever can be simulated by an
O(N^{11/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^{11/2t} separation for all t. As a bonus, we show that this
generalization is BQPcomplete. This yields what's arguably the simplest
BQPcomplete problem yet known, and gives a second sense in which Forrelation
"captures the maximum power of quantum computation."

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
nonsignaling 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 jumpstart the protocol. The bits output from
such a protocol are $\varepsilon$close to uniform even against quantum
adversaries. Our analysis yields that for a statistical distance of
$\varepsilon=10^{1}$ and $\varepsilon=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\frac{1}{\varepsilon})$.

We give an almostcomplete description of orthogonal matrices $M$ of order
$n$ that "rotate a nonnegligible fraction of the Boolean hypercube
$C_n=\{1,1\}^n$ onto itself," in the sense that $$P_{x\in C_n}(Mx\in C_n) \ge
n^{C},\mbox{ 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 linearoptical quantum computing.

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.

In 1994, Reck et al. showed how to realize any unitary transformation on a
single photon 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 unitary transformations (or orthogonal transformations, in
the real case) on the singlephoton subspace with m>=3 modes. (We prove the
same result for any twomode real optical gate, and for any twomode 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 for linear optics. Theoretically, it means
that one cannot produce "intermediate" models of linear 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 three or more modes.

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, twodimensional
cellular automaton that simulates the mixing of two liquids ("coffee" and
"cream"). A plausible complexity measure is then the Kolmogorov complexity of a
coarsegrained 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 noninteracting. 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.

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 blackbox 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 7th root of the classical randomized
query complexity. (An earlier version of this paper gave the 9th root.) This
resolves a conjecture of Watrous from 2002.
Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al.
(2006), we conjecture that every bounded lowdegree polynomial has a "highly
influential" variable. Assuming this conjecture, we show that every Tquery
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.

We introduce and study a new model of interactive proofs: AM(k), or
ArthurMerlin with k noncommunicating Merlins. Unlike with the betterknown
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 polynomialsize alphabet must take n^{(log n)^{1o(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 quasipolynomialtime 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 logarithmicsized random subgame.

We study the query complexity of Weak Parity: the problem of computing the
parity of an nbit input string, where one only has to succeed on a 1/2+eps
fraction of input strings, but must do so with high probability on those inputs
where one does succeed. It is wellknown 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/eps)) queries, as well as a quantum algorithm that makes only
O(n/sqrt(log(1/eps))) queries. We also prove a lower bound of
Omega(n/log(1/eps)) in both cases; and using extremal combinatorics, prove
lower bounds of Omega(log n) in the randomized case and Omega(sqrt(log n)) in
the quantum case for any eps>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.

We prove the following surprising result: given any quantum state rho on n
qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of
twoqubit interactions), such that any ground state of H can be used to
simulate rho 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 realvalued concept classes, a
result of Aaronson on the learnability of quantum states, and a result of
Aharonov and Regev on "QMA+ superverifiers"  and also creating some new
ones. The main new tool is a socalled majoritycertificates 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
in S can be expressed as the pointwise majority of m=O(n) functions f1,...,fm
in S, such that each fi is the unique function in S compatible with O(logS)
input/output constraints.