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

2016/10/03 by Chris Cade, Ashley Montanaro, Cade, Chris +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.1610.00581

openalex publication_date 2016/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study space and time efficient quantum algorithms for two graph problems\n-- deciding whether an n-vertex graph is a forest, and whether it is\nbipartite. Via a reduction to the s-t connectivity problem, we describe quantum\nalgorithms for deciding both properties in \O(n^3/2) time and using\nO(\log n) classical and quantum bits of storage in the adjacency matrix\nmodel. We then present quantum algorithms for deciding the two properties in\nthe adjacency array model, which run in time \O(n\√(d_m)) and also\nrequire O(\log n) space, where d_m is the maximum degree of any vertex in\nthe input graph.\n

Related

• Span-program-based quantum algorithms for graph bipartiteness and connectivity
• Time and Query Optimal Quantum Algorithms Based on Decision Trees
• Span-program-based quantum algorithm for tree detection
• Quantum algorithms for learning a hidden graph and beyond
• Quantum Algorithm for Maximum Biclique Problem