Transcript The Amazing Power of Postselection

A MAX Feature Presentation
=
Scott’s Grab Bag
o’ Cheap Yuks
Scott Aaronson (IAS)
Dr. Scott’s Grab
Bag o’ Cheap Yuks
Scott Aaronson (IAS)
Outlook on the Future
of Quantum Computing
Scott Aaronson (IAS)
The Remarkable
Ubiquity of
Postselection
Scott Aaronson (IAS)
The Stupendous
Strength of
Postselection
Scott Aaronson (IAS)
The Hunky, Rippling
Manliness of
Postselection
Scott Aaronson (IAS)
Lessons Learned in
the Gottesman
Institute of Comedy
Scott Aaronson (IAS)
The Amazing Power
of Postselection
Scott Aaronson (IAS)
What IS Postselection?
Learning something about a question by
conditioning on the fact that you’re asking it.
BERKELEY
CAMBRIDGE
What about the
quantum case?
“Anthropic Computing”: A foolproof way to
solve NP-complete problems in polynomial time
Input: A Boolean formula 
(1) Accept the many-worlds interpretation
(2) Generate a random truth assignment X
(3) If X doesn’t satisfy , kill yourself
In This Talk…
I’ll study what you could do with a quantum
computer, IF you could measure a qubit and
postselect on its being |1
This will lead to:
• An extremely simple proof of the celebrated
Beigel-Reingold-Spielman theorem
• Limitations on quantum advice and one-way
communication
• Unrelativized quantum circuit lower bounds
• And more!
I hereby define a new
complexity class…
PostBQP
(Postselected BQP)
Class of languages decidable by a boundederror polynomial-time quantum computer, if
at any time you can measure a qubit that
has a nonzero probability of being |1, and
assume the outcome will be |1
Another Important Animal: PP
Class of languages decidable by a
nondeterministic poly-time Turing machine
that accepts iff the majority of its paths do
PSPACE
P#P=PPP
PP
NP
P
Theorem: PostBQP = PP
Easy half: PostBQP  PP
Adleman, DeMarrais, and Huang (1997) showed
BQP  PP using “Feynman sum-over-histories”
Idea: Write acceptance and rejection
probabilities as sums of exponentially many
easy-to-compute terms; then use PP to decide
which sum is greater
For PostBQP, just sum over postselected
outcomes only
To Show PP  PostBQP…
Given a Boolean function f:{0,1}n{0,1},
let s=|{x : f(x)=1}|. Need to decide if s>2n-1
n / 2
2
From

2


n

x f  x
we can easily prepare
x0,1
n
 s 0  s 1
2  s  s
2
n
, H 
1/ 2  2 n  0  1/ 2  2 n  2 s  1
2
2

s

s


2
n
2
Goal: Decide if these amplitudes
have
the
n

s
0


1/
2
2
 2s  1

same
or
opposite
signs
Yields  :
in first qubit
 /
 s    / 2for
 2 s  ,.
 2 some
Prepare |0|+|1H|
Then postselect on second qubit being |1
2 2
2
n
2
To Show PP  PostBQP…
1
n-2s
Suppose
s
and
2
On the other hand, if
are
both
positive then
2n-2s
is negative,
we won’t.
QED/ = 2i
Then
by trying

0
for all i{-n,…,n}, we’ll
eventually get close to
 
Yields   /  :
 s 0   1/ 2  2 n  2 s  1
 2 s 2    2 / 2  2n  2 s 
2
0 1
2
in first qubit
Totally unexpectedly, the PostBQP=PP
theorem turned out to have implications
for classical complexity theory…
Beigel, Reingold, Spielman 1990: PP is
“closed under intersection”
Solved a problem that was open for 18 years…
Observation: PostBQP is trivially closed
under intersection  PP is too
Given L1,L2PostBQP, to decide if xL1 and
xL2, postselect on both computations
succeeding, and accept iff they both accept
Other Classical Results Proved With
Quantum Techniques:
Kerenidis & de Wolf, A., Aharonov & Regev, …
Other Results that
PostBQP=PP Makes Simpler
P||
PP
 PP
PP
 PP
