The quantum adversary method and classical formula size lower bounds

Sophie Laplante, Troy Lee, Mario Szegedy

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)163-196
Number of pages34
JournalComputational Complexity
Issue number2
StatePublished - Jun 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics


  • Adversary method
  • Communication complexity
  • Formula size
  • Lower bounds
  • Quantum computing


Dive into the research topics of 'The quantum adversary method and classical formula size lower bounds'. Together they form a unique fingerprint.

Cite this