Quantum Algorithm for Monotonicity Testing on the Hypercube

In this note, we develop a bounded-error quantum algorithm that makes $\tilde O(n^{1/4}\varepsilon^{-1/2})$queriestoaBooleanfunction$f$, accepts a monotone function, and rejects a function that is $\epsilon$-far from being monotone. This gives a super-quadratic improvement compared to the best known randomized algorithm for all $\epsilon =o(1)$. The improvement is cubic when $\epsilon =1\mathrm{/}\sqrt{n}$.