Quantum simulations of classical random walks and undirected graph connectivity

摘要: There are a number of questions in quantum complexity that have been resolved the time-bounded setting, but remain open space-bounded setting. For example, it is not currently known if probabilistic computations can be simulated by machines without allowing measurements during computation, while an analogous statement holds case. A more general question asks computation allow for space-efficient solutions to certain problems. In this paper we show Turing efficiently simulate limited class random processes-random walks on undirected graphs-without relying computation. By means such simulations, demonstrated graph connectivity problem regular graphs solved one-sided error run logspace and require single measurement at end their computations. It follows symmetric contained analogue randomized logspace, i.e., SL/spl sube/QR/sub H/L.