Transcript BQP/qpoly EXP/poly

BQP/qpoly  EXP/poly
Scott Aaronson
UC Berkeley
BQP/qpoly
• Class of languages recognized by a
bounded-error polytime quantum algorithm,
with a polysize quantum advice state
|n that depends only on the input size
• Buhrman: Is BQP/qpoly  anything/poly?
Our Result
• BQP/qpoly  EXP/poly
• Means we shouldn’t hope for an
unrelativized separation between BQP/poly
and BQP/qpoly—since it would imply
P/poly  EXP/poly, which is equivalent to
EXP  P/poly
Proof Sketch
• Given a BQP/qpoly algorithm, make error prob.
exponentially small by taking |np(n) as advice
• On input x{0,1}n, loop through all yx in
lexicographic order
• For i{0,1}, let Si be set of advice states that cause
algorithm to output i with prob. 1-c-n. Then there
exist orthogonal subspaces H0,H1 s.t. all states in
Si are exponentially close to Hi
• To see this: acceptance probability on advice |
can be written |x|, for some Hermitian p.s.d. x
with eigenvalues in [0,1]. Let H0,H1 be subspaces
spanned by eigenvectors of x corresponding to
eigenvalues in [0,1/3], [2/3,1] respectively
H1
H0
• Let Ty be subspace of |’s compatible with
inputs 1,…,y (initially T0 = whole Hilbert space)
• Let Ty = whichever has larger dimension:
projection of Ty-1 onto H0, or projection of Ty-1
onto H1
• Unless classical advice says to pick the
subspace of smaller dimension!
• Each time we pick smaller subspace, dim(Ty) is
at least halved. So advice needs to intervene
only polynomially many times
• Can do everything in EXP (diagonalize
exponentially large matrix y, loop over all
inputs, etc.)
• Main technical fact: Error (distance from
Ty to |np(n)) stays bounded over all
iterations
Open Problems
• Oracle separation between BQP/poly and
BQP/qpoly
• Is BQP/qpoly  PSPACE/poly?
• Is BQP/qpoly  PP/poly relative to an
oracle?
• Any natural problems in BQP/qpoly
(besides cousins of QMA problems)?