Transcript Can computer science help physicists resolve the

Can computer science help physicists
resolve the firewall paradox?
Scott Aaronson (MIT)
Papers and slides at www.scottaaronson.com
THEORETICAL
PHYSICISTS
Me
But in this talk, I’ll tell you about a developing story,
centered around the black hole information problem,
that’s been bringing computer science and physics
together in a remarkable and unexpected way—going
beyond the connection established in the 1990s by
quantum computing
Black Holes in Classical GR
No hair: just mass, charge, and angular
momentum
Black Holes in Quantum Mechanics
Jacob Bekenstein: Classical black holes seem
to violate the Second Law of Thermodynamics!
To fix, assume they somehow have an entropy
proportional to the square of the surface area
of the event horizon
Stephen Hawking: That’s absurd! If true, it
would imply that black holes have a
temperature and radiate … no, wait …
Modern Picture
Black holes are the most efficient hard
disks in the universe: they store ~1069
bits per square meter of surface area
(any denser arrangement will just
collapse to a black hole)
If you try to do more than 1043
computation steps per second, that will
also trigger collapse to a black hole
Information Problem
The QFT calculation that says in the first place that the
Hawking radiation exists, also predicts that it should be
thermal: that is, completely uncorrelated with
whatever
information
fell intothe
theinformation
black hole
So why
not just assume
somehow gets out in the Hawking radiation?
Yet all known laws of fundamental
physics, from Galileo through
quantum field theory, are perfectly
reversible (information-preserving)
The Xeroxing Problem
The No-Cloning Theorem says there’s no procedure to copy
an unknown quantum state
 0  1
 0
So then how could the same state
| both be permanently in the hole
(as seen by the infalling observer),
and out in the Hawking radiation (as
seen by the external observer)?
  1  0   1 


Complementarity
Susskind, ‘t Hooft 1990s
“It’s OK, as long as the
same observer never
measures both copies
of | !”
Jumping into a black hole: just a convoluted way of
measuring the same quantum states that were already
there outside the black hole, and on the event horizon
The AMPS Firewall Argument
(2012)
“When people much more expert than me
admitted that they also didn’t understand black
hole complementarity”
No longer a dispute about formalism: now an
actual (zany) thought experiment, such that if you
claim to understand black holes, then you must
be able to say what the infalling observer would
experience if this experiment were done.
Digression: Quantum Entanglement
Remember, if anyone asks,
I’ll be spinning up and you’ll
be spinning down…
Bell’s
Theorem
“Monogamy of
entanglement”:
Entanglement among 3 or
more parties just reduces
to classical correlation
among any 2 of them
0 0 0 1 1 1
2
What Do “Generic” Many-Particle
Entangled Pure States Look Like?
(Again, pure quantum information theory, nothing to
do with black holes)
Subset of fewer than half
of the particles: In a
completely random
(“maximally mixed”) state
Subset of more than half of
the particles: Not maximally
mixed. Any one particle in
the subset is entangled with
the remaining ones
In quantum field theory, the
“vacuum” has huge amounts of
short-range entanglement!
No entanglement  No smooth vacuum
The Firewall Paradox (AMPS 2012)
R = Faraway Hawking Radiation
B = Just-Emitted Hawking Radiation
Near-maximal
entanglement
H = Interior of
“Old” Black Hole
(with known pure
starting state)
Also near-maximal
entanglement
Violates monogamy of entanglement!
Harlow-Hayden
Argument
Striking argument that Alice’s first task, decoding the
entanglement between R and B, would take time
exponential in the number of qubits of the black hole (so
67
67
10
not 10 years but 2 )—by which point, the black hole
would’ve long ago evaporated anyway
Complexity to the rescue of quantum field theory?
Are they saying that an inconsistency in the laws of
physics is OK, as long as it takes exponential time to
discover it? NO! “Inconsistency” is only in low-energy
effective theories; question is where they break down
Digression About
Quantum Computers
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 classically—
and had the idea to overcome
that problem using computers
that were themselves quantum
Exponential
(inefficient)
Polynomial
(efficient)
Not Even a Quantum Computer
Could Do Everything!
 

x
 x
