Publications and Research
Document Type
Other
Publication Date
2006
Abstract
Quantum computing—so weird, so wonderful—inspires much speculation about the line between the possible and the impossible. (Of course, there is still unclarity about how “impossible” intractable problems are and about how “possible” quantum computers are.) This thesis takes a slightly different tack: instead of focusing on how to make the impossible possible, it focuses on how to make the possible easier.
More specifically, this paper discusses quantum algorithms for finding cycles in graphs, a problem for which polynomial-time classical algorithms already exist. It explains and compares the classical and quantum algorithms, and it introduces a few new algorithms and observations.
However, the primary contribution of this paper is its compilation of—and coherent progression through—old and new research. Interest in quantum cycle algorithms mushroomed in 2003, and many of the new algorithms are included here. While not a comprehensive catalog, this paper is a carefully chosen selection of the most important, elegant, and efficient cycle algorithms.
Thesis Summary Slideshow
Comments
This document is the author's master's thesis from the Universiteit van Amsterdam, where she studied logic at the Institute for Logic, Language, and Computation.