TY - JOUR

T1 - The quantum adversary method and classical formula size lower bounds

AU - Laplante, Sophie

AU - Lee, Troy

AU - Szegedy, Mario

N1 - Funding Information:
We would like to thank Frédéric Magniez, Robert Sˇpalek, and Ronald de Wolf for helpful discussions. We also wish to thank Ryan O’Donnell for suggesting to look at the recursive majority of three function, and Xiaomin Chen for help in programming. Finally, we thank the anonymous referees for many exposition improving suggestions. This work was supported in part by EU RESQ IST-2001-37559, EU QAP IST-2005-015848, ANR AlgoQP, and ACI SI Réseaux Quantiques.

PY - 2006/6

Y1 - 2006/6

N2 - We introduce two new complexity measures for Boolean functions, which we name 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 (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in Špalek & Szegedy (2005) 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 (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Håstad (1998), 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. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.

AB - We introduce two new complexity measures for Boolean functions, which we name 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 (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in Špalek & Szegedy (2005) 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 (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Håstad (1998), 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. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.

KW - Adversary method

KW - Communication complexity

KW - Formula size

KW - Lower bounds

KW - Quantum computing

UR - http://www.scopus.com/inward/record.url?scp=33745312939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745312939&partnerID=8YFLogxK

U2 - 10.1007/s00037-006-0212-7

DO - 10.1007/s00037-006-0212-7

M3 - Article

AN - SCOPUS:33745312939

SN - 1016-3328

VL - 15

SP - 163

EP - 196

JO - Computational Complexity

JF - Computational Complexity

IS - 2

ER -