**
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.)