dorsal/arxiv
View SchemaExact quantum query complexity for total Boolean functions
| Authors | Gatis Midrijanis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0403168 |
| URL | https://arxiv.org/abs/quant-ph/0403168 |
Abstract
We will show that if there exists a quantum query algorithm that exactly computes some total Boolean function f by making T queries, then there is a classical deterministic algorithm A that exactly computes f making O(T^3) queries. The best know bound previously was O(T^4) due to Beals et al.
{
"annotation_id": "c4cc4fb1-3012-424c-8f43-6d8974aeb70b",
"date_created": "2026-03-02T18:02:07Z",
"date_modified": "2026-03-02T18:02:07Z",
"file_hash": "8f1fa1fe3c70aa94f5f69edbd25c59a1cfee9a25f023dd6572d9e0365fe95dc1",
"private": false,
"record": {
"abstract": "We will show that if there exists a quantum query algorithm that exactly\ncomputes some total Boolean function f by making T queries, then there is a\nclassical deterministic algorithm A that exactly computes f making O(T^3)\nqueries. The best know bound previously was O(T^4) due to Beals et al.",
"arxiv_id": "quant-ph/0403168",
"authors": [
"Gatis Midrijanis"
],
"categories": [
"quant-ph"
],
"title": "Exact quantum query complexity for total Boolean functions",
"url": "https://arxiv.org/abs/quant-ph/0403168"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "883a0b57-22f1-4bf3-8849-1d0b8989087b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}