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

**
**