Quantum simulations of classical random walks and undirected graph connectivity

John Watrous

It is not currently known if quantum Turing machines can efficiently simulate probabilistic computations in the space-bounded case. In this paper we show that space-bounded quantum…