dorsal/arxiv
View SchemaSpectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule
| Authors | Mario Szegedy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0401053 |
| URL | https://arxiv.org/abs/quant-ph/0401053 |
Abstract
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.
{
"annotation_id": "a64a5abb-ce90-4727-bfd3-ab4de85dc04b",
"date_created": "2026-03-02T18:02:03.630000Z",
"date_modified": "2026-03-02T18:02:03.630000Z",
"file_hash": "f227793fe5e11b4df2764796c63d4d7647879b9b6b47493cb189554d8195ce87",
"private": false,
"record": {
"abstract": "We introduce quantized bipartite walks, compute their spectra, generalize the\nalgorithms of Grover \\cite{g} and Ambainis \\cite{amb03} and interpret them as\nquantum walks with memory. We compare the performance of walk based classical\nand quantum algorithms and show that the latter run much quicker in general.\nLet $P$ be a symmetric Markov chain with transition probabilities $P[i,j]$, $(i\n,j\\in [n])$. Some elements of the state space are marked. We are promised that\nthe set of marked elements has size either zero or at least $\\epsilon n$. The\ngoal is to find out with great certainty which of the above two cases holds.\nOur model is a black box that can answer certain yes/no questions and can\ngenerate random elements picked from certain distributions. More specifically,\nby request the black box can give us a uniformly distributed random element for\nthe cost of $\\wp_{0}$. Also, when ``inserting\u0027\u0027 an element $i$ into the black\nbox we can obtain a random element $j$, where $j$ is distributed according to\n$P[i,j]$. The cost of the latter operation is $\\wp_{1}$. Finally, we can use\nthe black box to test if an element $i$ is marked, and this costs us $\\wp_{2}$.\nIf $\\delta$ is the eigenvalue gap of $P$, there is a simple classical algorithm\nwith cost $O(\\wp_{0} + (\\wp_{1}+\\wp_{2})/\\delta\\epsilon)$ that solves the above\npromise problem. (The algorithm is efficient if $\\wp_{0}$ is much larger than\n$\\wp_{1}+\\wp_{2}$.) In contrast,we show that for the ``quantized\u0027\u0027 version of\nthe algorithm it costs only $O(\\wp_{0} +\n(\\wp_{1}+\\wp_{2})/\\sqrt{\\delta\\epsilon})$ to solve the problem. We refer to\nthis as the $\\sqrt{\\delta\\epsilon}$ rule. Among the technical contributions we\ngive a formula for the spectrum of the product of two general reflections.",
"arxiv_id": "quant-ph/0401053",
"authors": [
"Mario Szegedy"
],
"categories": [
"quant-ph"
],
"title": "Spectra of Quantized Walks and a $\\sqrt{\\delta\\epsilon}$ rule",
"url": "https://arxiv.org/abs/quant-ph/0401053"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "51637dbf-9a09-47d7-8326-d4b5c21ff9f1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}