Transcript The Power of Quantum Advice

The Power of Quantum Advice
Scott Aaronson
Andrew Drucker
Freeze-Dried Computation
Motivating Question: How much useful computational work
can one “store” in a quantum state, for later retrieval?
If quantum states are exponentially large objects, then possibly
a huge amount!
Yet we also know that quantum states have no more “generalpurpose storage capacity” than classical strings of the same size
Cast of Characters
BQP/qpoly is the class of problems solvable in quantum
polynomial time, with the help of polynomial-size “quantum
advice states”
Formally: a language L is in BQP/qpoly if there exists a polynomial
time quantum algorithm A, as well as quantum advice states {|n}n
on poly(n) qubits, such that for every input x of size n, A(x,|n)
decides whether or not xL with error probability at most 1/3
YQP (“Yoda Quantum Polynomial-Time”) is the
same, except we also require that for every alleged
advice state , A(x,) outputs either the right
answer or “FAIL” with probability at least 2/3
BQP  YQP  QMA  BQP/qpoly
QUANTUM ADVICE IS POWERFUL
Watrous 2000: For any fixed, finite black-box group Gn and
subgroup Hn≤Gn, deciding membership in Hn is in BQP/qpoly
The quantum advice state is just an equal superposition |Hn over
the elements of Hn
We don’t know how to solve the same problem in BQP/poly
A.-Kuperberg 2007: There exists a “quantum oracle”
separating BQP/qpoly from BQP/poly
NO IT ISN’T
A. 2004: BQP/qpoly  PP/poly = PostBQP/poly
Quantum advice can be simulated by classical advice, combined with
postselection on unlikely measurement outcomes
A. 2006: HeurBQP/qpoly = HeurYQP/poly
Trusted quantum advice can be simulated on most inputs by trusted
classical advice combined with untrusted quantum advice
New Result: BQP/qpoly = YQP/poly
Trusted quantum advice is equivalent in power to trusted
classical advice combined with untrusted quantum advice.
(“Quantum states never need to be trusted”)
FOR THE PHYSICISTS
Given an n-qubit state  and parameters m,, there exists a
local Hamiltonian H on poly(n,m,1/) qubits (e.g., a sum of 2qubit interactions) for which the following holds:
For any ground state | of H, and any binary measurement E
on  performed by a circuit with ≤m gates, there’s an efficient
measurement f(E) that we can perform on | such that
 f E    TrE    .
What Does It Mean?
Preparing quantum advice states is no harder than preparing
ground states of local Hamiltonians
This explains a once-mysterious relationship between
quantum proofs and quantum advice: efficient
preparability of ground states would imply both
QMA=QCMA and BQP/qpoly=BQP/poly
“Quantum Karp-Lipton Theorem”: NP-complete problems are
not efficiently solvable using quantum advice, unless some
uniform complexity classes collapse unexpectedly
QCMA/qpoly  QMA/poly: classical proofs and quantum advice
can be simulated with quantum proofs and classical advice
PSPACE/poly
A.’06
QMA/qpoly
PP/poly
QMA/poly
This work
PP
QCMA/qpoly
BQP/qpoly
=YQP/poly
QCMA/poly
QMA
BQP/poly
YQP
QCMA
BQP
Minimax
Theorem
Safe
Winnowing
Lemma
Circuit Learning
(Bshouty et al.)
Real MajorityCertificates Lemma
LOCAL HAMILTONIANS is
QMA-complete
(Kitaev)
Covering Lemma
(Alon et al.)
Learning of pConcept Classes
(Bartlett & Long)
MajorityCertificates
Lemma
Cook-Levin Theorem
Holevo’s Theorem
Random Access
Code Lower Bound
(Ambainis et al.)
Fat-Shattering Bound
(A.’06)
QMA=QMA+
(Aharonov & Regev)
HeurBQP/qpoly=HeurYQP/poly
(A.’06)
BQP/qpoly=YQP/poly
Quantum advice no harder
than ground state preparation
Used as lemma
Generalizes
Intuition: We’re given a black box (think: quantum state)
x
f
f(x)
that computes some Boolean function f:{0,1}n{0,1} belonging
to a “small” set S (meaning, of size 2poly(n)). Someone wants to
prove to us that f equals (say) the all-0 function, by having us
check a polynomial number of outputs f(x1),…,f(xm).
This is trivially impossible!
But … what if we get 3
black boxes, and are
allowed to simulate f=f0 by
taking the point-wise
MAJORITY of their outputs?
f0
f1
f2
f3
f4
f5
x1
0
1
0
0
0
0
x2
0
0
1
0
0
0
x3
0
0
0
1
0
0
x4
0
0
0
0
1
0
x5
0
0
0
0
0
1
Majority-Certificates Lemma
Definitions: A certificate is a partial Boolean function
C:{0,1}n{0,1,*}. A Boolean function f:{0,1}n{0,1} is
consistent with C, if f(x)=C(x) whenever C(x){0,1}. The size of
C is the number of inputs x such that C(x){0,1}.
Lemma: Let S be a set of Boolean functions f:{0,1}n{0,1}, and
let f*S. Then there exist m=O(n) certificates C1,…,Cm, each of
size k=O(log|S|), such that
(i) Some fiS is consistent with each Ci, and
(ii) If fiS is consistent with Ci for all i, then
MAJ(f1(x),…,fm(x))=f*(x) for all x{0,1}n.
Proof Idea
By symmetry, we can assume f* is the all-0 function. Consider a
two-player, zero-sum matrix game:
Bob picks an input x{0,1}n
The lemma follows from this claim! Just choose
certificates C1,…,Cm independently from Alice’s winning
Alice picks
a certificate
distribution.
Then by a Chernoff bound, almost certainly
C ofMAJ(f
size k1(x),…,f
consistent
m(x))=0 for all f1,…,fm consistent with C1,…,Cm
with someand
fSall inputs x{0,1}n. So clearly there exist
respectively
C1,…,Cm with this property.
Alice wins this game if f(x)=0 for all fS consistent with C.
Crucial Claim: Alice has a mixed strategy that lets her win
>90% of the time.
Proof of Claim
Use the Minimax Theorem! Given a distribution D over x, it’s
enough to create a fixed certificate C such that
1
Pr f consistent with C s.t. f x   1  .
xD
10
Stage I: Choose x1,…,xt independently from D, for some
t=O(log|S|). Then with high probability, requiring
f(x1)=…=f(xt)=0 kills off every fS such that
1
Pr  f  x   1  .
xD
10
Stage II: Repeatedly add a constraint f(xi)=bi that kills at least
half the remaining functions. After ≤ log2|S| iterations, we’ll
have winnowed S down to just a single function fS.
“Lifting” the Lemma to Quantumland
Boolean Majority-Certificates
BQP/qpoly=YQP/poly Proof
Set S of Boolean functions
Set S of p(n)-qubit mixed states
“True” function f*S
“True” advice state |n
Other functions f1,…,fm
Other states 1,…,m
Certificate Ci to isolate fi
Measurement Ei to isolate I
New Difficulty
Solution
The class of p(n)-qubit quantum states is
Result of A.’06 on learnability of quantum
infinitely large! And even if we discretize it, it’s states (building on Ambainis et al. 1999)
still doubly-exponentially large
Instead of Boolean functions f:{0,1}n{0,1},
now we have real functions f:{0,1}n[0,1]
representing the expectation values
Learning theory has tools to deal with
this: fat-shattering dimension, -covers…
(Alon et al. 1997)
How do we verify a quantum witness without
destroying it?
QMA=QMA+ (Aharonov & Regev 2003)
What if a certificate asks us to verify Tr(E)≤a,
but Tr(E) is “right at the knife-edge”?
“Safe Winnowing Lemma”
Theorem: BQP/qpoly = YQP/poly.
Proof Sketch: YQP/poly  BQP/qpoly is immediate. For the
other direction, let LBQP/qpoly. Let M be a quantum
algorithm that decides L using advice state |n. Define
f  x : PrM x,   accepts
Let S = {f : }. Then S has “fat-shattering dimension” at most
poly(n), by A.’06. So we can apply a real analogue of the
Majority-Certificates Lemma to S. This yields certificates
C1,…,Cm (for some m=poly(n)), such that any states 1,…,m
consistent with C1,…,Cm respectively satisfy


