Physical Sciences and Mathematics Commons^™

Classical And Quantum Algorithms For Finding Cycles, Jill Cirasella

Publications and Research

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