dorsal/arxiv
View SchemaA note on quantum black-box complexity of almost all Boolean functions
| Authors | Andris Ambainis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9811080 |
| URL | https://arxiv.org/abs/quant-ph/9811080 |
| Journal | Inform.Proc.Lett. 71 (1999) 5-7 |
Abstract
We show that, for almost all N-variable Boolean functions f, at least N/4-O(\sqrt{N} log N) queries are required to compute f in quantum black-box model with bounded error.
{
"annotation_id": "3522e831-9de8-41fc-8a28-b0474b373fc5",
"date_created": "2026-03-02T18:02:44.474000Z",
"date_modified": "2026-03-02T18:02:44.474000Z",
"file_hash": "a88189cebcfcbd2a0a81d24aee8c7140738ffee420bf00220884c6403dd32693",
"private": false,
"record": {
"abstract": "We show that, for almost all N-variable Boolean functions f, at least\nN/4-O(\\sqrt{N} log N) queries are required to compute f in quantum black-box\nmodel with bounded error.",
"arxiv_id": "quant-ph/9811080",
"authors": [
"Andris Ambainis"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Inform.Proc.Lett. 71 (1999) 5-7",
"title": "A note on quantum black-box complexity of almost all Boolean functions",
"url": "https://arxiv.org/abs/quant-ph/9811080"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1f5a842c-9d2a-4c7b-aa3e-2a802c77462d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}