Transcript Computational Complexity and Fundamental Physics

Computational Complexity and
Fundamental Physics
Scott Aaronson (MIT)
www.scottaaronson.com
Things we never see…
GOLDBACH
CONJECTURE:
TRUE
NEXT QUESTION
Warp drive
Perpetuum mobile
Übercomputer
The (seeming) impossibility of the first two machines
reflects fundamental principles of physics—Special
Relativity and the Second Law respectively
So what about the third one? What are the ultimate
physical limits on what can be feasibly computed? And
do those limits have any implications for physics?
NP-hard
All NP problems are efficiently
reducible to these
Hamilton cycle
Steiner tree
Graph 3-coloring
Satisfiability
Maximum clique
…
NPcomplete
NP
Efficiently
verifiable
Graph connectivity
Primality testing
Matrix determinant
Linear programming
…
P
Efficiently
solvable
Matrix permanent
Halting problem
…
Factoring
Graph isomorphism
…
Does P=NP?
The (literally) $1,000,000 question
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
An important presupposition underlying P vs. NP is the
The Extended Church-Turing
Thesis (ECT)
“Any physically-realistic computing
device can be simulated by a
deterministic or probabilistic Turing
machine, with at most polynomial
overhead in time and memory”
But how sure are we of this thesis?
What would a challenge to it look like?
Old proposal: 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-hard
problem “instantaneously”
Relativity Computer
DONE
Zeno’s Computer
Time (seconds)
STEP 1
STEP 2
STEP 3
STEP 4
STEP 5
Ah, but what about
quantum computing?
(you knew it was coming)
Quantum mechanics: “Probability theory with minus signs”
(Nature seems to prefer it that way)
In the 1980s, Feynman, Deutsch, and others noticed that
quantum systems with n particles seemed to take ~2n time
to simulate—and had the amazing idea of building a
“quantum computer” to overcome that problem
Quantum computing: “The power of 2n complex numbers
working for YOU”
Quantum Mechanics in One Slide
Probability Theory:
Quantum Mechanics:
 s11  s1n   p1   q1 

   
          
s  s  p  q 
nn   n 
 n1
 n
 u11  u1n   1   1 

   
          
 u  u      
nn   n 
 n1
 n
pi  0,
n
p
i 1
i
1
Linear transformations
that conserve 1-norm of
probability vectors:
Stochastic matrices
 i  C,
n

i 1
2
i
1
Linear transformations
that conserve 2-norm of
amplitude vectors:
Unitary matrices
Journalists Beware:
A quantum computer is NOT like a
massively-parallel classical computer!
 

x
 x
x1,, 2 
n
Exponentially many
possible measurement
outcomes, but you only
see one, probabilistically!
Any hope for a speedup rides
on the magic of interference
between positive and negative
contributions to an amplitude
BQP (Bounded-Error Quantum Polynomial-Time): The class
of problems solvable efficiently by aInteresting
quantum computer,
defined by Bernstein and Vazirani in 1993
Shor 1994: Factoring integers is in BQP
NP-complete
NP
BQP
Factoring
P
Can QCs Actually Be Built?
Where we are now: A quantum computer has factored 21
into 37, with high probability (Martín-López et al. 2012)
Why is scaling up so hard? Because of decoherence:
unwanted interaction between a QC and its external
environment, “prematurely measuring” the quantum state
A few skeptics, in CS and physics, even argue that building
a QC will be fundamentally impossible
I don’t expect them to be right, but I hope they are! If so,
it would be a revolution in physics
And for me, putting quantum mechanics to the test is the
biggest reason to build QCs—the applications are icing!
Key point: factoring is not believed to be NP-complete!
And today, we don’t believe quantum computers can solve
NP-complete problems in polynomial time in general
(though not surprisingly, we can’t prove it)
Bennett et al. 1997: “Quantum magic” won’t be enough
If you throw away the problem structure, and just consider an
abstract “landscape” of 2n possible solutions, then even a
quantum computer needs ~2n/2 steps to find the correct one
(That bound is actually achievable, using Grover’s algorithm!)
If there’s a fast quantum algorithm for NP-complete problems,
it will have to exploit their structure somehow
Quantum Adiabatic Algorithm
(Farhi et al. 2000)
Hi
Hamiltonian with easilyprepared ground state
Hf
Ground state encodes solution
to NP-complete problem
Problem: “Eigenvalue gap”
can be exponentially small
Most striking application so far of complexity
to fundamental physics?
Hawking 1970s: Black holes radiate
The radiation seems thermal (uncorrelated with whatever
fell in)—but if quantum mechanics is true, then it can’t be
Susskind et al. 1990s: “Black-hole complementarity.” In
string theory / quantum gravity, the Hawking radiation
should just be a scrambled re-encoding of the same
quantum states that are also inside the black hole
The Firewall Paradox [Almheiri et al. 2012]
If the black hole interior is “built”
out of the same qubits coming out as
Hawking radiation, then why can’t
we do something to those Hawking
qubits (after waiting ~1067 years for
enough to come out), then dive into
the black hole, and see that we’ve
completely destroyed the spacetime
geometry in the interior?
Entanglement among
Hawking photons detected!
Harlow-Hayden 2013: Sure, there’s some unitary
transformation that Alice could apply to the Hawking
radiation, that would generate a “firewall” inside the event
horizon. But how long would it take her to apply it?
They gave evidence that this problem would take
exponential time, even for a quantum computer—in which
case, long before one had made a dent in the problem, the
black hole would’ve already evaporated anyway!
Their evidence relied on a lower bound on the number of
steps needed by a quantum computer to find collisions
(i.e., duplicates in a list of numbers), which I proved in 2002
Recently I improved their argument, so that it no longer
needs the collision lower bound, just one-way functions
Conclusion
My suggested research agenda:
Prove P≠NP
Prove that not even quantum computers can solve NPcomplete problems
Build a scalable quantum computer
(or even more interesting, show that it’s impossible)
Clarify whether all of known physics can be simulated by a
quantum computer
Use computational complexity ideas to make progress
toward a quantum theory of gravity