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 2 From 2 n /2 x 0 ,1 n x 2 s s n x we can easily prepare n s 0 s 1 2 f , H 1 / 2 2 n 0 1 / 2 2 2s 1 n 2 s s 2 n 2 2 Goal: Decide if these amplitudes have the s 0signs 1 / 2 2 2s 1 same or opposite : Yields in first qubit n / s / 2 for 2 s ,. 2 some Prepare |0|+|1H| 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 for all i{-n,…,n}, we’ll eventually get close to 0 0 1 2 s 0 1 / 2 2 2s 1 n Yields / : s / 22 2s 2 2 2 n 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,L2PostBQP, to decide if xL1 and xL2, 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 BQP (Fortnow and Reingold) PP (Fortnow and Rogers) QMA PP (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 1 f O mQ f log 1 Q f . 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 xL 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 x0L Conditioned on deciding x0 If no, set x0L correctly, does accept xx1 Conditioned onUdeciding 0 w.p. and x1 ½? correctly, does U If yes, set x1L ½? accept x2 w.p. If If no, yes,set setxx1L 2L If no, set x2L 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 - NPcoNP - (NPcoNP)/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 hierarchy—consisting of PP , PP PP , PP etc.—collapses to PP PP 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!

Descargar
# The Amazing Power of Postselection