Transcript The Future of Computer Science

Quantum Computing and the Limits
of the Efficiently Computable
Scott Aaronson ‘00
MIT
Moore’s Law
Extrapolating: Robot uprising?
But even a killer robot would still be
“merely” a Turing machine, operating on
principles laid down in the 1930s…
=
And it’s conjectured that thousands of
interesting problems are inherently
intractable for Turing machines…
Is there any feasible way to solve
these problems, consistent with
the laws of physics?
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”
What About Quantum Mechanics?
“Like probability, but with minus signs”
Probability Theory:
 s11

 
s
 n1



s1 n   p 1   q 1 

  
       
s nn   p n   q n 
Quantum Mechanics:
 u 11

 
u
 n1



u1 n    1    1 

 

       
u nn    n    n 
n
pi  0,

n
pi  1
i 1
Linear transformations
that conserve 1-norm of
probability vectors:
Stochastic matrices
 i  C,

2
i
1
i 1
Linear transformations
that conserve 2-norm of
amplitude vectors:
Unitary matrices
Quantum Computing
Where
we are:state
A QC
nowrequires
factored
into
A general
entangled
of has
n qubits
~2n21
amplitudes
with high probability (Martín-López et al. 2012)
to 37,
specify:
 x

Scaling up is hard, because of decoherence! But
 
x
x   0 ,1 
n
unless QM is wrong, there doesn’t seem to be any
Presents an obvious
practical problem
when using
fundamental
obstacle
conventional computers to simulate quantum mechanics
Interesting
Feynman 1981: So then why not turn things around, and
build computers that themselves exploit superposition?
Shor 1994: Such a computer could do more than simulate
QM—e.g., it could factor integers in polynomial time
But 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
Some Examples of My Research on
Computational Complexity and Physics
BosonSampling (with Alex Arkhipov):
A proposal for a rudimentary photonic
quantum computer, which doesn’t
seem useful for anything (e.g. breaking
codes), but does seem hard to
simulate using classical computers
(We showed that a fast, exact classical simulation would collapse the
polynomial hierarchy to the third level)
Experimentally demonstrated (with
3-4 photons…) by groups in Brisbane,
Oxford, Vienna, and Rome!
Computational Complexity of
Decoding Hawking Radiation
Firewall Paradox (2012): Hypothetical experiment
that involves waiting outside a black hole for
~1070 years, collecting all the Hawking photons it
emits, doing a quantum computation on them,
then jumping into the black hole to observe that
your computation “nonlocally destroyed” the
structure of spacetime inside the black hole
Harlow-Hayden (2013): Argument that the
requisite computation would take exponential
time (~210^70 years) even for a QC—by which time
the black hole has already fully evaporated!
Recently, I strengthened Harlow and Hayden’s argument, to show
that performing the computation is generically at least as hard as
inverting a one-way function
Summary
Quantum computing really is one of the most exciting things
in science—just not for the reasons you usually hear
Quantum computers are not known to provide any
practically-important speedups for NP-complete problems
(though they might provide modest ones, and they almost certainly
provide speedups for problems like factoring and quantum simulation)
And building them is hard (though the real shock for physics would
be if they weren’t someday possible)
On the other hand, one thing quantum computing has
already done, is create a bridge between computer science
and physics, carrying nontrivial insights in both directions