  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.
