Directed st-connectivity with few paths is in quantum logspace

We present a mathsf{BQSPACE}\(O(log n\))-procedure to count st-paths on directed graphs for which we are promised that there are at most polynomially many paths starting in s and polynomially many paths ending in t. For comparison, the best known classical upper bound in this case just to decide st-connectivity is mathsf{DSPACE}\(O(log² n/ log log n\)). The result establishes a new relationship between mathsf{BQL} and unambiguity and fewness subclasses of mathsf{NL}. Further, we also show how to recognize directed graphs with at most polynomially many paths between any two nodes in mathsf{BQSPACE}\(O(log n\)). This yields the first natural candidate for a language separating mathsf{BQL} from mathsf{L} and mathsf{BPL}. Until now, all candidates potentially separating these classes were inherently promise problems.