  Quantum walks on graphs are ubiquitous in quantum computing finding a myriad
of applications. Likewise, random walks on graphs are a fundamental building
block for a large number of algorithms with diverse applications. While the
relationship between quantum and random walks has been recently discussed in
specific scenarios, this work establishes a formal equivalence between the
processes on arbitrary finite graphs and general conditions for shift and coin
operators. It requires empowering random walks with time heterogeneity, where
the transition probability of the walker is non-uniform and time dependent. The
equivalence is obtained by equating the probability of measuring the quantum
walk on a given node of the graph and the probability that the random walk is
at that same node, for all nodes and time steps. The result is given by the
construction procedure of a matrix sequence for the random walk that yields the
exact same vertex probability distribution sequence of any given quantum walk,
including the scenario with multiple interfering walkers. Interestingly, these
matrices allows for a different simulation approach for quantum walks where
node samples respect neighbor locality and convergence is guaranteed by the law
of large numbers, enabling efficient (polynomial) sampling of quantum graph
trajectories (paths). Furthermore, the complexity of constructing this sequence
of matrices is discussed in the general case.
