  We present an efficient general method for realizing a quantum walk operator
corresponding to an arbitrary sparse classical random walk. Our approach is
based on Grover and Rudolph's method for preparing coherent versions of
efficiently integrable probability distributions. This method is intended for
use in quantum walk algorithms with polynomial speedups, whose complexity is
usually measured in terms of how many times we have to apply a step of a
quantum walk, compared to the number of necessary classical Markov chain steps.
We consider a finer notion of complexity including the number of elementary
gates it takes to implement each step of the quantum walk with some desired
accuracy. The difference in complexity for various implementation approaches is
that our method scales linearly in the sparsity parameter and
poly-logarithmically with the inverse of the desired precision. The best
previously known general methods either scale quadratically in the sparsity
parameter, or polynomially in the inverse precision. Our approach is especially
relevant for implementing quantum walks corresponding to classical random walks
like those used in the classical algorithms for approximating permanents and
sampling from binary contingency tables. In those algorithms, the sparsity
parameter grows with the problem size, while maintaining high precision is
required.
