dorsal/arxiv
View SchemaOn the Quantum Black-Box Complexity of Majority
| Authors | Thomas Hayes, Samuel Kutin, Dieter van Melkebeek |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0109101 |
| URL | https://arxiv.org/abs/quant-ph/0109101 |
Abstract
We describe a quantum black-box network computing the majority of N bits with zero-sided error eps using only 2N/3 + O(sqrt{N (log log N + log 1/eps)}) queries: the algorithm returns the correct answer with probability at least 1 - eps, and "I don't know" otherwise. Our algorithm is given as a randomized "XOR decision tree" for which the number of queries on any input is strongly concentrated around a value of at most 2N/3. We provide a nearly matching lower bound of 2N/3 - O(sqrt(N)) on the expected number of queries on a worst-case input in the randomized XOR decision tree model with zero-sided error o(1). Any classical randomized decision tree computing the majority on N bits with zero-sided error 1/2 has cost N.
{
"annotation_id": "2ce085ba-588b-4488-b6bf-027e7cc2026a",
"date_created": "2026-03-02T18:01:45.790000Z",
"date_modified": "2026-03-02T18:01:45.790000Z",
"file_hash": "83429f91ac22345420086deb640565d62b44519d8cbc0500e0851629f4a2209d",
"private": false,
"record": {
"abstract": "We describe a quantum black-box network computing the majority of N bits with\nzero-sided error eps using only 2N/3 + O(sqrt{N (log log N + log 1/eps)})\nqueries: the algorithm returns the correct answer with probability at least 1 -\neps, and \"I don\u0027t know\" otherwise. Our algorithm is given as a randomized \"XOR\ndecision tree\" for which the number of queries on any input is strongly\nconcentrated around a value of at most 2N/3. We provide a nearly matching lower\nbound of 2N/3 - O(sqrt(N)) on the expected number of queries on a worst-case\ninput in the randomized XOR decision tree model with zero-sided error o(1). Any\nclassical randomized decision tree computing the majority on N bits with\nzero-sided error 1/2 has cost N.",
"arxiv_id": "quant-ph/0109101",
"authors": [
"Thomas Hayes",
"Samuel Kutin",
"Dieter van Melkebeek"
],
"categories": [
"quant-ph"
],
"title": "On the Quantum Black-Box Complexity of Majority",
"url": "https://arxiv.org/abs/quant-ph/0109101"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a19b18fc-2c90-4a02-864a-0d6564202fae",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}