Transcript Limitations of Quantum Advice and One

Limitations of Quantum Advice
and One-Way Communication
Useful?

Scott Aaronson
UC Berkeley  IAS
What Are Quantum States?
To many quantum computing skeptics,
they’re exponentially long vectors—and
therefore a bad description of Nature
Yet a classical probability distribution over
{0,1}n also takes 2(n) bits to specify!
“Sure, but each sample is only n bits…”
Distributions
over n-bit strings

2n-bit strings
We give complexity-theoretic evidence that
quantum states lie to the left end of this spectrum
Supplements information-theoretic evidence (e.g. Holevo)
Quantum Advice
Nielsen & Chuang: “We know
that many systems in Nature
‘prefer’ to sit in highly entangled
states of many systems; might it be
possible to exploit this preference to
obtain extra computational power?”
BQP/qpoly: Class of languages decidable by
polynomial-size, bounded-error quantum circuits,
given a polynomial-size quantum advice state
|n that depends only on the input length n
Example (Watrous)
For each n, fix a group Gn and subgroup HnGn
(|Gn|2n, but group operations are polytime)
Given an element xGn as input, is xHn?
Solvable in BQP/qpoly using the advice state
1
to h
H nNot
 known
be in BQP/poly
H n hHn
Idea: Check whether Hn|xHn is 1 or 0
Obvious Challenge: Prove an oracle
separation between BQP/poly and BQP/qpoly
Buhrman: Hey Scott—why not try for an
unrelativized separation? After all, if quantum
states are like 2n-bit classical strings, then
maybe BQP/qpoly  NEEEEE/poly!
Maybe BQP/qpoly even contains NP!
Result #1
BQP/qpoly  PP/poly
Corollary: Can’t show
BQP/poly  BQP/qpoly without
also showing PP  P/poly
Proof based on new communication result:
Given f:{0,1}n{0,1}m{0,1} (partial or total),
D1(f) = O(m Q1(f) logQ1(f))
D1(f) = deterministic 1-way communication complexity of f
Q1(f) = bounded-error quantum 1-way complexity
Result #2
A
NP

A
BQP /qpoly
for some oracle A (actually, a random oracle)
Proof based on new Direct Product Theorem
for quantum search:
N items, K of them marked
Theorem: With few (N) quantum queries, the
probability of finding all K marked items is 2-(K)
Fixes a wrong result of Klauck
Result #3
(Won’t say any more about this one)
Ambainis: Suppose Alice has x,yFp and Bob
has a,bFp. They want to know whether yax+b.
1-way quantum communication complexity?
Theorem: Alice must send
(log p) qubits to Bob
Invented new “trace distance
method” to show this
Alice’s
point
Bob’s
line
Previously, even randomized
complexity was unknown
The “Almost As Good
As New” Lemma
Suppose a 2-outcome
measurement of a
mixed state  yields ‘0’
w.p. 1- and ‘1’ w.p. 
Then after the measurement,
we can recover a ’ such that
 ' 
tr
 
D1(f) = O(m Q1(f) logQ1(f)) for all
f : {0,1}n{0,1}m  {0,1}
x
Alice

 logQ1  f 
x
y1,y2,… f(x,y1)
f(x,y)
f(x,y2)
Bob
Alice can decrease the error probability to
1/Q1(f)10, by sending K=O(Q1(f)logQ1(f)) qubits
Bob can then compute f(x,y) for Q1(f)2 values of y
simultaneously, with probability  0.9
With no communication, he can still do that with
probability  0.9/2K, by guessing x=I
Alice’s Classical Message
y1
y2
Bob, let p0(y) be the probability
you’d guess f(x,y)=1 using I in place
of x. Then y1 is the lexicographically
first y for which |p0(y)-f(x,y)|½.
Now let I1 be the reduced state
assuming you guessed f(x,y1)
correctly. Let p1(y) be the probability
you’d guess f(x,y)=1 using I1 in place
of x. Then y2 is the first y after y1 for
which |p1(y)-f(x,y)|½.
Clearly Alice’s message lets Bob compute f(x,y)
for any y in his range
Claim: Alice never has to send more than K
yi’s—so her total message length is O(mK)
Suppose not. Then Bob would succeed on
y1,…,yK+1 simultaneously with probability  1/2K+1
But we already know he succeeds with
probability  0.9/2K, contradiction
BQP/qpoly  PP/poly
Alice is the
“advisor”
Bob is
the PP
algorithm
Suppose quantum advice has p(n) qubits. Then
classical advice consists of K = O(p(n) log p(n))
inputs x1,…,xK{0,1}n, on which algorithm would
make the wrong guess using maximally mixed
state in place
of adviceearlier
(as before)
Improves
result:
BQP/qpolyHuang:
 EXP/poly
Adleman, DeMarrais,
In PP, we can
decide which of two sequences of measurement
outcomes has greater probability
NPA  BQPA/qpoly
Oracle: A(x)=1 iff xS, where S  {0,1}n is
chosen uniformly at random subject to |S|=2n/10
Language: (y,z)LA iff there exists an xS
between y and z lexicographically (clearly LANPA)
Claim: If LABQPA/qpoly, then using boosted
advice, we can find all 2n/10 elements of S
w.h.p. using 2n/10poly(n) quantum queries
Now replace advice by maximally mixed state.
Success probability becomes 2-O(poly(n))
Direct Product Theorem
Goal: Show that with o(2n/2) quantum queries,
the probability of finding all 2n/10 marked items
must be doubly exponentially small in n
Beals et al: If a quantum algorithm makes T
queries to X{0,1}N, then the probability it
accepts a random X with |X|=k is a univariate
polynomial p(k) of degree  2T
1
p(k)
0
0
1
2
. . . . .
k
. . . . .
N
Have the algorithm accept iff it finds |S|=2n/10
marked items. Then
(1) p(k)=0 for all k{0,…,|S|–1}
(2) p(|S|) = 2-O(poly(n))
(3) p(k)[0,1] for all k{0,…,2n}
1
p(k)
0
0
1
2
. . .
|S|
k
. . . . .
2n
 2n S 

Theorem: Given the above, deg  p    
 poly  n  


(Improved by Klauck et al.)
Idea: Let r  m 
dmp
 maxn
.
m
0 x  2 dx
Then V.A. Markov (younger brother of A.A.
Markov) showed in 1892 that
r
m
 3deg  p 

n

2

2
m
 2m1  m  1!

  2m  1!

provided -1p(x)2 for all 0x2n.
On the other hand, one can show by
induction on m that r(m)  2-O(poly(n))/m!
Open Questions
Can we show BQP/poly  BQP/qpoly relative
to an oracle?
What about SZK  BQP/qpoly?
Are randomized and quantum 1-way
communication complexities polynomially
related for all total Boolean functions?
(No asymptotic gap is known)