Transcript Cosmology and Complexity Classes

SZK
ZPP
QAM
Cosmology and Complexity
Classes
Scott Aaronson (UC Berkeley)
GapP
L
EEXP
W[P]
Complexity Classes Not Needed For This Talk
0-1-NPC - #L - #L/poly - #P - #W[t] - +EXP - +L - +L/poly - +P - +SAC1 - AC - AC0 - AC0[m] - ACC0 - AH - AL AM - AmpMP - AP - AP - APP - APX - AVBPP - AvE - AvP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - βP - BH
- BPE - BPEE - BPHSPACE(f(n)) - BPL - BPPKT - BPP-OBDD - BPQP - BQNC - BQP-OBDD - k-BWBP - C=L C=P - CFL - CLOG - CH - CkP - CNP - coAM - coC=P - coMA - coModkP - coNE - coNEXP - coNL - coNP coNP/poly - coRE - coRNC - coRP - coUCC - CP - CSL - CZK - Δ2P - δ-BPP - δ-RP - DET - DisNP - DistNP - DP E - EE - EEE - EEXP - EH - ELEMENTARY - ELkP - EPTAS - k-EQBP - EQP - EQTIME(f(n)) - ESPACE - EXP EXPSPACE - Few - FewP - FNL - FNL/poly - FNP - FO(t(n)) - FOLL - FP - FPR - FPRAS - FPT - FPTnu - FPTsu FPTAS - F-TAPE(f(n)) - F-TIME(f(n)) - GapL - GapP - GC(s(n),C) - GPCD(r(n),q(n)) - G[t] - HkP - HVSZK IC[log,poly] - IP - L - LIN - LkP - LOGCFL - LogFew - LogFewNL - LOGNP - LOGSNP - L/poly - LWPP - MA MAC0 - MA-E - MA-EXP - mAL - MaxNP - MaxPB - MaxSNP - MaxSNP0 - mcoNL - MinPB - MIP - MIPEXP (Mk)P - mL - mNC1 - mNL - mNP - ModkL - ModkP - ModP - ModZkL - mP - MP - MPC - mP/poly - mTC0 - NC NC0 - NC1 - NC2 - NE - NEE - NEEE - NEEXP - NEXP - NIQSZK - NISZK - NL - NLIN - NLOG - NL/poly - NPC
- NPC - NPI - NP intersect coNP - (NP intersect coNP)/poly - 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)) - NTIME(f(n)) - OCQ - OptP - PBP - k-PBP - PC - PCD(r(n),q(n)) - P-close - PCP(r(n),q(n)) - PEXP PF - PFCHK(t(n)) - Φ2P - PhP - Π2P - PK - PKC - PL - PL1 - PLinfinity - PLF - PLL - P/log - PLS - PNP - PNP[k] - PNP[log]
- P-OBDD - PODN - polyL - PP - PPA - PPAD - PPADS - P/poly - PPP - PPP - PR - PR - PrHSPACE(f(n)) PromiseBPP - PromiseRP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PT1 - PTAPE - PTAS - PT/WK(f(n),g(n)) PZK - QAC0 - QAC0[m] - QACC0 - QAM - QCFL - QH - QIP - QIP(2) - QMA - QMA(2) - QMAM - QMIP QMIPle - QMIPne - QNC0 - QNCf0 - QNC1 - QP - QSZK - R - RE - REG - RevSPACE(f(n)) - RHL - RL - RNC - RPP
- RSPACE(f(n)) - S2P - SAC - SAC0 - SAC1 - SC - SEH - SFk - Σ2P - SKC - SL - SLICEWISE PSPACE - SNP - SOE - SP - span-P - SPARSE - SPP - SUBEXP - symP - SZK - TALLY - TC0 - TFNP - Θ2P - TREE-REGULAR - UCC
- UL - UL/poly - UP - US - VNCk - VNPk - VPk - VQPk - W[1] - W[P] - WPP - W[SAT] - W[*] - W[t] - W*[t] - XP XPuniform - YACC - ZPE - ZPP - ZPTIME(f(n))
More at http://www.cs.berkeley.edu/~aaronson/zoo.html
Outline
• The Physics of Databases
• Quantum Search of Spatial Regions
• The Universe in 10 Minutes
• The Inflationary Turing Machine
(work in progress)
Quantum Search of Spatial Regions
Joint work with Andris Ambainis (U. of Latvia)
quant-ph/0303041
Grover’s O(n) Quantum Search Algorithm:
Great for combinatorial search
But can it help search a physical region?
BWAHAHA!
Look who
needs physics
now!
What even a dumb computer scientist knows:
THE SPEED OF LIGHT IS FINITE
Consider a quantum robot searching a 2D grid:
Robot
n
n
Marked item
We need n Grover iterations, each of which
takes n time, so we’re screwed!
We saw Grover search of a 2D grid presented a problem…
So why not pack data in 3 dimensions?
Then the complexity would be n  n1/3 = n5/6
Trouble: Suppose our “hard disk” has mass density 
Once radius exceeds Schwarzschild bound of
(1/), hard disk collapses to form a black hole
Makes things harder to retrieve…
Actually worse—even a 2D hard disk would
collapse once radius exceeds (1/)
1D hard disk would not collapse…
But we care about entropy, not mass
A ball of radiation of radius r has energy (r) but
entropy (r3/2)
Holographic Principle: A region of space can’t store
more than 1.41069 bits per meter2 of surface area
Quantum Mechanics and General Relativity
both yield a n lower bound on search
If space had d>3 dimensions, then relativity
bound would be weaker: n1/(d-1)
Is that bound achievable? Apparently not, since
even stronger limit (Bekenstein’s) applies for
weakly-gravitating systems
What We Can Achieve
If n ~ rc bits are scattered in a 3D ball of radius r
(where c3 and bits’ locations are known), search
time is (n1/c+1/6)
(up to polylog factor)
For “radiation disk” (n ~ r3/2): (n5/6) = (r5/4)
For n ~ r2 (saturating holographic bound):
(n2/3) = (r4/3)
To get O(n polylog n), bits would need to be
concentrated on a 2D surface
Objections to the Model
(1)Would need n parallel computing elements to
maintain a quantum database
Response: Might have n “passive elements,” but
many fewer “active elements” (i.e. robots), which
we wish to place in superposition over locations
(2) Must consider effects of time dilation
Response: For upper bounds, will have in mind
weakly-gravitating systems, for which time
dilation is by at most a constant factor
Back to the Main Issue
Classical search takes (n) time
Quantum search takes (rn)
(r = maximum radius of region)
Can we do anything better?
Benioff (2001): Guess we can’t…
REVENGE OF COMPUTER SCIENCE
• We can.
• Idea: Recursively divide into sub-squares
Using amplitude
amplification techniques
of BHMT’2002, we get:
O(n log3n) for 2D grid
O(n) for 3 and higher
dimensions
What’s the Model?
• Undirected connected graph G=(V,E)
• Bit xi at each vertex vi
• Goal: Compute some Boolean f(x1…xn){0,1}
• State can have arbitrary ancilla z:
  i, z vi , z
