Decoherence in quantum walks and quantum computers

Decoherence is the major stumbling block in the realization of a large-scale quantum computer. Ingenious methods have been devised to overcome decoherence, but their success has been proven only for over-simplified models of system-environment interaction. Whether such methods will be reliable in the face of more realistic models is a fundamental open question. In this partly pedagogical article, we study two toy models of quantum information processing, using the language of \emph{quantum walks}. Decoherence is incorporated in 3 ways - by coupling to a noisy `projective measurement' system, and by coupling to oscillator and spin baths.