18 citations · 31 across the 4 of their papers we have counts for
Showing 2005 · quant-phShow all
2 papers · 2 filters
quant-ph2005★ 13 cited
Tight adversary bounds for composite functions
Peter Hoyer, Troy Lee, Robert Spalek
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many…
quant-ph2005
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, Mario Szegedy
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 b…