  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\sqrt{n})$ quantum queries; an
algorithm for testing if the graph is connected that uses $O(n\sqrt{n})$
quantum queries.

Quantum Physics;Computational Complexity;Data Structures and Algorithms