dorsal/arxiv
View SchemaSearch via Quantum Walk
| Authors | Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0608026 |
| URL | https://arxiv.org/abs/quant-ph/0608026 |
| DOI | 10.1137/090745854 |
| Journal | SIAM Journal on Computing, 40(1):142-164, 2011 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
We propose a new method for designing quantum search algorithms for finding a "marked" element in the state space of a classical Markov chain. The algorithm is based on a quantum walk \'a la Szegedy (2004) that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis (2004) and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.
{
"annotation_id": "9202a015-3e19-4c6f-bd5c-3cd83003c5fc",
"date_created": "2026-03-02T18:02:30.922000Z",
"date_modified": "2026-03-02T18:02:30.922000Z",
"file_hash": "0992dae88925b0f96e9ee5325edbfdc98e113328f023c90ab72b9056baf9cd05",
"private": false,
"record": {
"abstract": "We propose a new method for designing quantum search algorithms for finding a\n\"marked\" element in the state space of a classical Markov chain. The algorithm\nis based on a quantum walk \\\u0027a la Szegedy (2004) that is defined in terms of\nthe Markov chain. The main new idea is to apply quantum phase estimation to the\nquantum walk in order to implement an approximate reflection operator. This\noperator is then used in an amplitude amplification scheme. As a result we\nconsiderably expand the scope of the previous approaches of Ambainis (2004) and\nSzegedy (2004). Our algorithm combines the benefits of these approaches in\nterms of being able to find marked elements, incurring the smaller cost of the\ntwo, and being applicable to a larger class of Markov chains. In addition, it\nis conceptually simple and avoids some technical difficulties in the previous\nanalyses of several algorithms based on quantum walk.",
"arxiv_id": "quant-ph/0608026",
"authors": [
"Fr\u00e9d\u00e9ric Magniez",
"Ashwin Nayak",
"J\u00e9r\u00e9mie Roland",
"Miklos Santha"
],
"categories": [
"quant-ph",
"cs.CC",
"cs.DS"
],
"doi": "10.1137/090745854",
"journal_ref": "SIAM Journal on Computing, 40(1):142-164, 2011",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Search via Quantum Walk",
"url": "https://arxiv.org/abs/quant-ph/0608026"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "72033c7b-a745-4ceb-8db1-61cf649e1711",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}