Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness

Chris Cade, Ashley Montanaro, Aleksandrs Belovs

We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the…