Decohering quantum walks: exploring the space between quantum and classical computing - Viv Kendon

Quantum versions of random walks have markedly different properties from classical random walks, such as faster spreading and mixing. These properties have been exploited to create several quantum algorithms. It has also been observed that making the quantum walk slightly less than perfectly quantum can actually improve the useful behaviour, such as even faster mixing to the uniform distribution. We have calculated the entanglement between the coin and position, and find that the optimal computational behaviour occurs just at the point all the entanglement has been removed by the decoherence. Combined with recent work by others, this provides several interesting perspectives on the phenomenon and its usefulness.