Transcript The Future of Computer Science

Quantum Computers and Beyond
Scott Aaronson
Associate Professor, EECS
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?
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 we’ve learned from
quantum computers so far:
15 = 3 × 5
(with high probability)
Linear-Optical Quantum Computing
www.scottaaronson.com/papers/optics.pdf
My student Alex Arkhipov and I recently
proposed an experiment, which involves
generating n identical photons, passing
them through a network of beamsplitters,
then measuring where they end up
Our proposal almost certainly wouldn’t
yield a universal quantum computer—and
indeed, it seems a lot easier to implement
Nevertheless, we give complexity-theoretic evidence that our
experiment would solve some sampling problem that’s
classically intractable
Groups in Brisbane, Australia and Imperial College London are
currently working to implement our experiment
Summary
1. From a theoretical standpoint, modern
computers are “all the same slop”: polynomialtime Turing machines
2. We can imagine computers that vastly exceed
those (by using closed timelike curves, etc.)
3. But going even a tiny bit beyond polynomial-time
Turing machines (say, with linear-optical quantum
computers) is a great experimental challenge