Spectra of Quantized Walks and a $\sqrt{δε}$ rule

Details Spectra of Quantized Walks and a $\sqrt{δε}$ rule Spectra of Quantized Walks and a $\sqrt{δε}$ rule

2004-01-10

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

Physics

Quantum Physics

27pages

Scientific paper

We introduce quantized bipartite walks, compute their spectra, generalize the algorithms of Grover \cite{g} and Ambainis \cite{amb03} and interpret them as quantum walks with memory. We compare the performance of walk based classical and quantum algorithms and show that the latter run much quicker in general. Let $P$ be a symmetric Markov chain with transition probabilities $P[i,j]$, $(i ,j\in [n])$. Some elements of the state space are marked. We are promised that the set of marked elements has size either zero or at least $\epsilon n$. The goal is to find out with great certainty which of the above two cases holds. Our model is a black box that can answer certain yes/no questions and can generate random elements picked from certain distributions. More specifically, by request the black box can give us a uniformly distributed random element for the cost of $\wp_{0}$. Also, when ``inserting'' an element $i$ into the black box we can obtain a random element $j$, where $j$ is distributed according to $P[i,j]$. The cost of the latter operation is $\wp_{1}$. Finally, we can use the black box to test if an element $i$ is marked, and this costs us $\wp_{2}$. If $\delta$ is the eigenvalue gap of $P$, there is a simple classical algorithm with cost $O(\wp_{0} + (\wp_{1}+\wp_{2})/\delta\epsilon)$ that solves the above promise problem. (The algorithm is efficient if $\wp_{0}$ is much larger than $\wp_{1}+\wp_{2}$.) In contrast,we show that for the ``quantized'' version of the algorithm it costs only $O(\wp_{0} + (\wp_{1}+\wp_{2})/\sqrt{\delta\epsilon})$ to solve the problem. We refer to this as the $\sqrt{\delta\epsilon}$ rule. Among the technical contributions we give a formula for the spectrum of the product of two general reflections.

Affiliated with

Also associated with

No associations

Rating

Spectra of Quantized Walks and a $\sqrt{δε}$ rule 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 Spectra of Quantized Walks and a $\sqrt{δε}$ rule, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectra of Quantized Walks and a $\sqrt{δε}$ rule will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-688804