For monotone $f$:
- $\mathrm{s}(f) = \mathrm{bs}(f) = \mathrm{C}(f)$ [Nisan91].
- Hence $\mathrm{D}(f) \le \mathrm{C}^0(f)\mathrm{C}^1(f) \le \mathrm{s}(f)^2$ [BdW02, Cor. 5].
- $\mathrm{s}(f) \le \deg(f)$ [BdW02, Prop. 4].
- Therefore $\mathrm{D}(f)=O(\mathrm{R}(f)^2)$, $\mathrm{D}(f)=O(\mathrm{Q}_E(f)^2)$ and $\mathrm{D}(f)=O(\mathrm{Q}(f)^4)$ [BdW02, Cor. 6].
- Monotone graph properties have $\mathrm{Q}(f)=\Omega(n)$ on $\binom{n}{2}$-bit inputs, i.e. $\Omega(N^{1/2})$ [ABKRT21, Thm 5] -- a quantum version of the Aanderaa-Karp-Rosenberg evasiveness programme.
- Zero-error quantum gives near-optimal separations for monotone graph properties [BCWZ99].
Monotonicity is the standard sanity check: any conjectured super-quadratic separation must use a non-monotone function.