  A recent paper on quantum walks by Childs et al. [STOC'03] provides an
example of a black-box problem for which there is a quantum algorithm with
exponential speedup over the best classical randomized algorithm for the
problem, but where the quantum algorithm does not involve any use of the
quantum Fourier transform. They give an exponential lower bound for a classical
randomized algorithm solving the black-box graph traversal problem defined in
their paper. In this note we give an improved lower bound for this problem via
a straightforward and more complete analysis.