x1,, 2 
n
Exponentially-many
states, but you only get to
observe one of them
Any hope for a speedup
relies on the magic of
quantum interference—
amplitudes for wrong
answers cancelling out
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
The Collision Lower Bound
Problem: Decide whether a function f is one-to-one or
two-to-one, promised that one of those is the case
10 4 1 8 7 9 11 5 6 4 2 10 3 2 7 9 11 5 1 6 3 8
Models the breaking of collision-resistant hash
functions—a central problem in cryptanalysis—as well
as graph isomorphism

Aaronson 2001: If f has 2n inputs, and is only accessible
as a “black box,” then any quantum algorithm to solve
the collision problem takes at least ~2n/5 steps
(improved to ~2n/3 by Yaoyun Shi, which is optimal)
Evidence that problems of this kind are not in BQP
Harlow and Hayden’s Theorem
Let’s model a black hole by a set of qubits that start in a
known state, and the physics of a black hole by a known
polynomial-size quantum circuit acting on those qubits.
Suppose that, for any circuit C, there were another
polynomial-size quantum circuit to solve the “HarlowHayden decoding problem,” of acting on R to produce an
entangled pair with B. Then there’d also be a polynomialtime quantum algorithm for the collision problem!
My Improvement to HarlowHayden
Decoding entanglement between R and B is generically
hard, assuming only that there exists a one-way function
that’s hard to invert using a quantum computer
Indeed, even decoding classical correlation is hard
Is the geometry of spacetime protected by
an armor of computational complexity?
Computational Complexity and
AdS/CFT
AdS/CFT correspondence:
A duality between anti deSitter space in D dimensions,
and conformal field theory in
D-1 dimensions.
Considered one of the main
achievements of theoretical
physics of the past 30 years—
”a place where quantum
gravity works”
Thermofield Double State
A state in AdS involving two regions of spacetime
connected only by a wormhole. The wormhole is nontraversable, because it expands faster than light, before
pinching off in a singularity (after either finite or infinite time,
depending on one’s coordinates)
What’s the CFT dual of the
thermofield double state?
TIME
Just a bunch of qubits that
start out in a simple state,
and get more and more
scrambled as time goes on
1
2
n
x
x0,1n
 x
Problem: Something being
scrambled quickly reaches a
state of “maximum
scrambling” (as measured in
the usual ways). Yet the
wormhole continues to get
longer for exponential time!
Susskind’s Question: What function of the CFT state can we
point to, that’s “dual” to wormhole length on the AdS side?
His Proposal: The quantum circuit complexity—that is, the
number of quantum logic gates in the smallest circuit that
Theorem
Suppose
prepares
the(Aaronson-Susskind):
state from a simple initial
statethe scrambling
transformation is complicated enough to encode
n
2
universal computation. Then after exponential time,
Quantum
the
circuit complexity of the state will be more than
circuit
polynomial, unless PSPACE  PP/poly.
complexity
0
0
Time t
2n
His Question for Me: But does the circuit complexity
actually increase like this—at least for “natural” scrambling
dynamics, and under some plausible hardness assumption?
A Favorite Research Direction
“Not just for black holes and quantum gravity, for lots of things”
Understand the sizes of the smallest quantum circuits
needed to Relevant
prepare to
states
and one
apply
transformations.
whether
can
reverse Harlow and
Relate this
to the logic,
quantum
circuit
complexity
of solving
Hayden’s
and give
a sufficient
condition
for the
“traditional”
problems
with to
yes-or-no
firewall
experiment
be doableanswers
in polynomial time
Example question (Aaronson-Kuperberg 2006): For every
transformation T of n-qubit quantum states, is there a
decision problem such that a magic box for solving it
would let you apply T in only poly(n) steps?
Easy to show: for every n-qubit state |, there’s a
decision problem such that a magic box for solving it
would let you prepare | in only poly(n) steps
Now, to end this talk with something crazy
Wiesner 1969: Because of the No-Cloning Theorem, in principle it’s
possible to have “quantum money,” where each bill includes qubits that
are physically impossible to duplicate.
Bennett et al. 1982: Can even combine with cryptography so the bank
doesn’t need to remember stuff about every bill in circulation
Quantum resistant
one-way functions
Cryptographic
quantum money
Firewall
experiment
is hard