Span-program-based quantum algorithms for graph bipartiteness and connectivity

Original · EN

Span program is a linear-algebraic model of computation which can be used to design quantum algorithms. For any Boolean function there exists a span program that leads to a quantum algorithm with optimal quantum query complexity. In general, finding such span programs is not an easy task. In this work, given a query access to the adjacency matrix of a simple graph G with n vertices, we provide two new span-program-based quantum algorithms: an algorithm for testing if the graph is bipartite that uses O(n√n) quantum queries; an algorithm for testing if the graph is connected that uses O(n√n) quantum queries.