• Alternate query transforms vi , z   1
with ‘local’ unitaries
xi
What does ‘local’ mean? Depends on your religion
vi , z
Defining Locality: 3 Choices
(1) Unitary must be decomposable into commuting
local operations, each acting on a single edge
(2) Just don’t “send amplitude” between non-adjacent
vertices: if (i,j)E then
U i, z  j ,z  0
(3) Take U=eiH where H has eigenvalues of absolute
value at most , and if (i,j)E then
H i, z  j ,z  0
(1)  (2),(3). Upper bounds will work for (1); lower
bounds for (2),(3)
In More Detail: d3
• Assume there’s a unique marked item
• Divide into n1/5 subcubes, each of size n4/5
• Algorithm A:
If n=1, check whether you’re at a marked item
Else pick a random subcube and run A on it
Repeat n1/11 times using amplitude amplification
• Running time:
T n  n
1/11
T  n   O  n  
 O  n5/11 
4/5
1/ d
d3 (continued)
• Success probability (unamplified):
P n  n
1/ 5
P n
4/5

• With amplification:
P  n   1    n
 n
2/11 1/ 5
1/11
n
P n
4/ 5

 (since  is negligible)
• Amplify whole algorithm n1/22 times to get
P  n    1 , T  n   O  n
1/ 22
n
5/11
  O n
