dorsal/arxiv
View SchemaLower bounds of quantum black-box complexity and degree of approximation polynomials by influence of Boolean variables
| Authors | Yaoyun Shi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9904107 |
| URL | https://arxiv.org/abs/quant-ph/9904107 |
| Journal | IPL, 75(1-2):79--83, July 2000. |
Abstract
We prove that, to compute a Boolean function $f$ on $N$ variables with error probability $\epsilon$, any quantum black-box algorithm has to query at least $\frac{1 - 2\sqrt{\epsilon}}{2} \rho_f N = \frac{1 - 2\sqrt{\epsilon}}{2} \bar{S}_f$ times, where $\rho_f$ is the average influence of variables in $f$, and $\bar{S}_f$ is the average sensitivity. It's interesting to contrast this result with the known lower bound of $\Omega (\sqrt{S_f})$, where $S_f$ is the sensitivity of $f$. This lower bound is tight for some functions. We also show for any polynomial $\tilde{f}$ that approximates $f$ with error probability $\epsilon$, $deg(\tilde{f}) \ge 1/4 (1 - \frac{3 \epsilon}{1 + \epsilon})^2 \rho_f N$. This bound can be better than previous known lower bound of $\Omega(\sqrt{BS_f})$ for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping $\{0, 1\}^N$ to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step $t$ can be written as $\sum_{s\in \{0, 1\}^N, |s| \le t} \hat{\phi}_s (-1)^ {s \cdot x}$, which is handy for lower bound analysis.
{
"annotation_id": "b2a9d293-471d-4239-b47b-bc77ef75251c",
"date_created": "2026-03-02T18:02:48.531000Z",
"date_modified": "2026-03-02T18:02:48.531000Z",
"file_hash": "582cff55e946dbd47f52668c6b6b9541e6e26d99634d8bd603ff23c9c3640c8c",
"private": false,
"record": {
"abstract": "We prove that, to compute a Boolean function $f$ on $N$ variables with error\nprobability $\\epsilon$, any quantum black-box algorithm has to query at least\n$\\frac{1 - 2\\sqrt{\\epsilon}}{2} \\rho_f N = \\frac{1 - 2\\sqrt{\\epsilon}}{2}\n\\bar{S}_f$ times, where $\\rho_f$ is the average influence of variables in $f$,\nand $\\bar{S}_f$ is the average sensitivity. It\u0027s interesting to contrast this\nresult with the known lower bound of $\\Omega (\\sqrt{S_f})$, where $S_f$ is the\nsensitivity of $f$. This lower bound is tight for some functions. We also show\nfor any polynomial $\\tilde{f}$ that approximates $f$ with error probability\n$\\epsilon$, $deg(\\tilde{f}) \\ge 1/4 (1 - \\frac{3 \\epsilon}{1 + \\epsilon})^2\n\\rho_f N$. This bound can be better than previous known lower bound of\n$\\Omega(\\sqrt{BS_f})$ for some functions. Our technique may be of intest\nitself: we apply Fourier analysis to functions mapping $\\{0, 1\\}^N$ to unit\nvectors in a Hilbert space. From this viewpoint, the state of the quantum\ncomputer at step $t$ can be written as $\\sum_{s\\in \\{0, 1\\}^N, |s| \\le t}\n\\hat{\\phi}_s (-1)^ {s \\cdot x}$, which is handy for lower bound analysis.",
"arxiv_id": "quant-ph/9904107",
"authors": [
"Yaoyun Shi"
],
"categories": [
"quant-ph"
],
"journal_ref": "IPL, 75(1-2):79--83, July 2000.",
"title": "Lower bounds of quantum black-box complexity and degree of approximation polynomials by influence of Boolean variables",
"url": "https://arxiv.org/abs/quant-ph/9904107"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0925f816-64c3-45a9-b12f-11cca10e7ae7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}