Quantum simulations of classical random walks and undirected graph connectivity

Details Quantum simulations of classical random walks and undirected graph connectivity Quantum simulations of classical random walks and undirected graph connectivity

1998-12-11

arxiv.org/abs/cs/9812012v1

Computer Science

Computational Complexity

11 pages, submitted to Complexity'99

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

Quantum simulations of classical random walks and undirected graph connectivity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum simulations of classical random walks and undirected graph connectivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum simulations of classical random walks and undirected graph connectivity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-38456