Transcript Slide 1
Limits on Efficient Computation
in the Physical World
Scott Aaronson
MIT
Things we never see…
GOLDBACH
CONJECTURE:
TRUE
NEXT QUESTION
Warp drive
Perpetuum mobile
Übercomputer
$3 billion
But does the absence of these devices
have any scientific importance?
Goal of talk: Explain why the impossibility of
übercomputers is a great question for 21st-century
science
CS Theory 101
Problem: “Given a graph, is it connected?”
Each particular graph 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 prime 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
Steiner tree
Graph 3-coloring
Satisfiability
Maximum clique
…
NPcomplete
NP
Graph connectivity
Primality testing
Matrix determinant
Linear programming
…
P
Matrix permanent
Halting problem
…
Factoring
Graph isomorphism
…
Does P=NP?
The (literally) $1,000,000 question
Q: What if P=NP, and the algorithm takes n10000 steps?
A: Then we’d just change the question!
Q: Why is it so hard to prove PNP?
A: Because polynomial-time algorithms are so rich
What about quantum
computers?
BQP: Bounded-Error Quantum Polynomial-Time
Shor 1994: BQP contains integer factoring
But factoring isn’t believed to be NP-complete.
So the question remains: can quantum computers solve
NP-complete problems efficiently?
Bennett et al. 1997: “Quantum magic” won’t be enough
If we throw away the problem structure, and just consider
a “landscape” of 2n possible solutions, even a quantum
computer needs ~2n/2 steps to find a correct solution
Quantum Adiabatic Algorithm
(Farhi et al. 2000)
Hi
Hamiltonian with
easily-prepared
ground state
Hf
Ground state encodes
solution to NPcomplete problem
Problem: Eigenvalue gap can be
exponentially small
Other Alleged Ways to Solve
NP-complete Problems
Protein folding: Can also get stuck at local optima
(e.g., Mad Cow Disease)
DNA computers: A proposal for massively parallel
classical computing
The cognitive science approach: Think about it
really hard
My Personal Favorite
Dip two glass plates with pegs between them into
soapy water; let the soap bubbles form a minimum
“Steiner tree” connecting the pegs (thereby solving a
known NP-complete problem)
What would the world actually be like
if we could solve NP-complete
problems efficiently?
Proof of Riemann hypothesis
with 10,000,000 symbols?
Shortest efficient description
of stock market data?
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
The NP Hardness Assumption
There is no physical means to solve NP
complete problems in polynomial time.
Alright, what can we say about this assumption?
• Implies, but
is
stronger
than,
PNP
Rest of talk: Try to give
indications
• As falsifiable
as it getsthat it is
• Consistent with currently-known physical theory
• Scientifically fruitful?
1. “Relativity Computing”
DONE
2. Topological Quantum Field
Theories (TQFT’s)
Freedman, Kitaev, Wang 2000:
Equivalent to ordinary quantum computers
3. Nonlinear variants of the
Schrödinger Equation
Abrams & Lloyd 1998: If quantum mechanics
were nonlinear, one could exploit that to solve
NP-complete problems in polynomial time
Can take as an
additional
argument for why
QM is linear
1 solution to NP-complete problem
No solutions
4. Anthropic Principle
Foolproof way to solve NP-complete problems in
polynomial time (at least in the Many-Worlds Interpretation):
First guess a random solution. Then, if it’s wrong,
kill yourself
Technicality: If there are no solutions, you’d seem
to be out of luck!
Solution: With tiny probability don’t do anything. Then, if you find
yourself in a universe where you didn’t do anything, there probably were
no solutions, since otherwise you would’ve found one
What if we combine quantum computing
with the Anthropic Principle?
I.e. perform a polynomial-time quantum
computation, but where we can measure a
qubit and assume the outcome will be |1
Leads to a new complexity class:
PostBQP (Postselected BQP)
A. 2005: PostBQP=PP—and this yields a 1page proof of the Beigel-Reingold-Spielman
theorem, that PP is closed under intersection
5. Time Travel
Everyone’s first idea for a time travel computer:
Do an arbitrarily long computation, then send the
answer back in time to before you started
THIS DOES NOT WORK
Why not?
• Ignores the Grandfather Paradox
• Doesn’t take into account the computation you’ll have
to do after getting the answer
Deutsch’s Model
A closed timelike curve (CTC) is a computational
resource that, given an efficiently computable function
f:{0,1}n{0,1}n, immediately finds a fixed point of f—
that is, an x such that f(x)=x
Admittedly, not every f has a fixed point
But there’s always a distribution D such that f(D)=D
Probabilistic Resolution of the Grandfather Paradox
- You’re born with ½ probability
- If you’re born, you back and kill your grandfather
- Hence you’re born with ½ probability
Let PCTC be the class of problems solvable in
polynomial time, if for any function f:{0,1}n{0,1}n
described by a poly-size circuit, we can immediately get
an x{0,1}n such that f(m)(x)=x for some m
Theorem: PCTC = PSPACE
What if we perform a quantum
computation around a CTC?
Let BQPCTC be the class of problems solvable in
quantum polynomial time, if for any superoperator E
described by a quantum circuit, we can immediately get
a mixed state such that E() =
Clearly PSPACE = PCTC BQPCTC
A., Watrous 2008:
BQPCTC = PSPACE
If closed timelike curves exist, then quantum
computers are no more powerful than classical ones
Concluding Remarks
Are NP-complete problems intractable in the physical
universe? I conjecture that they are, but fully
understanding why will bring in:
• Math and computer science (duh): The P vs. NP
question
Prediction: The “NP Hardness Assumption” will
eventually
be seen as
analogous
to Second
Law
• Quantum
mechanics:
The
NP vs. BQP
question
of Thermodynamics or the impossibility of
• Other physics: superluminal
Quantum fieldsignaling
theory, quantum gravity,
closed timelike curves…
• Biology, cognitive science, economics?
Open Question: What is “polynomial
time” in quantum gravity?
Scientific American, March 2008:
www.scottaaronson.com