abstract: A quantum walk on a (quasi) linear graph can play the role of the quantum clock of a quantum computer: while the particle moves along the graph, unitary operations are applied to some computational degree of freedom. In this model, proposed by R.P. Feynman in 1985, the completion of a computational coincides with the traversal of a graph. The presence of imperfections and/or an interaction with an environment is usually believed to detriment the traversal capabilities of the quantum walker. In turn, the computational capabilities of the system are degraded. In this talk we discuss how to recover transmission along a graph affected by random on-site imperfections by means of a suitable interaction with the environment. We then show that the traversal of the graph still corresponds to the application of unitaries to the computational degrees of freedom. However, due to the presence of decoherence, quantum computation can be no longer supported.