  The polynomial method and the adversary method are the two main techniques to
prove lower bounds on quantum query complexity, and they have so far been
considered as unrelated approaches. Here, we show an explicit reduction from
the polynomial method to the multiplicative adversary method. The proof goes by
extending the polynomial method from Boolean functions to quantum state
generation problems. In the process, the bound is even strengthened. We then
show that this extended polynomial method is a special case of the
multiplicative adversary method with an adversary matrix that is independent of
the function. This new result therefore provides insight on the reason why in
some cases the adversary method is stronger than the polynomial method. It also
reveals a clear picture of the relation between the different lower bound
techniques, as it implies that all known techniques reduce to the
multiplicative adversary method.
