Classical and Quantum Algorithms for Finding Cycles
Jill Cirasella

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.