Other Results
to which I won’t subject you
• For r marked items, we get

n
T  n   O  d 1/ 21/ d
r

for d3, even if r is unknown



• For d=2, get T(n)=O(n log3n)
• For any graph that’s “d-dimensional” by expansion
properties (d>2), if h “potential” marked items are
scattered around (and their locations are known), get
1/ d


n
T  n   O  h   poly log h 


h




Application: Disjointness
• Problem: Alice has x1…xn{0,1}n, Bob has y1…yn
They want to know if xiyi=1 for some i
• How many qubits must they communicate?
• Buhrman, Cleve, Wigderson 1998: O
• Høyer, de Wolf 2002:
• Razborov 2002:

O
 n

nc log*n


n log n

Disjointness in O(n) Communication
B
A
State at any time:

i , zA , zB
vi , zA  vi , zB
Communicating one of 6 directions takes only 3
qubits
Searching by Walking
Can a quantum walk search a 2D grid efficiently?
(Maybe even n time instead of n log3n?)
Promising numerical evidence (courtesy N. Shenvi)
The Inflationary Turing
Machine
Before we were asking how the nature of space
affects query complexity
Now let’s ask how it affects computational
complexity
And let’s ground ourselves in the firm soil of
observation…
The New York Times Theory
of Cosmology
Closed
Flat
Open
With a vacuum
energy density
>0, geometry
is no longer
destiny
Source: Supernova
Cosmology Project
(Perlmutter et al.)
astro-ph/9812133
Evidence for >0
Scale Factor a(t)
(not to scale)
-Dominated Era
a(t) ~ ct again
Matter-Dominated Era
a(t) ~ t2/3
Inflation
a(t) ~ ct
10 billion years ABB:
Matter and  contribute
equally
14 billion years ABB:
P=?NP problem posed
Tipler’s Theory
As the big crunch draws near,
violent oscillations cause O(1)
computation steps to be
performed in shorter and
shorter intervals, so that time
appears subjectively infinite
Advantage of theory: Falsifiable
Disadvantage: Falsified
Bousso’s bound
hep-th/0010252
q
Largest number of bits
accessible to any one
observer: 3/  10122
Idea: Any experiment has a
beginning (p) and an end (q)
p
Consider causal diamond D:
intersection of future lightcone of p with past light-cone
of q
Use holographic principle to
upper-bound entropy in D
Lloyd’s bound
quant-ph/0110141
• Largest number of bits accessible so far:
(# of Planck times elapsed since the big bang)2
 (1061)2 = 10122
• Also uses holographic principle, but does not
depend on  > 0
• Why do the two bounds coincide? We live in a
transitional era, when both  and “dust” contribute
significantly to net energy:   0.7, dust  0.3
• Why should that be so? Dunno…
The Inflationary Turing Machine
0
1
1
1 00
0
1
The Inflationary Turing Machine
0
1
1
1 00
0
1
The Inflationary Turing Machine
0
1
1
1 0 0
0
1
The Inflationary Turing Machine
0
1
1
1 0 0
0
1
The Inflationary Turing Machine
0
1
1
1
0
0
0
1
At each time step t, a new tape square
(initialized to 0) is created after square k/ - t for
each integer k
Toy model for  > 0 spacetime
Let INF(1/) be the class of languages decided
by inflationary machine
Claim:
 1
1
1
DSPACE 
  INF    DSPACE  


 
Same for quantum analogues, BQSPACE and
BQINF
Open Problems In This Model
• In O(n) time, can we compute anything with an
nn square worktape that we couldn’t with a
nn square tape? I.e. how much of the
observable universe could we “take advantage
of” before it recedes?
• What about quantum-mechanically?
• What is the effect of including “gravity”?
Conclusions
• In a >0 spacetime, a quantum robot could
search a larger region than a classical one (not
assuming any time bound)
• Physics is a good source of “pure” CS questions
Quantum computing is just one example
Not all strings have n bits