dorsal/arxiv
View SchemaThe quantum adversary method and classical formula size lower bounds
| Authors | Sophie Laplante, Troy Lee, Mario Szegedy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0501057 |
| URL | https://arxiv.org/abs/quant-ph/0501057 |
Abstract
We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method [Amb02, Amb03, BSS03, Zha04, LM04], culminating in [SS04] with the realization that these many different formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to classical complexity theory. As a surprising application we show that sumPI^2(f) is a lower bound on the formula size, and even, up to a constant multiplicative factor, the probabilistic formula size of f. We show that several formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khr71, Kou93], including a key lemma of [Has98], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI^2(f) remains a lower bound on formula size. While sumPI(f) is always a lower bound on the quantum query complexity of f, this is not the case in general for maxPI(f). A strong advantage of sumPI(f) is that it has both primal and dual characterizations, and thus it is relatively easy to give both upper and lower bounds on the sumPI complexity of functions. To demonstrate this, we look at a few concrete examples, for three functions: recursive majority of three, a function defined by Ambainis, and the collision problem.
{
"annotation_id": "df6a2b6b-decd-41cb-a180-89aa060e5517",
"date_created": "2026-03-02T18:02:13.515000Z",
"date_modified": "2026-03-02T18:02:13.515000Z",
"file_hash": "7c1aa41fff42a2c293829af9a2cd070ce9df6d980d8f32c4c5f4b6a9d7afa1b5",
"private": false,
"record": {
"abstract": "We introduce two new complexity measures for Boolean functions, or more\ngenerally for functions of the form f:S-\u003eT. We call these measures sumPI and\nmaxPI. The quantity sumPI has been emerging through a line of research on\nquantum query complexity lower bounds via the so-called quantum adversary\nmethod [Amb02, Amb03, BSS03, Zha04, LM04], culminating in [SS04] with the\nrealization that these many different formulations are in fact equivalent.\nGiven that sumPI turns out to be such a robust invariant of a function, we\nbegin to investigate this quantity in its own right and see that it also has\napplications to classical complexity theory.\n As a surprising application we show that sumPI^2(f) is a lower bound on the\nformula size, and even, up to a constant multiplicative factor, the\nprobabilistic formula size of f. We show that several formula size lower bounds\nin the literature, specifically Khrapchenko and its extensions [Khr71, Kou93],\nincluding a key lemma of [Has98], are in fact special cases of our method.\n The second quantity we introduce, maxPI(f), is always at least as large as\nsumPI(f), and is derived from sumPI in such a way that maxPI^2(f) remains a\nlower bound on formula size. While sumPI(f) is always a lower bound on the\nquantum query complexity of f, this is not the case in general for maxPI(f). A\nstrong advantage of sumPI(f) is that it has both primal and dual\ncharacterizations, and thus it is relatively easy to give both upper and lower\nbounds on the sumPI complexity of functions. To demonstrate this, we look at a\nfew concrete examples, for three functions: recursive majority of three, a\nfunction defined by Ambainis, and the collision problem.",
"arxiv_id": "quant-ph/0501057",
"authors": [
"Sophie Laplante",
"Troy Lee",
"Mario Szegedy"
],
"categories": [
"quant-ph"
],
"title": "The quantum adversary method and classical formula size lower bounds",
"url": "https://arxiv.org/abs/quant-ph/0501057"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "706b45f6-2b90-45b8-ab89-98fc8bccbb37",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}