  While the quantum query complexity of $k$-distinctness is known to be
$O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$, the best
previous upper bound on the time complexity was
$\widetilde{O}\left(n^{1-1/k}\right)$. We give a new upper bound of
$\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)$ on the time complexity, matching
the query complexity up to polylogarithmic factors. In order to achieve this
upper bound, we give a new technique for designing quantum walk search
algorithms, which is an extension of the electric network framework. We also
show how to solve the welded trees problem in $O(n)$ queries and $O(n^2)$ time
using this new technique, showing that the new quantum walk framework can
achieve exponential speedups.
