Theory of Computing ------------------- Title : Quantum Algorithm for Monotonicity Testing on the Hypercube Authors : Aleksandrs Belovs and Eric Blais Volume : 11 Number : 16 Pages : 403-412 URL : https://theoryofcomputing.org/articles/v011a016 Abstract -------- In this note, we develop a bounded-error quantum algorithm that makes $\tilde{O}(n^{1/4}\varepsilon^{-1/2})$ queries to a function $f\colon \{0,1\}^n \to\{0,1\}$, accepts when $f$ is monotone, and rejects when $f$ is $\varepsilon$-far from being monotone. This result gives a super-quadratic improvement compared to the best known randomized algorithm for all $\varepsilon = o(1)$. The improvement is cubic when $\varepsilon = 1/\sqrt{n}$.