dorsal/arxiv
View SchemaAverage case quantum lower bounds for computing the boolean mean
| Authors | A. Papageorgiou |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0311007 |
| URL | https://arxiv.org/abs/quant-ph/0311007 |
Abstract
We study the average case approximation of the Boolean mean by quantum algorithms. We prove general query lower bounds for classes of probability measures on the set of inputs. We pay special attention to two probabilities, where we show specific query and error lower bounds and the algorithms that achieve them. We also study the worst expected error and the average expected error of quantum algorithms and show the respective query lower bounds. Our results extend the optimality of the algorithm of Brassard et al.
{
"annotation_id": "1ddf5151-37af-470a-9261-aa79526ded0b",
"date_created": "2026-03-02T18:02:03.190000Z",
"date_modified": "2026-03-02T18:02:03.190000Z",
"file_hash": "fb795b3ce77d7d467787ce551f31ecb84901531fe45add3fc360608365638b50",
"private": false,
"record": {
"abstract": "We study the average case approximation of the Boolean mean by quantum\nalgorithms. We prove general query lower bounds for classes of probability\nmeasures on the set of inputs. We pay special attention to two probabilities,\nwhere we show specific query and error lower bounds and the algorithms that\nachieve them. We also study the worst expected error and the average expected\nerror of quantum algorithms and show the respective query lower bounds. Our\nresults extend the optimality of the algorithm of Brassard et al.",
"arxiv_id": "quant-ph/0311007",
"authors": [
"A. Papageorgiou"
],
"categories": [
"quant-ph"
],
"title": "Average case quantum lower bounds for computing the boolean mean",
"url": "https://arxiv.org/abs/quant-ph/0311007"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "27236f4a-67d2-4bf1-8061-849c3a5f046e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}