Quantum simulations of classical random walks and undirected graph connectivity

Simple item page
dc.creatorWatrous, John
dc.date1998-12-11
dc.date.accessioned2026-07-07T03:23:52Z
dc.date.available2026-07-07T03:23:52Z
dc.descriptionIt 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 Turing machines can efficiently simulate a limited class of random processes: random walks on undirected graphs. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and halt absolutely. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace.
dc.description11 pages, submitted to Complexity'99
dc.identifierhttps://arxiv.org/abs/cs/9812012
dc.identifierhttp://arxiv.org/abs/cs/9812012
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/33112
dc.subjectComputational Complexity
dc.subjectQuantum Physics
dc.subjectF.1.3; F.2.2; G.2.2
dc.titleQuantum simulations of classical random walks and undirected graph connectivity
dc.typetext

Files

Collections

arXiv