Feb 25, 2004
Quantum Algorithms
Dr. Jeffrey Goldstone, MIT/Caltech
After a brief review of some ideas of classical and quantum computational
complexity theory and description of some examples of computational problems
that could be solved much faster on a quantum computer (and of one which
could not) I will describe two methods developed by the MIT Center for
Theoretical Physics group.
- Quantum walks on a graph. We have an
example of a problem and a quantum algorithm that works in time polynomial
in the size of the problem input, while we can prove that any classical
algorithm must take exponential time.
- Quantum adiabatic evolution used
to find assignments of many bit values to satisfy multiple constraints.
We have (inconclusive) results from simulating our hypothetical quantum
computer on a classical computer, and some theoretical insights into
special cases.
Begin WebCam and audio for the whole talk: high bandwidth or medium bandwidth.
Or, begin audio only for the whole talk:
high bandwidth or low bandwidth.
(Or, right-click to download the whole audio file.)
To begin viewing slides, click on the first slide below.
(Or, view as pdf.)
Author entry (protected)