Transcript Another version - Scott Aaronson

Quantum Computing and the Limits
of the Efficiently Computable
Scott Aaronson
MIT
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?
Complexity Theory 101
Problem: “Given a flight map, is every airport
reachable from every other in 5 flights or less?”
Any specific map is an instance of the problem
The size of an instance, n, is the number of bits
used 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 for which there’s a
deterministic, polynomial-time algorithm that
correctly solves every instance
NP: Nondeterministic Polynomial
Time
Does
379765951771766953797024914793741172726275933019
504626889963674936650784536994217766359204092298
415904323398509069628960404170720961978805136508
024164948216028859271269686294643130473534263952
048819204754561291633050938469681196839122324054
336880515678623037853371491842811969677438058008
30815442679903720933
have a factor ending in 7?
NP-hard: If you can solve it, then you
can solve every NP problem
NP-complete: NP-hard and in NP
Can you send
your passenger
on a round-trip
that visits each
city once?
NP-hard
Hamilton cycle
Steiner tree
Graph 3-coloring
Satisfiability
Maximum clique
…
Graph connectivity
Primality testing
Matrix determinant
Linear programming
…
NPcomplete
NP
P
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
Q: Hey, wasn’t P≠NP proved this summer?
A: No.
P/NP FAQ
Q: Why is PNP so hard to prove?
A: Basically because all known approaches, if they worked, would
also prove other things that are false (e.g., “2SAT is hard”)
Q: How sure are you that PNP?
A: If we were physicists, we would’ve long ago declared it a “law
of nature” and been done with it…
Q: If almost everyone believes PNP, why bother proving it?
A: It’s not the destination, it’s what else we’ll learn along the way
Q: Could it be that PNP is Gödel-undecidable?
A: Maybe, but Fermat’s Last Theorem took 350 years! We’ve only
been at this 40 years and know way more than when we started
Q: What if P=NP, but the algorithm took n10000 steps?
A: Then we’d change the question
Q: Even if PNP, can’t there be clever heuristics that often work?
A: Yes, but cleverness would be “provably necessary”
An important presupposition underlying P vs. NP is the...
Extended Church-Turing Thesis
“Any physically-realistic computing device can be
simulated by a deterministic (or maybe probabilistic) Turing machine,
with at most polynomial overhead in time and memory”
So how sure are we of this thesis?
Have there been serious challenges to it?
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”
Other Approaches
Protein folding: Can also get stuck at local optima (e.g.,
Mad Cow Disease)
DNA computers: Just massively parallel classical computers
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
Shor 1994: A quantum computer, if built, could factor
integers (and hence break RSA) in polynomial time
Quantum algorithms: “The power of 2n complex numbers
working for YOU”
But remember: factoring isn’t thought to be NP-complete!
To this day (and contrary to popular misconception), we don’t know
a fast quantum algorithm to solve NP-complete problems
(though not surprisingly, we also can’t prove there isn’t one)
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!)
So, is there any quantum algorithm for NP-complete problems
that would exploit their structure?
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
Nonlinear variants of the Schrödinger
Equation
Abrams & Lloyd 1998: If quantum mechanics were
nonlinear, one could exploit that to solve NPcomplete problems in polynomial time
1 solution to NP-complete problem
No solutions
Closed Timelike Curves (CTCs)
Here’s a polynomial-time algorithm to solve NP-complete
problems (only drawback is that it requires time travel):
Read an integer x{0,…,2n-1} from the future
If x encodes a valid solution, then output x
Otherwise, output (x+1) mod 2n
If valid solutions exist, then the only fixed-points of the
above program input and output them
Building on work of Deutsch, [A.-Watrous 2008] defined a
formal model of CTC computation, and showed that in
both the classical and quantum cases, it has exactly the
power of PSPACE (believed to be even larger than NP)
Anthropic Computing
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’re 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!
Relativity Computer
DONE
Zeno’s Computer
Time (seconds)
STEP 1
STEP 2
STEP 3
STEP 4
STEP 5
“The No-SuperSearch Postulate”
There is no physical means to solve NP-complete
problems in polynomial time.
Includes PNP as a special case, but is stronger
No longer a purely mathematical conjecture, but also a
claim about the laws of physics
If true, would “explain” why adiabatic systems have
small spectral gaps, the Schrödinger equation is linear,
CTCs don’t exist...
Question: What exactly does it mean to “solve” an NPcomplete problem?
Example: It’s been known for decades that, if you send n
identical photons through a network of beamsplitters, the
amplitude for the photons to reach some final state is given
If you can’t
observe
the answer,
it doesn’t
count!
byLesson:
the permanent
of an
nn matrix
of complex
numbers
n
(Recently, Alex Arkhipov and I gave the first evidence
that
even the observed output distribution
Per A of
 such a linear-optical
ai , i 
network would be hard to simulate on a classical
 S n i 1computer—
but the argument was necessarily more subtle)
  
But the permanent is #P-complete
(believed even harder than NPcomplete)! So how can Nature do
such a thing?
Resolution: The amplitudes aren’t directly observable, and
require exponentially-many probabilistic trials to estimate
Conclusion
One could imagine worse research agendas than the
following:
Prove P≠NP (better yet, prove factoring is classically hard, implying P≠BQP)
Prove NPBQP—i.e., that not even quantum computers
can solve NP-complete problems
Build a scalable quantum computer
(or even more interesting, show that it’s impossible)
Determine whether all of physics can be simulated by a
quantum computer
“Derive” as much physics as one can from NoSuperSearch and other impossibility principles
www.scottaaronson.com/talks
www.scottaaronson.com/papers
www.scottaaronson.com/blog