1
f 1 x     f  m x   f  n
m
n
x   
for all x{0,1}n (regardless of entanglement). To check the Ci’s,
we use the “QMA+ super-verifier” of Aharonov & Regev.
Promised Application to “Physics”
By Kitaev et al., we know LOCAL HAMILTONIANS is QMA-complete.
Furthermore, in their reduction, the witness is a “history state”
1
 :
T
T
t
t 1
t
Measuring this state yields the original QMA witness |1 with
(1/poly(n)) probability. Hence |1 can be recovered from
 poly  n 
 ' : 
So given any language LBQP/qpoly=YQP/poly, we can use the
Kitaev et al. reduction to get a local Hamiltonian H whose
unique ground state is |’. We can then use |’ to recover
the YQP witness |, and thereby decide L
Quantum Karp-Lipton Theorem
Karp-Lipton 1982: If NP  P/poly, then coNPNP = NPNP.
Our quantum analogue:
If NP  BQP/qpoly, then coNPNP  QMAPromiseQMA.
Proof Idea: A coNPNP statement has the form x y R(x,y).
By the hypothesis and BQP/qpoly = YQP/poly, there exists an
advice string s, such that any quantum state  consistent with s
lets us solve NP problems (and some such  is consistent).
In QMAPromiseQMA, first guess an s that’s consistent with some
state . Then use the oracle to search for an x and  such that,
if  is consistent with s, then R(x,Q(x,)) holds, where Q is a
quantum algorithm that searches for a y such that R(x,y).
A Theory of Isolatability
We can generalize the majority-certificates idea well beyond
what we have any application for
We study the following abstract question, inspired by
computational learning theory:
Which classes of functions C are “isolatable”—in the sense
that for any fC, one can give a small number of conditions
such that any f1,…,fmC satisfying the conditions can be
used to compute f efficiently on all inputs?
Another application of the Majority-Certificates Lemma: it
substantially simplifies the proof that
BQPSPACE/coin = PSPACE/poly
Although this work closes off a chapter in the quantum advice
story, there are still
Open Problems
Find other applications of the majority-certificates technique
Circuit complexity? Communication complexity? Learning
theory? Quantum information?
Is the dependence on n, log|S|, and 1/ optimal?
Improve QMA/qpoly  PSPACE/poly to QMA/qpoly  P#P/poly
Prove a classical oracle separation between BQP/poly and
BQP/qpoly=YQP/poly