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

  1. 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.
  2. 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.

Other video options