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 quantum walks. Decoherence is incorporated in three ways - by coupling to a noisy "projective measurement" system, and by coupling to oscillator and spin baths.