Here, we provide an alternative proof for a quantum lower bound that is based on the so-called polynomial method [1]}. The result will be slightly less general – it requires \(n \le m\)  as an extra assumption. But the argument is instructive, as it has a very different flavor.
Because the two proofs have very different flavor, we provide both of them. But we emphasize once more that the mutual information proof works in a somewhat more general setting.
