  We present a quantum algorithm for sampling an edge on a path between two
nodes s and t in an undirected graph given as an adjacency matrix, and show
that this can be done in query complexity that is asymptotically the same, up
to log factors, as the query complexity of detecting a path between s and t. We
use this path sampling algorithm as a subroutine for st-path finding and
st-cut-set finding algorithms in some specific cases. Our main technical
contribution is an algorithm for generating a quantum state that is
proportional to the positive witness vector of a span program.

Quantum Physics;Data Structures and Algorithms