A note on the classical lower bound for a quantum walk algorithm

Details A note on the classical lower bound for a quantum walk algorithm A note on the classical lower bound for a quantum walk algorithm

2003-12-31

arxiv.org/abs/quant-ph/0312230v1

Physics

Quantum Physics

3 pages, no figures

Scientific paper

A recent paper on quantum walks by Childs et al. [STOC'03] provides an example of a black-box problem for which there is a quantum algorithm with exponential speedup over the best classical randomized algorithm for the problem, but where the quantum algorithm does not involve any use of the quantum Fourier transform. They give an exponential lower bound for a classical randomized algorithm solving the black-box graph traversal problem defined in their paper. In this note we give an improved lower bound for this problem via a straightforward and more complete analysis.

Affiliated with

Also associated with

No associations

Rating

A note on the classical lower bound for a quantum walk algorithm 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 A note on the classical lower bound for a quantum walk algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on the classical lower bound for a quantum walk algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-351282