Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness

Chris Cade*, Ashley Montanaro, Aleksandrs Belovs

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

5 Citations (Scopus)

Abstract

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 s-t connectivity problem, we describe quantum algorithms for deciding both properties in Õ(n3/2) time whilst using O(log n) classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time Õ(n√dm) and also require O(log n) space, where dm is the maximum degree of any vertex in the input graph.

Original languageEnglish
Pages (from-to)18-50
Number of pages33
JournalQuantum Information and Computation
Volume18
Issue number1-2
Publication statusPublished - 1 Feb 2018

Fingerprint

Dive into the research topics of 'Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness'. Together they form a unique fingerprint.

Cite this