Transcript What Google Won`t Find: The Ultimate Physical

What Google Won’t Find:
The Ultimate Physical Limits of Search
Scott Aaronson
University of Waterloo
Why Am I Speaking Here?
“Is Google God?”
—Thomas Friedman, NYT, 6/29/2003
My field—theoretical computer science—is
directly concerned with the question of how to
distinguish God from mortal impostors.
CS Theory in One Slide
Problem: “Given the Internet, are at least 50%
of web pages all reachable from one another?”
Each particular Internet is an instance
The size of the instance, n, is the number of
bits needed to specify it
An algorithm is polynomial-time if it uses at
most knc steps, for some constants k,c
P is the class of all problems that have
polynomial-time algorithms
NP: Nondeterministic
Polynomial Time
Does
37976595177176695379702491479374117272627593
30195046268899636749366507845369942177663592
04092298415904323398509069628960404170720961
97880513650802416494821602885927126968629464
31304735342639520488192047545612916330509384
69681196839122324054336880515678623037853371
49184281196967743805800830815442679903720933
have a factor ending in 7?
NP-hard: If you can solve it, you
can solve everything in NP
NP-complete: NP-hard and in NP
Is there a
Hamilton cycle
(tour that visits
each vertex
exactly once)?
NP-hard
Hamilton cycle
Graph 3-coloring
Satisfiability
Maximum clique
…
NPcomplete
NP
Graph connectivity
Primality testing
Linear programming
…
P
Halting problem
Counting problems
…
Factoring
Graph isomorphism
…
Audience Exam
Does P=NP?
Answer: No.
Extra credit: Prove it.
(You’ll win at least $1,000,000 if you do)
What could we do if we could
solve NP-complete problems?
If there actually were a machine with [running
time] ~Kn (or even only with ~Kn2), this would
have consequences of the greatest magnitude.
—Gödel to von Neumann, 1956
Then why is it so hard to
prove PNP?
Algorithms can be very clever
Gödel/Turing-style diagonalization
arguments don’t seem powerful enough
Combinatorial arguments face the
“Razborov-Rudich barrier”
But maybe there’s some
physical system that solves an
NP-complete problem just by
“relaxing” to its lowest energy
state?
-
Dip two glass plates with pegs
between them into soapy water
-
Let the soap bubbles form a minimum
Steiner tree connecting the pegs
Other Physical Systems
Spin glasses
Folding proteins
...
Well-known
to admit
“metastable”
states
DNA computers: Just highly parallel
ordinary computers
It’s Quantum Time
If an object can be in two states |0 or |1, then it can
also be in a superposition
|0 + |1
Here  and  are complex
amplitudes satisfying
||2+||2=1
If we observe, we see
|0 with probability ||2
|1 with probability ||2
Also, the object collapses to
whichever outcome we see
1
0 1
2
0
To modify a state
n

i 1
i
i
we can multiply the vector of amplitudes
by a unitary matrix—one that preserves
n

i 1
2
i
1
0 1





1
2
1
2
1  1  1 

2  12   20
      
1  01   11
2   2   2 
2
1
0 1
2
We’re seeing interference between positive and
negative amplitudes—the source of all “quantum
weirdness”
0
Quantum Computing
A quantum state of n “qubits” takes 2n complex
numbers to describe:

x0,1
x x
n
The goal of quantum computing is to exploit
this exponentiality in Nature.
Shor 1994: QuantumInteresting
computers can factor
integers in polynomial time
But what about NP-complete problems?
Bennett, Bernstein, Brassard, Vazirani
1994: “Quantum magic” won’t be enough
Even a quantum computer would need
~2n/2 queries to search an unsorted array
of size 2n for a single “marked” item
“Relativity Computing”
DONE
Analog Computing
Do the first step of a computation in 1 sec,
the second in ½ sec, the third in ¼ sec, …
Possible in “Malament-Hogarth spacetimes,”
which have naked singularities
Problem: The Planck scale (10-33 cm, 10-43
sec) seems to impose a fundamental limit!
Time Travel Computing
Naïve idea: Do the first step of a computation,
then go back in time and do the next step, etc.
Problem: Grandfather paradoxes
Resolution (Deutsch 1991): Use probability or
quantum theory. E.g. you’re born with ½ probability,
and if you’re born you go back and kill your
grandfather, ergo you’re born with ½ probability, etc.
Immediately suggests a model of computation,
which can be shown to be exactly as powerful as
the class PSPACE (A. 2005)
Quantum Gravity
Freedman, Kitaev, Wang 2000:
“Topological quantum field theories,” a
particular class of (2+1)-dimensional
quantum gravity theories, yield no
more power than ordinary quantum
computers
String theory? Loop quantum gravity?
It’d help if the physicists themselves
understood these things better!
“Anthropic Computing”
Guess a solution to an NP-complete
problem. If it’s wrong, kill yourself.
Suppose you could kill yourself in all
universes where a quantum computer fails,
then condition on remaining alive. What’s
the class of problems you could then solve
in polynomial time?
A. 2005: It’s exactly the classical complexity
class PP (Probabilistic Polynomial-Time),
which is believed to be strictly larger than NP
Second Law of
Thermodynamics
Proposed
Counterexamples
No Superluminal
Signalling
Proposed
Counterexamples
Intractability of
NP-complete
problems
Proposed
Counterexamples
Concluding Remark
I know this talk seemed pessimistic…
But I’m an optimist