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.

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.

quantum_and_classical_cycles_slides.pdf (145 kB)
Thesis Summary Slideshow

 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.