Transcript The Learnability of Quantum States

QMA/qpoly  PSPACE/poly:
De-Merlinizing Quantum Protocols
Scott Aaronson
University of Waterloo
The Story
xi
One-Way
x{0,1}N
Alice
i{1,…,N}
Bob
Bob, a grad student, has a thesis problem i{1,…,N}
Alice, Bob’s omniscient advisor, knows the binary
answer xi to every thesis problem i
But she’s too busy to find out which specific problems
her students are working on
So instead, she just doles out the same generic advice
ax to all of them
The Story
xi
One-Way
One-Way
x{0,1}N
Alice
i{1,…,N}
Bob
Merlin
Clearly ax needs to be (N) bits long, for Bob to be able
to learn xi with probability 2/3 for any i
Ambainis et al., Nayak: Indeed, this is true even if
Alice can send a quantum message |x
So in desperation, Bob turns for help to Merlin, the star
student in his department…
The Story
xi
One-Way
One-Way
x{0,1}N
Alice
i{1,…,N}
Bob
Merlin
On the plus side: Merlin knows both x1…xn and i
On the minus side: He’s a lying weasel
Can Bob play Alice’s vague but reliable advice against
Merlin’s specific but unreliable witness, to learn xi
using polylog(N) bits from both?
Not hard to prove that this is classically impossible
The Story
xi
One-Way
One-Way
x{0,1}N
Alice
i{1,…,N}
Bob
Merlin
Main Result: Even in the quantum case, if
Alice sends a qubits and Merlin sends w
qubits, for Bob to learn xi w.h.p. we need
 N 
aw  1   2 
 log N 
Application to Quantum Advice
BQP/qpoly: Class of problems solvable efficiently by
a quantum computer with help from polynomial-size
“quantum advice states”
A., CCC 2004: BQP/qpoly  PostBQP/poly = PP/poly
Seemed to place a strong limit on quantum advice…
Ran Raz’s curveball:
QIP/qpoly = ALL
Raz’s result actually has nothing to do with quantum
mechanics, since IP/rpoly = ALL as well
Where’s The Phase Transition?
(the point in the complexity hierarchy where quantum advice
starts acting like exponentially-long classical advice)
Oded Regev: What about QMA/qpoly?
Is that also equal to ALL? Or can you
upper-bound it by (say) PP/poly?
QMA/qpoly: Class of languages L for which there exists
a poly-time quantum verifier V, together with poly-size
n:
A few
months
later,
I
had
my
answer:
quantum
advice
states {|
},
such
that
for
all
x{0,1}
n
QMA/qpoly
PSPACE/poly
(1) If xL then
there exists 
a poly-size
quantum witness
| such that V accepts |x|n| w.p.  2/3
(2) If xL, then for all purported witnesses |, V rejects
|x|n| w.p.  2/3
“Sure, quantum advice is a weird resource, but
so is classical randomized advice!”
The Quantum Advice
For any “natural”
complexity class C, if
Hypothesis:
C/qpoly=ALL, then C/rpoly=ALL as well
Four Confirming Instances So Far:
1. BQP/qpoly  PP/poly, BQP/rpoly = BQP/poly
2. QIP/qpoly = QIP/rpoly = ALL
3. PostBQP/qpoly = PostBQP/rpoly = ALL
4. QMA/qpoly  PSPACE/poly, QMA/rpoly = QMA/poly
Plan of Attack
PSPACE/poly
Similar to Watrous’s result
that BQPSPACE=PSPACE
PostBQPSPACE/poly
Similar to my result that
BQP/qpolyPostBQP/poly
BQPSPACE/qpoly
Main difficulty of proof
QMA/qpoly
(Why doesn’t it follow trivially
from QMAPSPACE??)
Warmup: The Classical Case
xi
x{0,1}N
i{1,…,N}
Claim: For all awN, there’s a randomized protocol where
Alice sends a+O(log N) bits and Merlin sends w bits
Proof: Alice divides x into w-bit substrings. She then
encodes each one with an error-correcting code, and sends
Bob a random k along with the kth bit of each codeword.
Merlin sends the substring containing xi.
Warmup: The Classical Case
xi
x{0,1}N
i{1,…,N}
Claim: The previous protocol is optimal.
Proof: Suppose Alice amplifies her a-bit randomized
advice O(w+1) times. Then Bob’s error probability
becomes 2-w. So Bob no longer needs Merlin—he can
just loop over all possible w-bit witnesses. Hence
a(w+1)=(N).
Trouble in QuantumLand
If Bob wants to eliminate Merlin’s w-qubit quantum
witness, the number of states he needs to loop through
is doubly exponential in w!
And Alice can’t afford to amplify her message
exponentially many times
Solution: Bob will detect | by looking for the
“shadows” it casts on computational basis states

z
 z
2
1
|
Quantum OR Bound
Let C| be a quantum verifier that takes | as advice
But couldn’t the
Let |HN be a witness that C| accepts with
measurements
probability at least .
destroy |?
Suppose that, instead of feeding | to C|, we feed it
TN/2 uniformly random basis states in sequence:
|j1,…,|jTHN
Sure. But that can only
(reusing the same advice | throughout)
mean one of the
Theorem: C| measurements
will accept at least has
one ofalready
the basis
2
accepted
states with probability
at least with non
N
 .
negligible probability




T


QMA/qpoly  BQPSPACE/qpoly
Simulation algorithm:
Repeatedly choose a random basis state |j, then
simulate the QMA machine with | as advice and
|j as witness
By the quantum OR bound, if there’s a valid witness
|, then w.h.p. some iteration will accept
And what if there’s no valid witness?
To control soundness error, we use an unusual
amplification procedure—one that involves
amplifying Alice’s message poly(n) times and
Merlin’s message only log(n) times
Can we get below PSPACE/poly?
Yes, if either the advice or the witness is classical
Theorem: QMA/rpoly = QMA/poly
Idea: First amplify, then find a single random string r
that works for all inputs of size n and all quantum
witnesses (doubly-exponentially many, but OK)
Chicken & egg problem: The more we amplify the
witness, the more we need to amplify
Solution: In-place amplification [Marriott & Watrous]
Theorem: QCMA/qpoly  PP/poly
PP/rpoly = IP(2)/rpoly = ALL
PSPACE/poly = PSPACE/rpoly
PP/poly = PostBQP/poly
QMA/poly = QMA/rpoly
QCMA/poly = QCMA/rpoly
BQP/poly = BQP/rpoly
QMA/qpoly
QCMA/qpoly
BQP/qpoly
Open Problems
Is the Quantum Advice Hypothesis true? What about
for QMA(2) (QMA with two unentangled yes-provers)?
Can we tighten the de-Merlinization result from
a(w+1)=(N/log2N) to a(w+1)=(N)?
Is QMA/qpoly  PP/poly?