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.