Transcript Slide 1
NP-complete Problems and
Physical Reality
Scott Aaronson
Institute for Advanced Study
What could we do if we could
solve NP-complete problems?
Proof of
Riemann
hypothesis of
length 100000?
Circuit of size
100000 that
does best at
predicting stock
market data
Shortest
program that
outputs works
of Shakespeare
in 107 steps
If there actually were a machine with
[running time] ~Kn (or even only with
~Kn2), this would have consequences
of the greatest magnitude. That is to
say, it would clearly indicate that,
despite the unsolvability of the
Entscheidungsproblem, the mental
effort of the mathematician could be
completely (apart from the postulation
of axioms) replaced by machines.
—Gödel to von Neumann, 1956
Current Situation
Algorithms (GSAT, survey propagation, …) that
work well on random 3SAT instances, but
apparently not on “semantically hard” instances
No proof of PNP in sight
- Razborov-Rudich barrier
- Depth-3 threshold circuits evade us
- P vs. NP independent of set theory?
This Talk
Is there a physical system that solves NPcomplete problems in polynomial time?
Classical? Quantum? Neither?
Argument:
- This is a superb question to ask about physics
- NP is special (along with NPcoNP, one-way functions, …)
- Intractability as physical axiom?
-
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: Well-known to admit
“metastable” optima
Folding proteins: Same (e.g. prions).
But also, are local optima weeded out
by evolution?
DNA computers: Just highly parallel
ordinary computers
Analog Computing
Schönhage 1979: If we could compute
x+y, x-y, xy, x/y, x
for any real x,y in a single step, then we
could solve NP- and even PSPACEcomplete problems in polynomial time
Problem: The Planck Scale!
10-33 cm
Reasons to think spacetime is discrete
(1) Past experience with matter, light, etc.
(2) Existence of a natural minimum length scale
(3) Infinities of quantum field theory
(4) Black hole entropy bounds (1.41069 bits/m2)
(5) Area quantization in loop quantum gravity
(6) Cosmic rays above GZK cutoff (~1020 eV)
(7) Independence of AC and CH?
Quantum Computing
Shor 1994: Quantum computers can
factor in polynomial time
But can they solve NP-complete problems?
Bennett, Bernstein, Brassard, Vazirani 1994:
“Quantum magic” a la Grover won’t be enough
Given a “black box” function f:{0,1}n{0,1}, a
quantum computer needs (2n/2) queries to f
to find an x such that f(x)=1
Thus NPA BQPA relative to some oracle A
Quantum Advice
BQP/qpoly: the class of problems solvable in
bounded-error quantum polynomial time, given
a polynomial-size “quantum advice state” |n
that depends only on the input length n
To many quantum computing skeptics,
|n is an “exponentially long vector.”
So, could it encode the solutions to
every SAT instance of length n?
A. 2004: NPA BQPA/qpoly relative to some
oracle A. Proof based on “direct product
theorem” for quantum search
Quantum Adiabatic Algorithm
(Farhi et al. 2000)
Hi
Hamiltonian with
easily-prepared
ground state
(1-s)Hi+sHf
Hf
Ground state
encodes solution
to 3SAT instance
Quantum analogue of simulating annealing
Numerical data suggested polynomial running time
van Dam, Mosca, Vazirani 2001; Reichardt 2004:
Takes exponential time on some 3SAT instances
Topological Quantum Field
Theories (TQFT’s)
Freedman, Kitaev, Wang 2000:
Equivalent to ordinary quantum computers
“Non-Collapsing Measurements”
To solve Graph Isomorphism: Given G and H,
prepare
1
0 G
2n !
1 H
Sn
After we measure third register, first two registers
will have the form
0 1
2
if G H,
b if not
If only we could measure both ||0 and ||1
without collapsing, we’d solve the problem…
(Generalizes to all problems in SZK)
A. 2002: Any quantum algorithm needs (N1/5)
queries to decide w.h.p. whether a function
f:{1,…,N}{1,…,N} is one-to-one or two-to-one
Improved by Shi, Kutin, Ambainis, Midrijanis
Yields oracle A such that SZKA BQPA
A. 2004: On the other hand, if we could sample the
entire history of a hidden variable (satisfying a
reasonable axiom), we could solve anything in SZK
But still not NP-complete problems, relative to an
oracle!
“Special Relativity Computing”
To get a factor-k speedup:
DONE
v
1
1
c
k
2
Exponentially close to c if
k is exponentially large
So need an exponential
amount of energy.
Where does it come from?
Nonlinear Quantum Mechanics
Abrams & Lloyd 1998: Could use to solve
NP-complete and even #P-complete
problems in polynomial time
1 solution to NP-complete problem
No solutions
Time Travel Computing
(Adapted from Brun 2003)
C(x)
C
x
Causal
loop
Assumption (Deutsch): Probability
distribution over x{0,1}n must be a
fixpoint of polynomial-size circuit C
Model: We choose C, then a fixpoint distribution D over
x is chosen adversarially, then an xD is sampled
To solve SAT: Let C(x)=x if x is a satisfying
assignment, C(x)=x+1(mod 2n) otherwise
To solve PSPACE-complete problems:
Exercise for the audience…
Time Travel Computing with 1 Looping Bit
Chronology-respecting bit
(Adapted from Bacon 2003)
xy
x
Causal
loop
x
y
Suppose
Pr[x=1] = p,
Pr[y=1] = q
Then consistency
requires p=q
So Pr[xy=1]
= p(1-q) + q(1-p)
= 2p(1-p)
Quantum Gravity
Spacetimes that have to be treated as
identical if their metric structures are
isomorphic?
Probabilities that don’t sum to 1 unless
they’re normalized by hand?
Highly nonlocal unitaries
implementable in polynomial time?
“Anthropic Computing”
Guess a solution to an NP-complete problem.
If it’s wrong, kill yourself.
Doomsday alternative:
If solution is right, destroy human race.
If wrong, cause human race to survive into far
future.
Classically, anthropic computing lets us do
exactly BPPpath (between MA and PP)
A. 2003: Quantumly, it lets us do exactly PP
Second Law of
Thermodynamics
Proposed
Counterexamples
No Superluminal
Signalling
Proposed
Counterexamples
Intractability of
NP-complete
problems
Proposed
Counterexamples