dorsal/arxiv
View SchemaQuantum Counting
| Authors | Gilles Brassard, Peter Hoyer, Alain Tapp |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9805082 |
| URL | https://arxiv.org/abs/quant-ph/9805082 |
| DOI | 10.1007/BFb0055105 |
| Journal | 25th Intl. Colloquium on Automata, Languages, and Programming (ICALP), LNCS 1443, pp. 820-831, 1998 |
Abstract
We study some extensions of Grover's quantum searching algorithm. First, we generalize the Grover iteration in the light of a concept called amplitude amplification. Then, we show that the quadratic speedup obtained by the quantum searching algorithm over classical brute force can still be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform approximate counting, which can be seen as an amplitude estimation process.
{
"annotation_id": "188f37bf-3aa5-482c-b78f-baf7cbce1b54",
"date_created": "2026-03-02T18:02:43.865000Z",
"date_modified": "2026-03-02T18:02:43.865000Z",
"file_hash": "a71ec1a2c7477f34347c92b1fcff814a376ebc908a1c35dbb0632ee56264cc1b",
"private": false,
"record": {
"abstract": "We study some extensions of Grover\u0027s quantum searching algorithm. First, we\ngeneralize the Grover iteration in the light of a concept called amplitude\namplification. Then, we show that the quadratic speedup obtained by the quantum\nsearching algorithm over classical brute force can still be obtained for a\nlarge family of search problems for which good classical heuristics exist.\nFinally, as our main result, we combine ideas from Grover\u0027s and Shor\u0027s quantum\nalgorithms to perform approximate counting, which can be seen as an amplitude\nestimation process.",
"arxiv_id": "quant-ph/9805082",
"authors": [
"Gilles Brassard",
"Peter Hoyer",
"Alain Tapp"
],
"categories": [
"quant-ph"
],
"doi": "10.1007/BFb0055105",
"journal_ref": "25th Intl. Colloquium on Automata, Languages, and Programming\n (ICALP), LNCS 1443, pp. 820-831, 1998",
"title": "Quantum Counting",
"url": "https://arxiv.org/abs/quant-ph/9805082"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d7cb2751-0658-44cb-955f-529142f04bc2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}