  A number of recent studies have investigated the introduction of decoherence
in quantum walks and the resulting transition to classical random walks.
Interestingly, it has been shown that algorithmic properties of quantum walks
with decoherence such as the spreading rate are sometimes better than their
purely quantum counterparts. Not only quantum walks with decoherence provide a
generalization of quantum walks that naturally encompasses both the quantum and
classical case, but they also give rise to new and different probability
distribution. The application of quantum walks with decoherence to large graphs
is limited by the necessity of evolving a state vector whose size is quadratic
in the number of nodes of the graph, as opposed to the linear state vector of
the purely quantum (or classical) case. In this technical report, we show how
to use perturbation theory to reduce the computational complexity of evolving a
continuous-time quantum walk subject to decoherence. More specifically, given a
graph over n nodes, we show how to approximate the eigendecomposition of the
n^2 x n^2 Lindblad super-operator from the eigendecomposition of the n x n
graph Hamiltonian.
