Transcript The Power of Quantum Advice

A Full Characterization 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, from Holevo’s Theorem, that quantum states
have no more “general-purpose 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  PostBQP/poly  P#P/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”)
“PHYSICS” IMPLICATION:
Given any n-qubit state , there exists a local Hamiltonian H
(indeed, a sum of 2D nearest-neighbor interactions) such that:
For any ground state | of H, and measuring circuit E with ≤m
gates, there’s an efficient measuring circuit E’ such that
 E '   TrE    .
Furthermore, H is on poly(n,m,1/) qubits.
Implication for Quantum
Communication
, x
Given any n-qubit state , Alice can send a poly(n)-qubit
state  and a string x to Bob, in such a way that:
 can be used to simulate  on all small circuits, and
Bob can efficiently verify that using x
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
Main Tool: Majority-Certificates Lemma
(Related to boosting in computational learning theory)
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) There’s a unique fiS consistent with each Ci, and
(ii) f*(x)=MAJORITY(f1(x),…,fm(x)) for all x{0,1}n.
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
“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”
Quantum Karp-Lipton Theorem:
An Unexpected Application of Our BQP/qpoly=YQP/poly Theorem
Karp-Lipton 1982: If NP  P/poly, then coNPNP = NPNP.
Our quantum analogue:
If NP  BQP/qpoly, then coNPNP  QMAPromiseQMA.
Idea: Let M be a YQP/poly machine that solves 3SAT. In QMA,
guess the classical advice z to M, and check that some quantum
witness | is consistent with z. Then, in PromiseQMA, search
for a quantum witness | consistent with z, as well as a 3SAT
instance of size n on which | fails. If no such instance is
found, guess the first quantified string of the coNPNP
statement, and use | to find the second quantified string.
Open Problems
Does QMA=QCMA? Does BQP/qpoly=BQP/poly? Can we
at least prove (classical) oracle separations?
Improve the parameters of the majority-certificates lemma,
and clarify the connection with boosting?
Other applications of majority-certificates?
Is it possible that every state on n qubits can be simulated
by a verifiable state on n qubits, rather than poly(n)?
If you can make the following terms
comprehensible to a computer scientist:
“Squeezed state”
“Parametric downconversion”
“Homodyne measurement”
please see me after the talk