QMA PP
BQP
(Fortnow and Reingold)
(Fortnow and Rogers)
(Kitaev and Watrous)
Quantum Advice
Mike & Ike: “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
How powerful is quantum advice?
Could it let us solve problems that are not
even recursively enumerable given
classical advice of similar size?!
Limitations of Quantum Advice
NP  BQP/qpoly relative to an oracle
(Uses direct product theorem for quantum search)
BQP/qpoly  PostBQP/poly
( = PP/poly)
Closely related: for all (partial or total) Boolean
functions f : {0,1}n  {0,1}m  {0,1},


D  f   O mQ  f logQ  f  .
1
1
1
Alice’s Classical Advice
x1
x2
Bob, suppose you used the
maximally mixed state in place of
your quantum advice. Then x1 is the
lexicographically first input for which
you’dGiven
output an
theinput
right answer
with
x,
probability
lessBob
than ½.
clearly lets
But suppose you succeeded on x1,
decide in PostBQP
and used the resulting reduced state
whether xL
as your advice. Then x2 is the
lexicographically first input after x1 for
which you’d output the right answer
with probability less than ½...
But how many inputs must Alice specify?
We can boost a quantum advice state so
that the error probability on any input is at
most (say) 2-100n; then Bob can reuse the
advice on as many inputs as he likes
We can decompose the maximally mixed
state on p(n) qubits as the boosted advice
plus 2p(n)-1 orthogonal states
Alice needs to specify at most p(n) inputs
x1,x2,…, since each one cuts Bob’s total
success probability by least half, but the
probability must be (2-p(n)) by the end
PPP Does Not Have Quantum
Circuits of Size nk
U: Picks a size-nk quantum
circuit uniformly at random
and runs it
Does U accept x0 w.p.  ½?
If yes, set x0L
Conditioned on deciding x0
If no, set x0L
correctly,
does
accept xx1
Conditioned
onUdeciding
0
w.p.
and x1 ½?
correctly, does U
If
yes, set
x1L ½?
accept
x2 w.p.
If
If no,
yes,set
setxx1L
2L
If no, set x2L
 x0
 x1
