Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule
Márió Szegedy · arXiv (Cornell University) · 2004
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.