Transcript Another version - Scott Aaronson

Quantum Computing and the Limits
of the Efficiently Computable
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
…
“OUR
STANDARD
MODEL”
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
Time Travel Computer
S. Aaronson and J. Watrous. Closed Timelike
Curves Make Quantum and Classical
Computing Equivalent, Proceedings of the Royal
Society A 465:631-647, 2009. arXiv:0808.2669.
Answer
Polynomial
Size Circuit
C
“Closed
Timelike
Curve
Register”
R CTC
R CR
0 0 0
“CausalityRespecting
Register”
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
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 basis
states, but you only get to
observe one of them
Any hope for a speedup
rides on the magic of
quantum interference
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
“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
Could be invoked to “explain” why adiabatic systems
have small spectral gaps, why protein folding gets stuck
in metastable states, why the Schrödinger equation is
linear, why time only flows in one direction…
Some of My Recent Research
BosonSampling (with Alex Arkhipov):
A proposal for a rudimentary optical
quantum computer, which doesn’t
seem useful for anything (e.g. breaking
codes), but does seem hard to
simulate using classical computers
Computational Complexity of Decoding Hawking
Radiation: Building on a striking recent proposal
by Harlow and Hayden—that part of the
resolution of the black hole information problem
might be that reconstructing the infalling
information from the Hawking radiation would
require an exponentially long computation
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 No-SuperSearch or related impossibility principles to
make progress in quantum gravity