x2
x3
x4
x5
For any k, defines a language L that does not
have quantum circuits of size nk
Even works for
Why? Intuitively,
each
iteration cuts the
quantum
circuits
number of potential
circuits in half, but there
with quantum
k
n
were at most ~ advice!
2 circuits to begin with
On the other hand, clearly L  PPP
Also…
If a function f:{0,1}n{0,1} has a polynomialsize quantum circuit, then a PostBQP machine
can find such a circuit using queries to f
Even
worksinputs
for x and quantum
Intuition: Guess
random
t
quantum circuits
circuits Ct. Repeatedly
use postselection to find
with quantum
• An input xt on which
Ct fails
advice!
• A circuit Ct+1 that succeeds on x1,…,xt
Reminiscent of a classical learning theory
result of Bshouty, Cleve, et al.
And now for a grand finale…
0-1-NPC - #AC0 - #L - #L/poly - #P - #W[t] - +EXP - +L - +L/poly - +P - +SAC1 - A0PP - AC - AC0 - AC0[m] - ACC0 - AH - AL
- AlgP/poly - AM - AM-EXP - AM intersect coAM - AM[polylog] - AmpMP - AmpP-BQP - AP - AP - APP - APP - APX - AUCSPACE(f(n)) - AVBPP - AvE - AvP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - βP - BH - BPE - BPEE - BPHSPACE(f(n)) BPL - BP•NP - BPP - BPPcc - BPPKT - BPP-OBDD - BPPpath - BPQP - BPSPACE(f(n)) - BPTIME(f(n)) - BQNC - BQNP BQP - BQP/log - BQP/poly - BQP/qlog - BQP/qpoly - BQP-OBDD - BQPtt/poly - BQTIME(f(n)) - k-BWBP - C=AC0 - C=L C=P - CFL - CLOG - CH - Check - CkP - CNP - coAM - coC=P - cofrIP - Coh - coMA - coModkP - compIP - compNP - coNE
- coNEXP - coNL - coNP - coNPcc - coNP/poly - coNQP - coRE - coRNC - coRP - coSL - coUCC - coUP - CP - CSIZE(f(n))
- CSL - CZK - D#P - Δ2P - δ-BPP - δ-RP - DET - DiffAC0 - DisNP - DistNP - DP - DQP - DSPACE(f(n)) - DTIME(f(n)) DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC0 - E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - ELkP - EPTAS - k-EQBP
- EQP - EQTIME(f(n)) - ESPACE - BPP - NISZK - EXP - EXP/poly - EXPSPACE - FBQP - Few - FewP - FH - FNL FNL/poly - FNP - FO(t(n)) - FOLL - FP - FPNP[log] - FPR - FPRAS - FPT - FPTnu - FPTsu - FPTAS - FQMA - frIP - FTAPE(f(n)) - F-TIME(f(n)) - GA - GAN-SPACE(f(n)) - GapAC0 - GapL - GapP - GC(s(n),C) - GI - GPCD(r(n),q(n)) - G[t] HeurBPP - HeurBPTIME(f(n)) - HkP - HVSZK - IC[log,poly] - IP - IPP - L - LIN - LkP - LOGCFL - LogFew - LogFewNL LOGNP - LOGSNP - L/poly - LWPP - MA - MA' - MAC0 - MA-E - MA-EXP - mAL - MaxNP - MaxPB - MaxSNP - MaxSNP0 mcoNL - MinPB - MIP - MIP*[2,1] - MIPEXP - (Mk)P - mL - mNC1 - mNL - mNP - ModkL - ModkP - ModP - ModZkL - mP MP - MPC - mP/poly - mTC0 - NC - NC0 - NC1 - NC2 - NE - NE/poly - NEE - NEEE - NEEXP - NEXP - NEXP/poly NIQSZK - NISZK - NISZKh - NL - NL/poly - NLIN - NLOG - NP - NPC - NPcc - NPC - NPI - NPcoNP - (NPcoNP)/poly NP/log - NPMV - NPMV-sel - NPMVt - NPMVt-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NPR - NPSPACE NPSV - NPSV-sel - NPSVt - NPSVt-sel - NQP - NSPACE(f(n)) - NT - NTIME(f(n)) - OCQ - OptP - P - P/log - P/poly - P#P P#P[1] - PAC0 - PBP - k-PBP - PC - Pcc - PCD(r(n),q(n)) - P-close - PCP(r(n),q(n)) - PermUP - PEXP - PF - PFCHK(t(n)) PH - PHcc - Φ2P - PhP - Π2P - PINC - PIO - PK - PKC - PL - PL1 - PLinfinity - PLF - PLL - PLS - PNP - PNP[k] - PNP[log] - PNP[log^2]
- P-OBDD - PODN - polyL - PostBQP - PP - PP/poly - PPA - PPAD - PPADS - PPP - PPP - PPSPACE - PQUERY - PR - PR
- PrHSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PT1 PTAPE - PTAS - PT/WK(f(n),g(n)) - PZK - QAC0 - QAC0[m] - QACC0 - QAM - QCFL - QCMA - QH - QIP - QIP(2) - QMA QMA+ - QMA(2) - QMAlog - QMAM - QMIP - QMIPle - QMIPne - QNC0 - QNCf0 - QNC1 - QP - QPLIN - QPSPACE - QSZK R - RE - REG - RevSPACE(f(n)) - RHL - RL - RNC - RP - RPP - RSPACE(f(n)) - S2P - S2-EXP•PNP - SAC - SAC0 - SAC1 SAPTIME - SBP - SC - SEH - SelfNP - SFk - Σ2P - SKC - SL - SLICEWISE PSPACE - SNP - SO-E - SP - SP - span-P SPARSE - SPL - SPP - SUBEXP - symP - SZK - SZKh - TALLY - TC0 - TFNP - Θ2P - TreeBQP - TREE-REGULAR - UAP UCC - UE - UL - UL/poly - UP - US - VNCk - VNPk - VPk - VQPk - W[1] - WAPP - W[P] - WPP - W[SAT] - W[*] - W[t] - W*[t] XOR-MIP*[2,1] - XP - XPuniform - YACC - ZPE - ZPP - ZPTIME(f(n))
Quantum Karp-Lipton Theorem
If PP  BQP/qpoly, then the counting
PP
PPPP
hierarchy—consisting of PP, PP , PP
,
etc.—collapses to PP
But there’s more: With no assumptions, PP
does not have quantum circuits of size nk
And more: PEXP requires quantum circuits
of size f(n), where f(f(n))2n
Even Stronger Separations
QMAEXP (a subclass of PEXP) is not in
BQP/qpoly
QCMAEXP (a subclass of QMAEXP) is not in
BQP/poly
A0PP (a subclass of PP) does not have
quantum circuits of size nk
Conclusions
I started out with a weird philosophical question
I ended up with seven or eight results
Try it—it works!