Algorithms Speedup From Quantum Mechanics
Abstract
This project was concerned primarily with one central theme which is the attempt to use quantum mechanics to design algorithms that perform better than conventional (non-quantum) algorithms for solving certain problems. We looked at a variety of approaches. The first is quantum adiabatic evolution which was invented by the authors along with M. Sipser and S. Gutmann. During the period of this report we studied the robustness of this algorithm, generalized the algorithm beyond its original specification and also showed that it can outperform classical algorithms in certain settings. We also investigated continuous time quantum walks which were introduced as a quantum algorithmic tool by Farhi and Gutmann. Here the high point was the discovery of a quantum walk algorithm that gives provable exponential speedup over the best possible classical algorithm for a certain oracle problem. Goldstone and Childs (a graduate student at MIT at the time) explored the use of quantum walk algorithms for searching a spatial grid. Also Farhi, Goldstone and coworkers showed how to use repeated measurements as an algorithmic tool. In particular we showed how to achieve the Grover square root speedup using measurement algorithms. In the remainder of the report we will elaborate on these findings and make reference to the associated papers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 29, 2005
- Accession Number
- ADA442558
Entities
People
- Edward Farhi
- Jeffrey Goldstone
Organizations
- Massachusetts Institute of Technology