dorsal/arxiv
View SchemaEntropy lower bounds of quantum decision tree complexity
| Authors | Yaoyun Shi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0008095 |
| URL | https://arxiv.org/abs/quant-ph/0008095 |
Abstract
We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard the computation as a communication process in which the oracle and the computer exchange several rounds of messages, each round consisting of O(log(n)) bits. Let E(f) be the Shannon entropy of the random variable f(X), where X is uniformly random in f's domain. Our main result is that it takes \Omega(E(f)) queries to compute any \emph{total} function f. It is interesting to contrast this bound with the \Omega(E(f)/log(n)) bound, which is tight for \emph{partial} functions. Our approach is the polynomial method.
{
"annotation_id": "c840d200-4b2b-400f-9340-96db8f1a1932",
"date_created": "2026-03-02T18:01:38.354000Z",
"date_modified": "2026-03-02T18:01:38.354000Z",
"file_hash": "9b9e5c9be538032fcbf21f9c2f00ecdd9edc7d1d4813afb0ae39076eb8e5ce20",
"private": false,
"record": {
"abstract": "We prove a general lower bound of quantum decision tree complexity in terms\nof some entropy notion. We regard the computation as a communication process in\nwhich the oracle and the computer exchange several rounds of messages, each\nround consisting of O(log(n)) bits. Let E(f) be the Shannon entropy of the\nrandom variable f(X), where X is uniformly random in f\u0027s domain. Our main\nresult is that it takes \\Omega(E(f)) queries to compute any \\emph{total}\nfunction f. It is interesting to contrast this bound with the\n\\Omega(E(f)/log(n)) bound, which is tight for \\emph{partial} functions. Our\napproach is the polynomial method.",
"arxiv_id": "quant-ph/0008095",
"authors": [
"Yaoyun Shi"
],
"categories": [
"quant-ph"
],
"title": "Entropy lower bounds of quantum decision tree complexity",
"url": "https://arxiv.org/abs/quant-ph/0008095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "3987e43c-d168-4377-b58c-b878df805257",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}