Transcript Quantum Complexity and Fundamental Physics

Quantum Complexity and
Fundamental Physics
Scott Aaronson
MIT
RESOLVED: That the results of
quantum complexity research over
the last two decades have deepened
our understanding of physics.
That this represents an intellectual
“payoff” from quantum computing,
whether or not scalable QCs are ever
built.
A Personal Confession…
While proving theorems about QCMA/qpoly and
QMAlog(2), sometimes even I wonder whether it’s all
just an irrelevant mathematical game
But then I meet distinguished physicists
who say things like:
“A quantum computer is obviously just a souped-up analog
computer: continuous voltages, continuous amplitudes, what’s
the difference?”
“A quantum computer with 400 qubits would have ~2400
classical bits, so it would violate a cosmological entropy bound”
“My classical cellular automaton model can explain everything
about quantum mechanics!
(How to account for, e.g., Schor’s algorithm for factoring prime numbers is a detail
left for specialists)”
“Who cares if my theory requires Nature to solve the Traveling
Salesman Problem in an instant? Nature solves hard problems
all the time—like the Schrödinger equation!”
The biggest implication of QC for
fundamental physics is obvious:
“Shor’s Trilemma”
Because of Shor’s factoring algorithm, either
1. the Extended Church-Turing Thesis—the
foundation of theoretical CS for decades—is wrong,
That’s why YOU
2. textbookshould
quantum
mechanics is wrong, or
care
3. there’sabout
a fastquantum
classical factoring algorithm.
computing
All three seem like crackpot speculations.
At least one of them is true!
Rest of the Talk
Ten of my favorite quantum complexity theorems …
and their relevance for physics
PART I. BQP-Infused Quantum Foundations
BQP  P#P, BBBV lower bound, collision lower bound,
limits of random access codes
PART II. BQP-Encrusted Many-Body Physics
QMA-completeness, the limits of adiabatic computing,
search by quantum walk
PART III. Quantum Gravity With a Side of BQP
TQFT’s, postselection & closed timelike curves, black
holes as mirrors
PART I. BQP-Infused Quantum
Foundations
BQP
Quantum Computing Is Not Analog
is a linear equation, governing
d
i
 H  quantities (amplitudes) that are
not directly observable
dt
This fact has many profound implications, such as…
The Fault-Tolerance
Theorem
Absurd precision in
amplitudes is not
necessary for
scalable quantum
computing
EXP
P#P
BQP
QC’s Don’t Provide Exponential
Speedups for Black-Box Search
I.e., if you want more than the N Grover speedup
for solving an NP-complete problem, then you’ll
The “BBBV
Noproblem
SuperSearch
Principle” can even
need
to exploit
structure
be applied
in physicsBrassard,
(e.g., to lower-bound
[Bennett,
Bernstein,
Vazirani 1997]
tunneling times)
Is it a historical accident that quantum mechanics
courses teach the Uncertainty Principle but not the
“No SuperSearch Principle”?
Computational Power of Hidden Variables
Consider the problem of breaking a cryptographic
hash function: given a black box that computes a 2-to-1
function f, find any x,y pair such that f(x)=f(y)
Can also reduce graph
isomorphism to this problem

QCs can “almost” find collisions with just one query to f!
Conclusion [A. 2005]:
N
x mechanics,
y
1
If, in a hidden-variable theory like Bohmian
f x 
x f x 
nd
your N
whole
life trajectoryMeasure
flashed2before you2at the
x 1
register
moment of your death, you
could solve problems that are
(probably)
intractable
even for
quantum
computers
Nevertheless,
any quantum
algorithm
needs
(N1/3)

queries tonot
find
a collision [A.-Shi
2002]
(Probably
NP-complete
problems
though)
The Absent-Minded Advisor Problem

Can you give your graduate
student a state | with poly(n)
qubits—such that by measuring
| in an appropriate basis, the
student can learn your answer to
any yes-or-no question of size n?
NO [Ambainis, Nayak, Ta-Shma, Vazirani 1999]
Some consequences:
BQP/qpoly  PostBQP/poly [A. 2004]
Any n-qubit state  can be “PAC-learned” using O(n) sample
measurements—exponentially better than tomography [A. 2006]
One can give a local Hamiltonian H on poly(n) qubits, such that
any ground state of H can be used to simulate  on all yes/no
measurements with small circuits [A.-Drucker 2009]
PART II. BQP-Encrusted
Many-Body Physics
BQP
QMA-completeness
One of the great achievements of quantum complexity
theory, initiated by Kitaev
Just one of many things we learned
from this theory:
In general, finding a ground state of a
1D nearest-neighbor Hamiltonian is
just as hard as finding the ground state
of any Hamiltonian
[Aharonov, Gottesman, Irani, Kempe 2007]
The Quantum Adiabatic Algorithm
An amazing quantum analogue of simulated annealing
[Farhi, Goldstone, Gutmann et al. 2000]
Seems to come tantalizingly close to solving NP-complete
problems in polynomial time! But…
Why do these two energy
levels almost “kiss”?
One answer: because
NP-complete problems
are hard!
[Van Dam, Mosca, Vazirani
2001; Reichardt 2004]
Quantum Walks
To develop a quantum walk
algorithm for spatial search,
algorithmists essentially had to
rediscover the Dirac equation
[Childs, Goldstone 2004]
A free particle in a 2D box
To develop a quantum walk
algorithm for game-tree search,
they would’ve had to rediscover
scattering theory
[Farhi, Goldstone, Gutmann 2007]
To develop a quantum walk
algorithm for graph isomorphism,
will we need to rediscover some
more physics? [Bacon]
PART III. Quantum Gravity With a
Side of BQP
BQP
Topological Quantum Field Theory
TQFTs
BQP
Aharonov, Jones, Landau 2006
Jones
Polynomial
Beyond Quantum Computing?
If QM were nonlinear, one could exploit
that to solve NP-complete problems in
polynomial time [Abrams & Lloyd 1998]
Quantum computers with postselected
measurements could solve not only
NP-complete problems, but even
counting problems [A. 2005]
Answer
C
R CTC
R CR
000
Quantum computers with closed
timelike curves (i.e. time travel) could
solve PSPACE-complete problems—but
not more than that [A.-Watrous 2008]
Black Holes as Mirrors
Against many physicists’ intuition, information dropped into a black
hole seems to come out as Hawking radiation almost
immediately—provided you know the black hole’s state before the
information went in [Hayden & Preskill 2007]
Their argument uses explicit constructions of approximate unitary
2-designs
For Even More Interdisciplinary
Excitement, Here’s What You
Should Look For
A plausible complexity-theoretic story for how
quantum computing could fail (see A. 2004)
Intermediate models of computation between P and
BQP (highly mixed states? restricted sets of gates?)
Foil theories that lead to complexity classes slightly
larger than BQP (only example I know of: hidden variables)
A sane notion of “quantum gravity polynomial time”
(first step: a sane notion of “time”?)
A bold (but true) hypothesis linking
complexity and fundamental physics…
There is no physical means to solve
NP-complete problems in polynomial time.
Encompasses NPP, NPBQP, NPLHC…
My Prediction: Someday, this hypothesis will be about as
canonical as the 2nd Law or no superluminal signalling
GOLDBACH
CONJECTURE:
TRUE
NEXT QUESTION