dorsal/arxiv
View SchemaGrover's Quantum Search Algorithm and Diophantine Approximation
| Authors | Shahar Dolev, Itamar Pitowsky, Boaz Tamir |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0507234 |
| URL | https://arxiv.org/abs/quant-ph/0507234 |
| DOI | 10.1103/PhysRevA.73.022308 |
| Journal | Physical Review A 73 022308 (2006) |
Abstract
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size N by using only O(N^{1/2}) queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either M or K, M<K, our task is to determine which is the case. We show how to solve this problem with a high probability of success using only iterations of Grover's basic step (and no other algorithm). Let m be the required number of iterations; we prove that under certain restrictions on the sizes of M and K the estimation m < (2N^{1/2})/(K^{1/2}-M^{1/2}) obtains. This bound sharpens previous results and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.
{
"annotation_id": "eb64c3d8-024d-4af3-b6b4-9e9e0fd7651b",
"date_created": "2026-03-02T18:02:20.539000Z",
"date_modified": "2026-03-02T18:02:20.539000Z",
"file_hash": "05a49cce9324bccefc34ccdfd38b6f420d4eba15ef4ca50bc4e4dd9cac0a14cb",
"private": false,
"record": {
"abstract": "In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a\nquantum computer can find a single marked object in a database of size N by\nusing only O(N^{1/2}) queries of the oracle that identifies the object. His\nresult was generalized to the case of finding one object in a subset of marked\nelements. We consider the following computational problem: A subset of marked\nelements is given whose number of elements is either M or K, M\u003cK, our task is\nto determine which is the case. We show how to solve this problem with a high\nprobability of success using only iterations of Grover\u0027s basic step (and no\nother algorithm). Let m be the required number of iterations; we prove that\nunder certain restrictions on the sizes of M and K the estimation m \u003c\n(2N^{1/2})/(K^{1/2}-M^{1/2}) obtains. This bound sharpens previous results and\nis known to be optimal up to a constant factor. Our method involves\nsimultaneous Diophantine approximations, so that Grover\u0027s algorithm is\nconceptualized as an orbit of an ergodic automorphism of the torus. We comment\non situations where the algorithm may be slow, and note the similarity between\nthese cases and the problem of small divisors in classical mechanics.",
"arxiv_id": "quant-ph/0507234",
"authors": [
"Shahar Dolev",
"Itamar Pitowsky",
"Boaz Tamir"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1103/PhysRevA.73.022308",
"journal_ref": "Physical Review A 73 022308 (2006)",
"title": "Grover\u0027s Quantum Search Algorithm and Diophantine Approximation",
"url": "https://arxiv.org/abs/quant-ph/0507234"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "52d0a1a2-d7bf-4b85-a55f-c80468d2103a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}