dorsal/arxiv
View SchemaNoise in Grover's Quantum Search Algorithm
| Authors | B. Pablo-Norman, M. Ruiz-Altaba |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9903070 |
| URL | https://arxiv.org/abs/quant-ph/9903070 |
| DOI | 10.1103/PhysRevA.61.012301 |
| Journal | AIP Conf.Proc. 490 (1999) 405-408 |
Abstract
Grover's quantum algorithm improves any classical search algorithm. We show how random Gaussian noise at each step of the algorithm can be modelled easily because of the exact recursion formulas available for computing the quantum amplitude in Grover's algorithm. We study the algorithm's intrinsic robustness when no quantum correction codes are used, and evaluate how much noise the algorithm can bear with, in terms of the size of the phone book and a desired probability of finding the correct result. The algorithm loses efficiency when noise is added, but does not slow down. We also study the maximal noise under which the iterated quantum algorithm is just as slow as the classical algorithm. In all cases, the width of the allowed noise scales with the size of the phone book as N^-2/3.
{
"annotation_id": "094a5b18-1ffc-4ac7-93c5-cf203cf8e08e",
"date_created": "2026-03-02T18:02:44.539000Z",
"date_modified": "2026-03-02T18:02:44.539000Z",
"file_hash": "97fe8acb0c13a84293f4d775a7ce4432c92b3d57ef7b3e9f8b499b639a3e29fa",
"private": false,
"record": {
"abstract": "Grover\u0027s quantum algorithm improves any classical search algorithm. We show\nhow random Gaussian noise at each step of the algorithm can be modelled easily\nbecause of the exact recursion formulas available for computing the quantum\namplitude in Grover\u0027s algorithm. We study the algorithm\u0027s intrinsic robustness\nwhen no quantum correction codes are used, and evaluate how much noise the\nalgorithm can bear with, in terms of the size of the phone book and a desired\nprobability of finding the correct result. The algorithm loses efficiency when\nnoise is added, but does not slow down. We also study the maximal noise under\nwhich the iterated quantum algorithm is just as slow as the classical\nalgorithm. In all cases, the width of the allowed noise scales with the size of\nthe phone book as N^-2/3.",
"arxiv_id": "quant-ph/9903070",
"authors": [
"B. Pablo-Norman",
"M. Ruiz-Altaba"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.61.012301",
"journal_ref": "AIP Conf.Proc. 490 (1999) 405-408",
"title": "Noise in Grover\u0027s Quantum Search Algorithm",
"url": "https://arxiv.org/abs/quant-ph/9903070"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "df694715-d12c-4603-b2b9-4e0110c67d28",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}